树的概念与基本术语
树是若干结点的集合，是由唯一的根和若干棵互不相交的子树组成的。树的概念是递归的，即在树的定义中又用到了树的定义。
结点的度：结点拥有的子树个数或者分支的个数。
树的度：树中各结点度的最大值。
层次：从根开始，根为第一层，根的孩子为第二层。
树的高度（或者深度）：树中结点的最大层次。
结点的深度：从根结点到该结点路径上的结点个数
结点的高度：从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径的长度即为该结点在树中的高度。根结点的高度为树的高度。
兄弟：同一个双亲的孩子之间互为兄弟。
堂兄弟：双亲在同一层的结点互为堂兄弟。
有序树与无序树：树中的结点的子树从左到右是有次序的，不能交换，这样的树叫做有序树。可以随便交换的叫做无序树。
丰满树：丰满树即理想平衡树，要求除最底层外，其他层都是满的。
森林：若干棵互不相交的树的集合。
树的存储结构：
1.顺序存储结构：
树的顺序存储结构中最简单直观的是双亲存储结构。用一个整数数组来存储，下标就是该结点，数组元素的内容表示该结点的双亲结点。例如3的双亲是1，则tree[3]=1.
树的双亲存储结构在克鲁斯卡尔算法中有重要应用。
2.链式存储结构：
1）孩子存储结构：孩子存储结构实质上就是图的邻接表存储结构。树就是一种特殊的图。
2）孩子兄弟存储结构：孩子兄弟存储结构与树和森林与二叉树的相互转换关系密切。
二叉树
二叉树满足以下定义：
- 每个结点最多只有两棵子树，即二叉树中结点的度只能为0、1、2
- 子树有左右顺序之分，不能颠倒
满二叉树：如果所有的分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下一层，则这样的二叉树成为满二叉树。
完全二叉树：如果对一棵深度为k，有n个结点的二叉树进行编号后，各结点的编号与深度为k的满二叉树中相对位置上的结点的编号均相同，那么这棵树就是一棵完全二叉树。
一棵完全二叉树一定是由一棵满二叉树从右到左，从下到上，挨个删除结点所得到的。如果跳着删除，则得到的不是完全二叉树。
二叉树的主要性质：
性质1. 非空二叉树上叶子结点数等于双分支结点数加1.
证明：假设叶子结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数为n0+n1+n2。总分支数为n1+2n2。由于除了根结点外，其它结点都有一个分支指向它，所以总分支数=总结点数-1。得到n1+2n2 = n0 + n1 + n2 - 1。得到：n2 = n0 - 1。
一个变形：问二叉树中总的结点数为n，则树中空指针数为多少？可以将空指针数看成是叶子结点，则每个结点都是双分支结点。根据性质1，叶子结点数等于双分支结点数加1，则空指针数=n+1.
性质2. 二叉树的第i层最多有2^(i-1)个结点（i>=1）.
结点最多的情况即为满二叉树的情况，此时二叉树每层上的结点数构成了一个首项为1，公比为2的等比数列。通向为2^(i-1)，i为层号。
性质3. 高度（或深度）为k的二叉树最多有2^k - 1个结点.
最多的情况还是满二叉树，则根据等比公式求和可得(1-2k)/(1-2)=2k - 1.
在这里复习一下等比数列求和公式和等差数列求和公式：
等比数列求和公式.png
等差数列求和公式.png
性质4. 有n个结点的完全二叉树，对各结点从上到下，从左到右依次编号，则结点之间有如下关系：（i为某结点a的编号）
- 如果i不等于1，则a的双亲结点的编号为i/2向下取整
- 如果2i<=n，则a的左孩子的编号为2i；如果2i > n，则a无左孩子
- 如果2i+1 <= n，则a的右孩子编号为2i+1；如果2i+1 > n，则a无右孩子
性质5. 函数catalan( )：给定n个结点，能构成h(n)种不同的二叉树，h(n)=C(2n,n)/(n+1)
性质6. 具有n个结点的完全二叉树的高度或深度为 (log2n向下取整+1)，或者(log2(n+1)向上取整)
二叉树的存储结构
1. 顺序存储结构：
顺序存储结构即用一个数组来存储一棵二叉树，这种存储方式最适合于完全二叉树，用于存储一般的二叉树会浪费大量存储空间。
将完全二叉树中的结点值按编号依次存入一个一维数组中，即完成了一棵二叉树的顺序存储。如果知道了一个结点的下标为i，则该结点的左孩子的下标为2i，右孩子为2i+1（当其存在时）。
2. 链式存储结构（二叉链表存储结构）：
typedef struct BTNode {
char data; //数据域，可更改为其他类型
struct BTNode *lchild;
struct BTNode *rchild;
};
二叉树的遍历算法
二叉树的遍历方式有先序遍历、中序遍历、后序遍历和层次遍历。
1.先序遍历preorder
根、左、右
void preorder(BTNode *p) {
if (p != NULL) {
visit(p); //对该结点的访问操作，例如打印该结点的数值等信息
preorder(p->lchild);
preorder(p->rchild);
}
}
2.中序遍历inorder
左、根、右
void inorder(BTNode *p) {
if (p != NULL) {
inorder(p->lchild);
visit(p);
inorder(p->rchild);
}
}
3.后序遍历postorder
左、右、根
void postorder(BTNode *p) {
if (p != NULL) {
postorder(p->lchild);
postorder(p->rchild);
visit(p);
}
}
典型例题：写一个算法求一棵二叉树的深度，二叉树以二叉链表为存储方式。
int getDepth(BTNode *p) {
int LD, RD;
if (p == NULL)
return 0;
else {
LD = getDepth(p->lchild);
RD = getDepth(p->rchild);
return (LD>RD?LD:RD)+1;//返回左右子树深度的最大值加1
}
}
一个结论：根据二叉树的前、中、后3种遍历序列中的前和中、中和后两对遍历序列都可以唯一确定这棵二叉树，而根据前和后这对遍历序列不能确定这棵二叉树。
例题：假设二叉树采用二叉链表存储结构存储，输出先序遍历序列中的第k个结点的值，假设k不大于总的结点数。
int n;
void print_k_of_preorder(BTNode *p, int k) {
if (p != NULL) {
++n;
if (k == n) {
cout<<p->data<<endl;
return;
}
print_k_of_preorder(p->lchild, k);
print_k_of_preorder(p->rchild, k);
}
}
4.层次遍历level
对二叉树的层次遍历即从上到下，从左到右的遍历结点。
对二叉树的层次遍历，需要建立一个循环队列，先将二叉树头结点入队列，然后出队列，访问该结点，如果它有左子树，则将左子树的根结点入队；如果它有右子树，则将右子树的根结点入队。然后出队列，对出队结点访问，如此反复，直到队列为空为止。
void level(BTNode *p) {
queue<BTNode *> queue;
BTNode *q;
if (p != NULL)
queue.push(p);
while (!queue.empty( )) {
q = queue.front( );
queue.pop( );
cout<<q->data<<endl;
if (q->lchild != NULL)
queue.push(q->lchild);
if (q->rchild != NULL)
queue.push(q->rchild);
}
}
二叉树遍历算法的改进
之前的几个二叉树的深度优先（DFS）遍历算法，都是用递归实现的，这是很低效的。因为递归调用了系统本身的栈，会有很大开销。用户自己实现非递归的算法比较高效。
1. 先序遍历的非递归实现preorder
根结点入栈。当栈不为空时，出栈栈顶元素，将其右结点入栈，左结点入栈...
void PreOrderNonRecursion(BTNode *root) {
stack<BTNode *> node;
BTNode *p = root;
if (p != NULL) {
node.push(p);
BTNode *q;
while (!node.empty()) {
q = node.top();
node.pop();
cout<<q->val<<endl;
if (q->rchild)
node.push(q->rchild);
if (q->lchild)
node.push(q->lchild);
}
}
}
2. 中序遍历的非递归实现inorder
void InOrderNonRecursion(BTNode *root) {
stack<BTNode *> node;
BTNode *p, *q;
p = root;
while (!node.empty() || p != NULL) {
while(p != NULL) {
node.push(p);
p = p->lchild;
}
if (!node.empty()) {
p = node.top();
node.pop();
cout<<p->val<<endl;
p = p->rchild;
}
}
}
3. 后序遍历的非递归实现postorder
vector<int> PostOrderNonCursivion(BTNode *root) {
vector<int> postSeq;
stack<BTNode *> s;
if (root == NULL)
return postSeq;
BTNode *cur;
s.push(root);
BTNode *pre = NULL;
while (!s.empty()) {
cur = s.top();
if ((cur->left == NULL && cur->right == NULL) || (pre != NULL) && (pre == cur->left || pre->cur->right)){
/* 如果这个结点是叶子结点，或该结点的左右孩子被访问过了，则可访问它 */
postSeq.push_back(cur->val);
pre = cur;
s.pop();
}
else {
if (cur->right != NULL) {
s.push(cur->right);
}
if (cur->left != NULL) {
s.push(cur->left);
}
}
}
}
线索二叉树
二叉树非递归遍历算法避免了系统栈的调用，提高了一定的执行效率。线索二叉树可以将用户栈也省掉，把二叉树的遍历过程线性化，进一步提高效率。
n个结点的二叉树有n+1个空链域，线索二叉树将这些空链域利用起来。
二叉树被线索化后近似于一个线性结构，分支结构的遍历操作就转化为了近似于线性结构的遍历操作，通过线索的辅助使得寻找当前结点前驱或者后继的平均效率大大提高。
线索二叉树的结点定义如下：
typedef struct TBTNode {
char data;
int ltag, rtag; //线索标记
struct TBTNode *lchild;
struct TBTNode *rchild;
};
其中的两个线索标记，如果ltag=0，则表示lchild为指针，指向结点的左孩子；如果ltag=1，则表示lchild为线索，指向结点的直接前驱。
如果rtag=1，则表示rchild为线索，指向结点的直接后继。
线索二叉树可以分为前序线索二叉树、中序线索二叉树、后序线索二叉树。对一棵二叉树中所有结点的空指针域按照某种遍历方式加线索的过程叫做线索化，被线索化了的二叉树称为线索二叉树。
中序线索二叉树的考察最频繁。中序线索化的规则是，左线索指针指向当前结点在中序遍历序列中的前驱结点，右线索指针指向后继结点。
void InThread(TBTNode *p, TBTNode *&pre) {
if (p != NULL) {
InThread(p->lchild, pre);
if (p->lchild == NULL) {
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
InThread(p->rchild, pre);
}
}
通过中序遍历建立中序线索二叉树的主程序如下：
void createInThread(TBTNode *root) {
TBTNode *pre = NULL;
if (root != NULL) {
InThread(root, pre);
pre->rchild = NULL;
pre->rtag = 1;
}
}
二叉树的应用
1. 二叉排序树和平衡二叉树
2. 赫夫曼树和赫夫曼编码
赫夫曼树
赫夫曼树又叫做最优二叉树，它的特点是带权路径最短。
树的带权路径长度WPL：所有叶子结点的带权路径长度(从该结点到根之间的路径长度乘以结点的权值)之和。
赫夫曼树的构造方法
1）将这n个权值分别看作只有根结点的n棵二叉树，这些二叉树构成的集合记为F
2）从F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，新的二叉树的根结点的权值为左右子树根结点权值之和。
3）重复进行，直到构造成一棵二叉树。
赫夫曼编码
在存储文件的时候，对于包含同一内容的文件有多种存储方式，可以找出一种最节省空间的存储技术。这就是赫夫曼编码的用途。常见的.zip压缩文件和.jpeg图片文件的底层技术都用到了赫夫曼编码。
按字符出现的次数为权值，构造赫夫曼树，再进行前缀编码。
网友评论