+循环链表 Day26 Java中的数据结构概念(5)

但是对于一般的二叉树而言，必须用“虚结点”将一棵二叉树补成一棵完全二叉树来存储，

否则无法确定结点之间的前驱后续关系，但是这样一来就会造成空间的浪费

设计不同的结点结构可构成不同的链式存储结构。

在二叉树中每个结点都有两个孩子，则可以设计每个结点至少包括 3 个域：数据域、左孩子域和右孩子域。

数据域存放数据元素，左孩子域存放指向左孩子结点的指针，右孩子域存放指向右孩子结点的指针。如图 （a）所示。

利用此结点结构得到的二叉树存储结构称为二叉链表。

为了方便找到父结点，可以在上述结点结构中增加一个指针域，指向结点的父结点。如图 （b）所示。

采用此结点结构得到的二叉树存储结构称为三叉链表。

遍历（Traverse）：

就是按照某种次序访问树中的所有结点，且每个结点恰好访问一次。

也就是说，按照被访问的次序，可以得到由树中所有结点排成的一个序列。

树的遍历也可以看成是人为的将非线性结构线性化。

这里的“访问”是广义的，可以是对结点作各种处理，例如输出结点信息、更新结点信息等。

在我们的实现中，并不真正的“访问”这些结点，而是得到一个结点的线性序列，以线性表的形式输出

将整个二叉树看做三部分：根、左子树、右子树。如果规定先遍历左子树、再遍历右子树。

那么根据根的遍历顺序就有三种遍历方式

先序/根遍历DLR：根 左子树右子树

中序/根遍历LDR：左子树 根右子树

后根/序遍历LRD：左子树右子树 根

按照层次遍历：

注意：由于树的递归定义，其实对三种遍历的概念其实也是一个递归的描述过程

先序遍历DLR： 1 4 5 2 3 6 7

中序遍历LDR： 4 5 1 3 2 6 7

后序遍历LRD： 5 4 3 7 6 2 1

面试题：已知一棵二叉树的后序遍历的序列为 5 4 3 7 6 2 1，中序遍历的序列为 4 5 1 3 2 6 7，

则其先序遍历的序列是什么？

或者是一棵空树；

或者是具有下列性质的二叉树：

（1）若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；

（2）若它的右子树上所有结点的值均大于它的根节点的值；

（3）它的左、右子树也分别为二叉排序树。

平衡二叉树（Self-balancing binary search tree） 自平衡二叉查找树 又被称为AVL树（有别于AVL算法）

它是一 棵空树

或它的左右两个子树的高度差(平衡因子)的绝对值不超过1，

并且左右两个子树都是一棵平衡二叉树，

同时，平衡二叉树必定是二叉搜索树，反之则不一定

平衡因子（平衡度）：结点的平衡因子是结点的左子树的高度减去右子树的高度。（或反之定义）

平衡二叉树：每个结点的平衡因子都为 1、－1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树。

平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度

平衡二叉树的常用实现方法有AVL、红黑树、替罪羊树、Treap、伸展树等

红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种平衡二叉树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

（4）如果一个节点是红色的，则它的子节点必须是黑色的。

（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-62503-5.html