3.2 中序遍历的非递归算法
二叉树中序遍历非递归算法的关键之处在于，在中序遍历过某个节点的整个左子树之后，怎样找到该节点的根以及右子树。
基本思想：
建立一个栈；根结点进栈，遍历左子树；根结点出栈，输出根结点，之后遍历右子树。
void InOrderTraverse(BiTree root) { BiTree p = root; stack<BiTree> s;//构建一个栈 while(p || !s.empty()) { if(p) { s.push(p); //根结点入栈 p = p->lChild;//指向左子树 } else { BiTree t = s.top(); cout << t->data <<endl; //打印根结点 p = t->rChild; //指向右子树 s.pop(); //根结点出栈 } } }
3.3 二叉树的层次遍历算法
对于一颗二叉树，从根结点开始，从上到下，从左到右的顺序访问每一个结点。每一个结点仅仅访问一次。
算法思路：
使用一个队列；将根节点进队；队不空时进行循环，从队列中出队一个结点*p，访问节点p；若p有左，右孩子结点，将左孩子结点和右孩子结点进队。
void LevelOrder(BTree root) { BTree p = root; queue<BTree> que; que.push(p); while(!que.empty()) //队不空时进行循环 { BTree t = que.front(); cout << t->data << endl; //访问根节点 if(t->lChild) que.push(t->lChild);//有左孩子时将左孩子入队 if(t->rChild) que.push(t->rChild);//有右孩子时将右孩子入队 } }
还可以用两个栈结构来模仿队列实现二叉树的层序遍历，代码如下所示：
void LevelOrder(BTree root) { BTree p = root; stack<BTree> s1, s2; s1.push(root); while(!s1.empty() || !s2.empty()) { while(!s1.empty()) { BTree t = s1.top(); s2.push(t); s1.pop(); } while(!s2.empty()) { BTree t = s2.top(); s1.push(t->lChild); s1.push(t->rChild); cout << t->data<<endl; s2.pop(); } } }
3.4 二叉树遍历算法的应用
当只有一个二叉树的前序遍历序列时，二叉树是不唯一的，所以需要在前序遍历序列中添加空结点的值，如abc##de#g##f###，这样表示出来的二叉树就是唯一的。这样可以根据带空值的二叉树前序遍历序列来构建二叉树：
void CreatBiTree(BTree root) { char ch = ''; cin >> ch; if(ch == '#') root = nullptr; else { root = new BTree; //新建一个结点 root->data = ch; CreatBiTree(root->lChild);//构建左子树 CreatBiTree(root->rChild);//构建右子树 } }
复制二叉树：
如果是空树，则递归结束；否则，申请新的结点空间，复制根结点，之后递归复制左子树，之后递归复制右子树。
void Copy(BiTree root, BiTree newT) { if(root == nullptr) { newT = nullptr; return; } else { newT = new BiTree; newT->data = root->data; Copy(root->lChild, newT->lChild); Copy(root->rChild, newT->rChild); } }
计算二叉树的深度
如果为空树，则深度为0；否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大值再加1。
int m = 0, n = 0;//分别记录左右子树的深度 int Depth(BiTree root) { if(root == nullptr) return 0; else { m = Depth(root->lChild); n = Depth(root->rChild); if(m > n) return m + 1; else return n + 1; } }
计算二叉树中结点的总数
如果是空树，则结点个数为0；否则，结点个数为左子树的结点个数+右子树的结点个数再加1。
int NodeCount(BiTree root) { if(root == nullptr) return 0; else return NodeCount(root->lChild) + NodeCount(root->rChild) + 1; }
计算二叉树中叶子结点的总数
int LeafCount(BiTree root) { if(root==nullptr) return 0; else if(root->lChild == nullptr && root->rChild == nullptr) return 1; else return leafCount(root->lChild) + leafCount(root->rChild); }
3.5 线索二叉树
利用二叉链表中的空指针域，如果某个结点的左孩子为空，则将空的左孩子的指针域改为指向其前驱；如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继，这种改变指向的指针称为线索。加上了线索的二叉树称为线索二叉树(Threaded Binary Tree)。对二叉树按照某种遍历次序使其变为线索二叉树的过程称为线索化。
为了区分左指针和右指针到底是指向孩子的指针还是指向前驱/后继的指针，对二叉链表的每个结点增设两个标志域ltag和rtag，并规定，ltag=0时，左指针指向左孩子；ltag=1时，左指针指向前驱；右标志域同样进行这样的规定。
typedef struct BiThrNode {//线索二叉树的结点结构 int data; //数据域 int ltag, rtag; //标志域 struct BiThrNode *lChild, *rChild;//指针域 }*BiTheTree;
增设了头结点的线索二叉树如下所示：
4、树和森林
森林：是m(m≥0)棵互不相交的树的集合。
4.1 树的存储结构
双亲表示法：定义结构数组，存放树的结点，每个结点含有两个域：数据域：存放结点本身信息；双亲域：指示本结点的双亲结点在数组中的位置。双亲表示法的示意图如下图所示：
双亲表示法的特点是：找某个子结点的双亲容易，但是找某个根结点的孩子比较难，需要遍历整个数组。双亲表示法的数据结构表示如下所示：
typedef strruct PTNode {//结点结构 TElemType data; int parent; //双亲位置域 }PTNode; #define MAX_TREE_SIZE 100 typedef struct {//树结构 PTNode nodes[MAX_TREE_SIZE ]; int r, n; //根结点的位置和节点的个数 }PTree;
孩子链表法：把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个节点有n个孩子链表(叶子结点的孩子链表为空表)。而n个头指针又组成一个线性表，用顺序表(含有n个元素的结构数组)存储。孩子链表法的示意图如下所示：
孩子链表法的数据结构表示如下所示：
typedef struct CTNode {//孩子结点结构 int child; //孩子结点所在的下标 struct CTNode *next; }*ChildPtr; typedef struct {//双亲结点结构 TElemType data; ChildPtr firstChild;//孩子链表头指针 }CTBox; #define MAX_TREE_SIZE 100 typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r;//结点数量和根结点的位置 };
孩子链表法找孩子容易，但是孩子找双亲比较难，所以可以给双亲结点结构中添加一个双亲的下标记录，这样结合双亲表示法和孩子链表法形成：带双亲的孩子链表，找双亲和找孩子都比较容易，示意图如下所示：
孩子兄弟表示法：也叫二叉树表示法或者二叉链表表示法。这种方法使用二叉链表作为树的存储结构，链表中的每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。
typedef struct CSNode { ElemType data; struct CSNode *firstChild, *nextSilbing; }* CSTree;
孩子兄弟表示法的示意图如下所示：
这种表示方法找孩子和兄弟比较容易，找双亲比较困难。
4.2 森林与二叉树
将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作。由于树和二叉树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可以导出树与二叉树之间的一个对应关系。
利用存储结构作为媒介，可以找到二叉树和树之间的对应关系，如下图所示：
从上图可以发现规律：一棵树某个结点的兄弟节点转化成二叉树之后变成这个节点的右孩子结点；而一棵树某个结点的第一个孩子结点转化成二叉树中的左孩子结点。
将树转化成二叉树的方法：首先加线：在兄弟之间加一条线；之后抹线：对每个结点，除了其左孩子之外，去除其与其余孩子之间的关系；最后旋转：以树的根结点为轴心，将整棵树顺时针旋转45°。将树转化为二叉树的示意图如下图所示：
将二叉树转化为树的方法：首先加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子… …沿着分支找到所有的右孩子，都与p的双亲用线连起来；之后抹线：抹掉原二叉树中双亲与右孩子之间的连线；最后调整：将结点按层次排序，形成树结构。二叉树转化成树的示意图如下所示：
将森林转化为二叉树的方法(二叉树与多棵树之间的关系)：首先将各棵树分别转化成二叉树；之后将每棵树的根结点用线相连；之后以第一棵树的根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树的树型结构。森林转化为二叉树的示意图如下图所示：
将二叉树转化为森林的方法：首先抹线，将二叉树中根结点与其右孩子连线，及沿右分枝搜索到的所有右孩子之间的连线全部抹掉，使之变成孤立的二叉树；之后还原，将孤立的二叉树还原成树。二叉树转化为森林的示意图如下图所示：
4.3 树的遍历(三种方式)
先根遍历：若树不空，则先访问根结点，然后依次先根遍历各个子树；后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点；层次遍历：若树不空，则自上而下，自左至右访问树中的每个结点。树的遍历示意图如下图所示：
4.4 森林的遍历
首先将森林看成由三部分组成，第一部分是第一棵树的根结点；第二部分是第一棵树的子树森林；第三部分是其他树构成的森林。这样先序遍历的遍历顺序为：第一部分，第二部分，第三部分，即一次从左至右对森林中的每一棵树进行先根遍历。中序遍历的顺序为：第二部分，第一部分，第三部分，即依次从左至右对森林中的每一棵树进行后根遍历。森林遍历的示意图如下所示：
5、哈夫曼树
首先通过一个引入案例来了解引入哈夫曼树：如下图所示的两个不同的判别树，不同树在相同输入情况下的计算次数有很大差距，怎样构造一个判别树使得判断的次数最少，效率最高，这就是构造哈夫曼树的过程，哈夫曼树也叫最优二叉树。
5.1 哈夫曼树的基本概念
路径：从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：两个结点之间路径上的分支数量；路径长度示意图如下图所示：
树的路径长度：从树根 到每一个结点的路径长度之和，记作TL，包含结点数目相同的二叉树的路径长度不一定相同，在结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。但是路径长度最短的不一定是完全二叉树。
权重：将树中的结点赋值一个有着某种意义的数值，则这个数值称为该结点的权重。
结点的带权重路径长度：从根节点到该节点之间的路径长度与该节点的权重的乘积。
树的带权重路径长度：树中所有叶子节点的带权路径长度之和。
哈夫曼树：带权路径长度最短的树叫做哈夫曼树，也叫最优树；注意带权路径长度最短是在“度相同”的树中比较而得的结果，因此有最优二叉树(带权路径长度最短的二叉树)，最优三叉树等。满二叉树不一定是哈夫曼二叉树。哈夫曼树中权重越大的叶子结点离根结点越近。具有相同权重结点的哈夫曼树不是唯一的。
5.2 哈夫曼树的构造算法
因为哈夫曼树中权重越大的叶子节点离根结点越近，所以可以使用贪心算法，构造哈夫曼树是首先选择权重小的叶子节点。哈夫曼树算法的流程如下所示：
哈夫曼树中只有度为0和度为2的结点，没有度为1的结点。
包含n个叶子结点的哈夫曼树中共有2n-1个结点，因为包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新的结点。下图展示了哈夫曼树的构造过程：
哈夫曼算法的实现：
结点类型定义：
typedef struct {//哈夫曼树结点定义 int weight; //结点权重 int parent, lCh, rCh; //双亲结点，左孩子结点，右孩子结点 }HTNode, *HuffmanTree;
//哈夫曼树构造算法 void CreateHuffmanTree(HuffmanTree HT, int n) { if(n<=1)return; int m = 2*n-1; HT = new HTNode[m+1]; //初始化数组 for(int i = 1; i <= m; ++i) {//初始化都为根结点 HT[i].lCh = 0; HT[i].rCh = 0; HT[i].parent= 0; } for(int i = 1; i <=m; ++i) cin >> HT[i].weight;//初始化权重 for(i = n+1; i <=m; ++i) { //在HT[k](1<=k<=i-1)中选择两个双亲域为0，同时权重值最小的结点并返回它们在HT中 //的需要s1和s2 Selece(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lCh=s1; HT[i].lCh=s2; HT[i].weight = HT[s1].weight+HT[s2].weight; } }
5.3 哈夫曼编码
在远程通讯中，要将待传字符转换成由二进制组成的字符串，如下图所示：
若使用等长的编码，则会比较浪费存储空间；若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能尽可能少。但是这样处理会出现重码，从而导致解码混乱：
所以设计不等长编码的关键在于，使得任一字符的编码都不是另一个字符编码的前缀 – 前缀码。哈夫曼编码要解决的问题就是：设计使得电文长度最短的前缀码。哈夫曼编码规则如下所示：
哈夫曼编码的示意图如下图所示：
寻找哈夫曼编码的代码如下所示：
