树

树形结构是一种非线性结构。

树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。

树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。

树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。

1. 树的实例

家族树：在现实生活中，有入如下血统关系的家族可用树形图表示：

张源有三个孩子张明、张丽和张亮；
张明有两个孩子张林和张维；
张亮有三个孩子张平、张华和张群；
张平有两个孩子张晶和张磊。

attachment:tree.jpg

2. 树的定义

树是由n (n≥0)个结点构成的有限集合；n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：

有且仅有一个特定的结点称之为根，它没有前驱结点；
其余结点分成m(m≥0)个互不相交的有限集合latex($$T_1, T_2,\cdots,T_m$$)，其中每一个集合又都是一棵树，称latex($$T_1, T_2,\cdots,T_m$$)为根结点的子树。

3. 树的图示

倒置的树形图表示

attachment:tree2.jpg

凹入表示

attachment:indenttree.jpg

嵌套集合表示（文氏图表示）

attachment:treeset.jpg

嵌套括号表示（广义表表示）

(A(B(E,F),C,D(G,H(J,K),I)))

4. 树的相关术语

子结点：树中某个结点的子树之根称为该结点的孩子(Child)或子结点
父结点：该结点称为孩子的双亲(Parents)或父亲或父结点。
兄弟结点：同一个双亲的孩子称为兄弟(Sibling)结点。
结点的度：树中的一个结点拥有的子树数称为该结点的度(Degree)。
树的度：一棵树的度是指该树中结点的最大度数。：
叶结点：度为零的结点称为叶子(Leaf)或终端结点。
分支节点：度不为零的结点称分支结点或非终端结点。
路径：若树中存在一个结点序列k1，k2，…，kj，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从kl到kj的一条路径(Path)或道路。
路径的长度：路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。
祖先和子孙：若树中结点k到ks存在一条路径，则称k是ks的祖先(Ancestor)，ks是k的子孙(Descendant)。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。（结点k的祖先和子孙不包含结点k本身。）
结点的层次：根结点的层次为1（也有将根的层次定义为0的），其余结点的层次为父结点的层次加1。即从根结点到该结点的路径长度加1。
树的高度：树中结点的最大层数称为树的高度(Height)或深度(Depth)。
堂兄弟：双亲在同一层的结点互为堂兄弟。
有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnoderedTree)。（若不特别指明，一般讨论的树都是有序树。）
森林：森林(Forest)是m(m≥0)棵互不相交的树的集合。
同构：

5. 树形结构的特点

树中任一结点都可以有零个或多个直接后继(即孩子)结点，但至多只能有一个直接前趋(即双亲)结点。
树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。
祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。
有序树中，同一组兄弟结点从左到右有长幼之分。对这一关系加以延拓，规定若k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边，那么就定义了树中结点之间的横向次序。
将一棵树的根结点去掉，它的子树的集合即为一个森林。而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。
从树的根结点到树中其余结点均存在一条唯一的路径。

6. 树的基本操作

init_tree(t)初始化
destroy_tree(t)销毁树
create_tree(t)创建树
tree_empty(t)判断空树
root(t)返回树根
parent(t, node)返回树t中node结点的父结点
first_child(t, node)返回树t中node结点的第一个子结点
next_sibling(t, node)返回树t中node结点的下一个兄弟结点
insert_child(t, parent, child)在树t中插入子child结点作为parent结点的子结点
delete_child(t, parent, child)删除树t中parent结点的子结点child
tranverse_tree(t, visit)遍历树t，对t的每个结点做一次visit操作且仅作一次。

二叉树

1. 二叉树的定义

二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

二叉树与度为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

2. 二叉树的相关术语

左孩子
右孩子

3. 二叉树五种基本形态

attachment:binarytree.jpg

二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

4. 二叉树的特殊形态

1、满二叉树(FullBinaryTree)

一棵深度为k且有2k-1个结点的二又树称为满二叉树。

满二叉树的特点：

每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。

2、完全二叉树(Complete BinaryTree)

若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

attachment:completetree.jpg

