数据结构树的总结

树的知识点

在计算器科学中，树（英语：tree）是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

①每个节点有零个或多个子节点；
②没有父节点的节点称为根节点；
③每一个非根节点有且只有一个父节点；
④除了根节点外，每个子节点可以分为多个不相交的子树；

树是图的一种，树和图的区别就在于：树是没有环的，而图是可以有环的。

关于树的术语：

• 节点深度：对任意节点x，x节点的深度表示为根节点到x节点的路径长度。所以根节点深度为0，第二层节点深度为1，以此类推
• 节点高度：对任意节点x，叶子节点到x节点的路径长度就是节点x的高度
• 树的深度：一棵树中节点的最大深度就是树的深度，也称为高度
• 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
• 子节点：一个节点含有的子树的根节点称为该节点的子节点
• 节点的层次：从根节点开始，根节点为第一层，根的子节点为第二层，以此类推
• 兄弟节点：拥有共同父节点的节点互称为兄弟节点
• 度：节点的子树数目就是节点的度
• 叶子节点：度为零的节点就是叶子节点

结点层次

二叉树

每个节点最多含有两个子树的树称为二叉树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树的遍历方式

(先中后序遍历都是相对于根节点来说的，先就先遍历根节点，中就中间遍历根节点，后就后遍历根节点)
先序遍历：先根节点->遍历左子树->遍历右子树
中序遍历：遍历左子树->根节点->遍历右子树
后序遍历：遍历左子树->遍历右子树->根节点
层序遍历：广度优先遍历

二叉树的类型

• 平衡二叉树

当且仅当任何节点的两棵子树的高度差不大于1的二叉树。

满二叉树：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。

完全二叉树：

颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
如果结点度为1，则该结点只有左孩子，即没有右子树。满二叉树一定是完全二叉树，但反过来不一定成立。

二叉查找树

是指一棵空树或者具有下列性质的二叉树：

1.若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
   3.任意节点的左、右子树也分别为二叉查找树；
   4.没有键值相等的节点。

   

红黑树

特征：(首先，红黑树是一颗二叉查找树)
1.每个结点要么是红的要么是黑的。（红或黑）
2.根结点是黑的。 （根黑）
3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。 （叶黑）
4.如果一个结点是红的，那么它的两个儿子都是黑的。 （红子黑）
5.对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。（路径下黑相同）

霍夫曼树

带权路径最短的二叉树称为哈夫曼树或最优二叉树。