数据布局经典算法总复习（下卷）

第五章:树和二叉树

先序遍历二叉树的非递归算法。

1. void PreOrderTraverse(BiTree T, void (*Visit)(TElemType)) {//表示用于查找的函数的指针
2.   Stack S; BiTree p = T;
3.   InitStack(S);//S模拟工作栈
4.   while (p || !StackEmpty(S)) {//S为空且下一个结点为空，意味着结束遍历
5.     if (p) {//p有值，则Push进栈为一个工作进程
6.       Visit(p->data); Push(S, p); p = p->lchild;//先序遍历，先Visit
7.     } else {
8. //p为空，则它的上级被Pop出去，成为新的p，再取右孩子。在下一个循环中如果它的上级没右孩子，则说明它的上级是叶子结点（或两端已经工作栈弹出了），则再Pop出它的上级的上级（此时它的上级已经无用，工作栈弹出），取它上级的兄弟结点
9.       Pop(S, p); p = p->rchild;
10.     }
11.   }
12. }

复制代码

使用工作栈的头脑，过程非常复杂，多多复习，巩固加深！

层序遍历二叉树

1. void LayerTraverse(BiTree T, void (*Visit)(TElemType)) {
2.   Queue Q; BiTree p;
3.   InitQueue(Q);
4.   EnQueue(Q, T);
5.   while (!QueueEmpty(Q)) {
6.     DeQueue(Q, p);
7. //每有一个父母结点出队列，就把它的左右孩子放到队尾排队，确保一层一层遍历
8.     if (p) {
9.       Visit(p->data);
10.       EnQueue(Q, p->lchild); EnQueue(Q, p->rchild);
11.     }
12.   }
13. }

复制代码

盘算二叉树中每个结点的条理

1. void LevelRecur(BiTree T, int lev) {
2.   if (T) {
3.     ++lev;//准备遍历下一层
4.     cout << T->data << ' ' << lev << endl;
5.     LevelRecur(T->lchild, lev);
6.     LevelRecur(T->rchild, lev);//下一层启动
7.   }
8. }
9. void Level(BiTree T) {
10.   LevelRecur(T, 0);
11. }

复制代码

输出二叉树根结点到全部叶子结点的路径

1. void OutPath(BiTree T, Stack &S) {//使用一个栈存储路径，起到回溯的作用
2.   if (T) {
3.     Push(S, T);
4.     if (!T->lchild && !T->rchild)
5.       PrintStack(S);//S栈中元素依次输出，不取出
6.     OutPath(T->lchild, S);
7.     OutPath(T->rchild, S);
8.     Pop(S, T);//该节点左右孩子搜索完，则出栈，不再计入路径中
9.   }
10. }

复制代码

由扩展的先序序列，即波兰式，创建二叉树

1. void CreateBiTree(BiTree &T) {
2.   // 读入扩展的先序序列，假定数据元素为字符型，#表示NULL
3.   char ch; scanf("%c", &ch);
4.   if (ch == '#') T = NULL;
5.   else {
6.     T = new BiTNode; T->data = ch;
7.     CreateBiTree(T->lchild);//依次建立二叉树
8.     CreateBiTree(T->rchild);
9.   }
10. }

复制代码

先根遍历树，孩子链表实现

1. void PreOrderRecur(CTree T, int loc, void (*Visit)(TElemType)) {
2.   if (loc == -1) return;
3.   Visit(T.nodes[loc].data);//先查询根结点
4.   ChildPtr p;
5.   for (p = T.nodes[loc].firstchild; p; p = p->next) {
6.     PreOrderRecur(T, p->child, Visit);//取出下个孩子，并查询
7.   }
8. }
9. void PreOrderTree(CTree T, void (*Visit)(TElemType)) {
10.   PreOrderRecur(T, T.root, Visit);
11. }

复制代码

盘算树的深度，孩子兄弟链表实现

1. int TreeDepth(CSTree T) {
2.   if (!T) return 0;//最简单情况，遍历结束条件
3.   CSTree p; int maxh = 0;//maxh为全局变量
4.   for (p = T->firstchild; p; p = p->nextsibling) {//到T的下一个孩子，并且遍历其孩子的兄弟
5.     int h = TreeDepth(p);//当前遍历结点的深度
6.     if (h > maxh) maxh = h;
7.   }
8.   return maxh + 1;
9. }

复制代码

构造huffman树

1. typedef unsigned int WeightType;
2. typedef struct {
3.   TElemType data;
4.   WeightType weight; // 叶子权值的类型
5.   int parent, lchild, rchild; // 三叉静态链表
6. } HTNode, *HuffmanTree;
7. void CreateHuffmanTree(HuffmanTree &HT, int n) {
8.   int m = 2*n-1; // 最终将得到2n-1个结点
9.   HT = new HTNode[m];
10.   for (i=0; i<n; ++i) {
11.     cin >> HT[i].data >> HT[i].weight;
12.     HT[i].lchild = HT[i].rchild = HT[i].parent = -1;//-1即示意为为null
13.   }//输入结点值
14.   for (i=n; i<m; ++i) {
15.   

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。