完全二叉树的特点：

满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
完全二叉树中除最下面一层外，各层都充满了结点，每一层的结点个数恰好是上一层结点个数的2倍。

编号：在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。

从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是ki(1≤i≤n)，则有：

若i>1，则ki的双亲编号为[i/2]；若i=1，则Ki是根结点，无双亲。
若2i≤n，则Ki的左孩子的编号是2i；否则，Ki无左孩子，即Ki必定是叶子。因此完全二叉树中编号的结点必定是叶结点。
若2i+1≤n，则Ki的右孩子的编号是2i+1；否则，Ki无右孩子。
若i为奇数且不为1，则Ki的左兄弟的编号是i-1；否则，Ki无左兄弟。
若i为偶数且小于n，则Ki的右兄弟的编号是i+1；否则，Ki无右兄弟。

5. 二叉树的重要性质

性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。

证明：使用数学归纳法证明。

归纳基础：当i=1时，整个二叉树只有一个根结点，此时latex($$2^{i-1}=2^0=1$$)，结论成立。
归纳假设：假设i=k时，结论成立，即第k层上结点总数最多为latex($$2^{k-1}$$)。

那么，因为二叉树中每个节点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的两倍，即latex($$2\times 2^{i-1}=2^k$$)，故结论成立。证毕。

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。

性质4 具有n个结点的完全二叉树的深度为

6. 二叉树的存储结构

6.1. 顺序存储

完全二叉树的顺序存储

将完全二叉树中所有结点按编号顺序依次存储在一个数组bt[0..n]中。其中：

bt[1...n]用来存储结点
bt[0]不用或用来存储结点数目

attachment:completetree.jpg

attachment:treearray.jpg

非完全二叉树的顺序存储

将一般二叉树添上一些 "虚结点"，成为"完全二叉树"

attachment:noncompletetree.jpg

attachment:treearray2.jpg

顺序存储的特点：

对完全二叉树而言，顺序存储结构既简单又节省存储空间。
一般的二叉树采用顺序存储结构时，易造成存储空间的浪费。
- 思考：最坏情况下顺序存储的存储密度是多少？答案：最坏的情况下，一个深度为k且只有k个结点的右单支树需要latex($$2^k-1$$)个结点的存储空间，存储密度为latex($$\frac{k}{2^k-1}$$)。

顺序存储结构的定义

   1 #define MAXSIZE 100
   2 typedef char ElemType;
   3 typedef struct {
   4    ElemType elem[MAXSIZE];
   5    int size;
   6 } sequence_bin_tree;

6.2. 链式存储

二叉链表

二叉树的每个结点最多有两个孩子，可以用链接方式存储二叉树。每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点bintree_node的结构为：

attachment:bintreenode.jpg

一棵二叉树中，所有类型为bintree_node的结点，再加上一个指向开始结点(即根结点)的bintree_node型指针root，就构成了二叉树的链式存储结构，并将其称为二叉链表。

   1 typedef char ElemType;
   2 struct bintree_node{
   3    ElemType data;
   4    struct bintree_node *lchild;
   5    struct bintree_node *rchild;
   6 };
   7 typedef struct bintree_node bintree_node;
   8 typedef struct bintree_node *bintree;

二叉链表的特点：

一个二叉链表由根指针root唯一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。
具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。
找给定节点的父节点非常困难

带父节点指针的链式表示

经常要在二叉树中寻找某结点的父节点时，可在每个结点上再加一个指向其父节点的指针parent，形成一个带双亲指针的二叉链表，称作三叉链表。

attachment:link3tree.jpg

7. 练习

试画出三个结点的树和三个节点的二叉树的所有不同形态。
已知一棵高度为k的树中有n1个度为1的结点，n2个度为2的结点，则该树有多少个叶子节点？给出证明。
已知一棵二叉树有50个结点，则该二叉树的总节点数至少有多少个？
已知一棵二叉树按顺序存储方式存储在A[1...n]中。设计算法求出下标分别为i和j的两个结点的最近公共祖先节点的编号。

树和二叉树

树