树与二叉树的基本知识

树的术语

1. 结点： 树中的每个元素都称为结点， 例如上图中的 A,B,C…
2. 根结点： 位于树顶部的结点， 它没有父结点,比如 A 结点。
3. 父结点： 若一个结点有子结点， 那么这个结点就称为其子结点的父结点。
   例如 A 是 B,C,D 的父节点。
4. 子结点： 一个结点含有的子树的根结点称为该结点的子结点。
   例如 B,C,D 是 A 的子节点。
5. 兄弟结点： 具有相同父结点的结点互称为兄弟结点。
   例如 B,C,D 结点互为兄弟结点。
6. 叶子结点： 没有子节点的节点， 例如 B,D,F,G,H 结点。
7. 结点的层次： 从根开始定义起， 根为第 1 层， 根的子结点为第 2 层， 以此类推。
8. 树的深度（高度） ： 树中结点的最大层次， 右图中的树的深度为 4。
9. 结点的度： 一个结点含有的子树的个数称为该结点的度。
10. 树的度： 一棵树中， 最大的结点的度称为树的度,右图中的树的度为 3。
11. 子孙： 以某结点为根的子树中任一结点都称为该结点的子孙。
12. 森林： 由 n(n>=0)棵互不相交的树的集合称为森林。

高度为h的m叉树和高度为h,度为m的树有什么区别?

1. 度为m的树中，必须至少有一个结点有m个孩子结点
2. m叉树中可以没有一个结点的孩子数等于m，甚至可以是一棵空树。

树的性质：

1. 树中的结点数等于所有结点的度数加1.
2. 度为m的树中第i层上至多有m^{i-1}个结点.
3. 高度为h的m叉树至多有(m^{h} - 1) / (m - 1)个结点
4. 具有n个结点的m叉树的最小高度为ceil(log_{m}(n(m-1)+1))

二叉树的基本概念

二叉树中每个节点的度数均不超过 2。

二叉树和度为2的有序树有什么区别?

1. 度为2的树至少有3个结点，二叉树可以为空。
2. 度为2的有序树的孩子结点的左右次序是相对而言的，
   若某个结点只有一个孩子，则这个孩子就不存在左右这个概念。
   二叉树无论有没有2个孩子，均需要区分左右孩子结点。

满二叉树

性质：

1. 高为 h 的满二叉树上一共有 2^h -1 个结点。
2. 高为 h 的满二叉树上, 每层都有 2^{h-1}个结点。
3. 高为 h 的满二叉树上, 所有的叶子结点都在最后一层。
4. 高为 h 的满二叉树上, 除叶子结点外， 每个结点的度都为 2.
5. 高为 h 的满二叉树上, 对每个结点从上到下， 从左到右进行编号(从 1 开始), 对于任意编号 i, 若有双亲， 则其双亲结点的编号一定是 floor(i/2), 若有孩子结点, 则左孩子编号为 2i, 右孩子编号为 2i+1.

完全二叉树

性质：

1. 高为 h, 有 n 个结点的完全二叉树上, 编号与满二叉树的一一对应。
2. 高为 h, 有 n 个结点的完全二叉树上, 若结点编号 i>floor(n/2), 则该结点一定是叶子结点, 否则是非叶子结点。
3. 高为 h, 有 n 个结点的完全二叉树上, 叶子结点只会处于最后一层和倒数第二层。
4. 高为 h, 有 n 个结点的完全二叉树上, 只可能存在一个结点度为 1 并且它肯定只有左孩子没有右孩子。
5. 高为 h, 有 n 个结点的完全二叉树上, 若 n 为奇数则所有结点度都为 2， 若为偶数，则有一个结点度为 1。
6. 具有 n 个(n>0)结点的完全二叉树的高度为 ceil(log_{2} (n+1))或 floor(log_{2} n)+1

6.证明：设完全二叉树的高度为h，则有
2^{h-1}-1 (高度为h-1的满二叉树)<n≤2^{h} -1(高度为h的满二叉树)
或 2^{h-1}≤n < 2^h 得 2^{h-1}<n+1 ≤ 2^h ，
即 h-1<log_{2}(n+1)≤h,
故 h= ceil(log_{2} (n+1))
或得 h-1 ≤log_{2}(n)<h,
故 h=floor(log_{2} n)+1

二叉树的性质

1. 树中的结点数等于所有结点的度数加1
2. 二叉树第 k 层上的结点数目最多为 2k-1。 (k≥1)
3. 深度为 k 的二叉树至多有 2k -1 个结点。 (k≥1)
4. 包含 n 个结点的二叉树的高度至少为 log2(n+1)。
5. 在任意一棵二叉树中， 若叶子结点的个数为 n0， 度为 2 的结点数为 n2， 则 n0=n2+1 。
   证明： 结点总数为 n0+n1+n2,有 n0+n1+n2 = n1+2n2+1 化简得 n0=n2+1

