数据结构二叉树知识点总结
时间：2022-09-05 00:00:00
术语
1.节点度：节点中子树的数量称为节点度；
2. 叶节点或终端节点：零度节点；
3. 非终端节点或分支节点：度不为零的节点；
4. 父节点或父节点：如果一个节点含有子节点，则该节点称为子节点的父节点；
5. 兄弟节点：具有相同父节点的节点互称兄弟节点；
6.节点层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推；
7. 树的高度或深度：树中节点的最大层次；
8. 表兄弟节点：同一层节点的父节点互为表兄弟；
9. 节点的祖先：从根到节点分支的所有节点；
10. 孙:以节点为根的子树中的任何一个节点都被称为节点的。
11. 森林：由m（m>=0)互不相交的树的集合称为森林；
12.满二叉树：深度为k，且有2^k-1 (2k次减一)节点称为满二叉树
13.完全二叉树：完全二叉树是由满二叉树引起的。对于深度为K的二叉树，当每个结点与深度为K的满二叉树中的数字从1到n的结点对应时，称为完全二叉树。叶节点只能出现在下层和下层，下层的结点集中在该层左侧的几个位置
二叉树的性质
1.在非空二叉树中，第一层的不超过2^(i-1),i>=1；
2.深度为h的二叉树最多2^h-1个结点(h>=一、至少有h个结点；
3.对于任何二叉树，如果叶结点是N0，度数为2的结点总数为N2，则N0=N2 1；
4.有n个结点完全二叉树的深度为K =[log2n」 1(取下整数)
5.有N个结点的完全二叉树如果按顺序存储每个结点，结点之间有以下关系： 若I为结点编号则 如果I>1.父结点的编号为I/2；
6.如果2*I<=N，左儿子(即左树根结点)的编号为2*I；若2*I>N，无左儿子； 如果2*I 1<=N，右儿子的结点号为2*I 1；若2*I 1>N，没有右儿子。
7.给定N个节点可以构成h(N)种植不同的二叉树。h(N)卡特兰数第N项。h(n)=C(2*n，n)/(n 1)。
8.有i个枝点，I总长度为所有枝点，J叶道路长度总和J=I 2i
二叉树遍历有三种方式：
(1)前序遍历（DLR），先访问根结点，再遍历左子树，最后遍历右子树。简记根-左-右。
(2)中序遍历（LDR），先遍历左子树，再访问根结点，最后遍历右子树。记住左-根-右。
(3)后序遍历（LRD），先遍历左子树，再遍历右子树，最后访问根结点。记住左-右-根。
