数据结构-树与二叉树-概念及性质

树的预备知识

• 一棵树是 N 个节点的有限集，N等于0时，称为空树。非空树时且仅有一个节点作根，其余节点本身又时一棵树，称为根节点的子树。
• 除根节点以外每个节点都有一个父亲，没有儿子的节点称为树叶，具有相同父亲的节点为兄弟。
• 树中一个节点的子节点的个数成为该节点的度，度大于0的节点成为分支节点，度等于0的系欸但成为叶子节点，树中最大度数称为树的度。
• 节点 n1 到 nk 的路径为 n1,n2,n3,…,nk 的序列,ni是ni+1的父亲。路径的长为路径上边的条数。
• 每个节点到它自己的路径为0的，一棵树从根到节点仅存在一条路径。
• 根的深度为0，树叶的高都为0。树的高为根的高。树的深度为最深的树叶的深度。树的高度（深度）是树中节点的最大层数，节点的层次以根为开始逐层向下。

树的性质

1. 树中的节点数等于所有节点的度数加1
2. 度为 m 的树中第 i 曾上至多有$m^{i-1}$mi−1 次方个节点$(i>1)$(i>1)。
3. 高度为 h 的 m 叉树至多有 $(m^h-1)/(m - 1)$(mh−1)/(m−1)。
4. 具有 n 个节点的 m 叉树的最小高度为 $log_m(n(m-1)+1)$logm​(n(m−1)+1)。

二叉树的与度为2的有序树的区别

• 二叉树可以为空，而度为2的有序树至少有三个节点。
• 二叉树的孩子节点适中有左右之分，而度为2的有序树的孩子节点次序是相对的。

满二叉树

• 一颗高度为 h，且含有$2^h-1$2h−1个节点的二叉树为满二叉树。
• 若存在编号为 i 的节点，其双亲的编号为 $i/2$i/2 ,左孩子为 $2i$2i ,右孩子为$2i+1$2i+1。

完全二叉树

• 设一个高度为 h ，有 n 个节点的二叉树，当且仅当其每个节点都与高度为 h 的满二叉树中编号 1 ~ n 的节点一一对应时，称为完全二叉树。
• 若 $i<=n/2$i<=n/2，则节点 i 为分支节点，否则为叶子节点。
• 叶子节点只可能在层次最大的两层上出现。对于最大层次的叶子节点，都一次排在最左边的位置上。
• 度为 1 的节点若存在，则可能有一个，且时编号最大的分支节点，并且孩子节点一定是左节点。

二叉排序树

• 若树不为空，且对于任意节点存在左子树或右子树，则其左子树上所有节点的关键字均小于该节点，右子树上所有节点的关键字均大于该节点。

平衡二叉树

• 树上任意节点的左子树和右子树的深度相差不超过1。

二叉树的性质

1. 非空二叉树上的叶子节点数等于度为 2 的节点数加1，即$n_0=n_2+1$n0​=n2​+1。
2. 非空二叉树上第 K 上至多有$2^{k-1}$2k−1 个节点$(k\geq1)$(k≥1)
3. 高度为 h 的二叉树至多有$2^h-1$2h−1个节点$(h\geq1)$(h≥1)
4. 对于完全二叉树按从上到下，从左到右的顺序依次编号1 ~ $n$n,则有以下关系：

• 当$i>1$i>1，且 $i$i 为偶数时，其双亲节点的编号为 $i/2$i/2 ,他是左孩子。当 $i$i 为奇数时，其双亲节点的编号为$(i-1)/2$(i−1)/2，他是有孩子。
• 当$2i\leq n$2i≤n时，节点 $i$i 的左孩子编号为$2i$2i , 否则无左孩子。
• 当$2i+1\leq n$2i+1≤n时，节点 $i$i 的右孩子编号为$2i+1$2i+1 , 否则无右孩子。
• 节点 $i$i 所在的层次为$log_2{i} +1$log2​i+1。

5. 具有 $n$n 个$(n>0)$(n>0)节点的完全二叉树的高度为$log_2{n}+1$log2​n+1或 $log_2(n+1)$log2​(n+1)