二叉树的存储结构

顺序存储结构

事实一：所有完全二叉树前k个结点的形状结构完全相同

事实二：完全二叉树中结点编号与其位置一对应

注: 数组编号应从 1 开始， 不然无法满足前面所述的二叉树节点编号之间的关系， 无法做到随机访问。 此方法也是后面堆排序的基础。

链式存储结构

数据结构定义

typedef struct BiTNode{Elemtypedata;struct BiTNode *Ichild, *rchild;
}BiTNode;typedef struct BiTreeBiTNode *root;
}BiTree;

注： 一棵含有 n 个结点的二叉树采用链式存储结构时， 有 n+1 个指针处于闲置状态， 也就是没有高效利用内存

二叉树的遍历

设解决某个递归问题的时间为T(N)其中处理一半问题的时间为T(N/2)
设其他处理的时间为O(N)
得 T(N) = 2*T(N/2) +c*N
则有T(N/2)= 2*T(N/4)+c*N/2
代入得T(N) = 2*(2*T(N/4)+c*N/2)+c*N
以此类推,
T(N) = 2^k* T(N/2^k)+ k*c*N
当N/2^k=1时，(N=2^k,k=log_{2}N 则有T(N)= 2^{k}*O(1)+k*c*N =N*O(1) + logN*c*N
O(nlogn)

以 A 为根节点的二叉树可以在左子树上递归划分

先序遍历

1. 访问根节点
2. 先序遍历左子树
3. 先序遍历右子树

void PreOrder(BiTree T){//先序递归遍历if(T != Null){ visit(T);PreOrder(T->lchild);PreOrder(T->rchild);}
}

中序遍历

1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树

void InOrder(BiTreeT) //中序递归遍历if(T != Null){InOrder(T->lchild); visit(T); InOrder(T->rchild);}
}

中序递归遍历时，当访问到某结点时，其他结点的状态?
当访问到任意结点时，都代表以该结点为根的左子树已经遍历完成并且都退出了栈；
若该结点是其双亲结点的左孩子，则它的双亲结点此时还没有被访问且在栈中;
若该结点是其双亲结点的右孩子，那么此时其双亲结点已经被访问过并且出栈了。

注：对于系统栈来说，中序遍历时，左右子树都访问完才会出栈双亲结点，而非递归遍历时用户自己申请的栈一般是双亲结点出栈后才访问的右子树(具体代码可能有不同的实现)

后序遍历

1. 后序访问左子树
2. 后序访问右子树
3. 访问根节点

void PostOrder(BiTree T) //后序递归遍历if(T != Null){PostOrder(T->lchild);PostOrder(T->rchild); visit(T);}
}

后序递归遍历时，当访问到某结点时，其他结点的状态?
若该结点是其双亲结点的左孩子，此时其双亲结点都没有被访问到并且还在栈中。而且该结点的所有祖先结点也保存在栈中。
若该结点是其双亲结点的右孩子，此时其双亲结点都没有被访问到并且还在栈中。而且该结点的所有祖先结点也保存在栈中。
当访问到任意结点时，都代表以该结点为根的子树已经全部遍历完成并且都退出了栈，不会再访问到。
不管该结点是其双亲结点的左孩子还是右孩子，此时其双亲结点都没有被访问到并且还在栈中。而且该结点的所有祖先结点也保存在栈中。

层序遍历

从上至上、 从左至右依次访问树中的每个节点

void LevelOrder(BiTree T) //层序遍历InitQueue(Q);//声明队列BiTree p; //声明工作结点EnQueue(Q, T);//根结点入队while(!isEmpty(Q)){//遍历整棵树 DeQueue(Q,p);//出队visit(p); //访问当前结点if(p->lchild != Null{ //左孩子入队EnQueue(Q, p->lchild);} if(p->rchild != Null{ //右孩子入队 EnQueue(Q, p->rchild);}}
}

若想要从下到上， 从右到左(也就是层序遍历逆序列)的遍历一棵二叉树， 只需要在层序遍历的基础上再借助一个栈即可实现。

例题

先序序列为 abcd 的不同二叉树的个数为( )B
A.13 B.14
C.15 D.16

f(4) = 2f(3)+2(f(1)× f(2))

f(3) = 2f(2) + f(1)× f(1)

f(2) = f(1) + f(1) = 2
f(3) = 2f(2) + f(1)× f(1) = 5
f(4) = 2f(3)+2(f(1)× f(2)) = 10+4 = 14

思考： 先序序列为1,2,3,…,n的二叉树一共有多少种不同的形状？
f(4) = 2f(3)+2(f(1)× f(2))
= f(3)× f(0) + f(2)× f(1) + f(1)× f(2) + f(0)× f(3), (f(0)=1)

f(n) = f(n-1)× f(0) + f(n-2)× f(1)+… + f(1)× f(n-2) + f(0)× f(n-1), (f(0)=1)