树

树(Tree): n(n≥0)个结点构成的有限集合。

1.当n=0时,称为空树; 2.对于任一棵非空树(n> 0),它具备以下性质:

树中有一个称为"根(Root)“的特殊结点,用r表示; 其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,称为原来树的"子树(SubTree)”

树的一些基本术语

结点的度(Degree):结点的子树个数树的度:树的所有结点中最大的度数叶结点(Leaf):度为0的结点父结点(Parent):有子树的结点是其子树的根结点的父结点子结点(Child):若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。兄弟结点(Sibling):具有同一父结点的各结点彼此是兄弟结点。路径和路径长度:从结点n1到nk的路径为一个结点序列$n_0$ , $n_1$,… , $n_k$, $n_i$是 n_{i+1}的父结点。路径所包含边的个数为路径的长度.祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点.子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙.结点的层次(Level):规定根结点在1层，其它任一结点的层数是其父结点的层数加1.树的深度(Depth):树中所有结点中的最大层次是这棵树的深度.

二叉树

1. 定义

二叉树T：一个有穷的结点集合。 这个集合可以为空 若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

完全二叉树Complete Binary Tree)有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i（1 ≤ i ≤ n）结点与满二叉树中编号为 i 结点在二叉树中位置相同

2. 二叉树几个重要性质

*一个二叉树第 i 层的最大结点数为: $2^{i-1}$ i≥1 *深度为k的二叉树有最大结点总数为: $2^k-1$ k≥1 *对任何非空二叉树 T，若$n_0$表示叶结点的个数、$n_2$是度为2的非叶结点个数，那么两者满足关系$n_0$= $n_2$+1

3. 二叉树的存储结构

顺序存储结构

完全二叉树：按从上至下、从左到右顺序存储n个结点的完全二叉树的结点父子关系

*非根结点(序号 i > 1）的父结点的序号是[i/2]; *结点(序号为 i)的左孩子结点的序号是2i，(若2i<= n，否则没有左孩子); *结点(序号为 i)的右孩子结点的序号是 2i+1，(若2i+1<= n，否则没有右孩子)

链表存储

typedef struct TreeNode* BinTree; typedef BinTree Position; struct TreeNode { ElementType Data; BinTree Left; BinTree Right; }