009-树的遍历和创建、二叉线索树、霍夫曼树

moc

1、树的遍历
二叉树有根、左子树、右子树构成，定义为D、L、R。
DLR组合可以定义6种遍历方案：  LDR 、LRD 、DLR  、DRL 、RDL 、RLD .
一般限定先左后右：于是有三种遍历方案：
        DLR  =>  先(根)序遍历
        LDR  =>  中(根)序遍历
        LRD  =>  后(根)序遍历

先序遍历：ABCDEFGH
中序遍历：BDCEAFHG
后序遍历：DECBHGFA
由于树本身就是一种递归结构，所以采用递归方式遍历树最合适；
先序遍历：

1. void preOrder(BiTNode *root)
   
2. {
   
3.         if (root == NULL)
   
4.         {
   
5.                 return;
   
6.         }
   
7.         // 遍历根
   
8.         printf("%d", root->data);
   
9.         // 遍历左子树
   
10.         preOrder(root->lchild);
    
11.         // 遍历右子树
    
12.         preOrder(root->rchild);
    
13. }

复制代码

中序遍历：

1. void inOrder(BiTNode *root)
   
2. {
   
3.         if (root == NULL)
   
4.         {
   
5.                 return;
   
6.         }
   
7.         // 遍历左子树
   
8.         inOrder(root->lchild);
   
9.         // 遍历根
   
10.         printf("%d", root->data);
    
11.         // 遍历右子树
    
12.         inOrder(root->rchild);
    
13. }

复制代码

后序遍历：

1. void postOrder(BiTNode *root)
   
2. {
   
3.         if (root == NULL)
   
4.         {
   
5.                 return;
   
6.         }
   
7.         // 遍历左子树
   
8.         postOrder(root->lchild);
   
9.         // 遍历右子树
   
10.         postOrder(root->rchild);
    
11.         // 遍历根
    
12.         printf("%d", root->data);
    
13. }

复制代码

分析：   上面三种遍历方法，如果将printf()语句去掉，三种算法完全相同，所以这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。
树的非递归中序遍历：
        利用栈实现中序遍历的先走到的后访问，后走到的先访问。
算法步骤：
            步骤1： 如果结点有左子树，该结点入栈；
                        如果结点没有右子树，访问该结点；
            步骤2： 如果结点有右子树，重复步骤1；
                        如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1
                        如果栈为空，表示遍历结束。
注意： 入栈的结点  其本身和其右子树没有被访问。

1. // 借助于栈结构
   
2. BiTNode* goLeft(BiTNode* t, stack<BiTNode*> &s)
   
3. {
   
4.         if (!t)
   
5.         {
   
6.                 return NULL;
   
7.         }
   
8.         while (t->lchild != NULL)
   
9.         {
   
10.                 s.push(t);
    
11.                 t = t->lchild;
    
12.         }
    
13.         return t;
    
14. }
    
15. 
    
16. void inOrder2(BiTNode* tree)
    
17. {
    
18.         stack<BiTNode*> st;
    
19.         BiTNode *tmp;
    
20.         if (tree == NULL)
    
21.         {
    
22.                 return;
    
23.         }
    
24.        
    
25.         tmp = goLeft(tree, st);
    
26.         while (tmp)
    
27.         {
    
28.                 printf("%d ", tmp->data);
    
29.                 if (tmp->rchild != NULL)
    
30.                 {
    
31.                         tmp = goLeft(tmp->rchild, st);
    
32.                 }
    
33.                 else if (tmp->rchild == NULL && !st.empty())
    
34.                 {
    
35.                         tmp = st.top();
    
36.                         st.pop();
    
37.                 }
    
38.                 else
    
39.                 {
    
40.                         tmp = NULL;
    
41.                 }
    
42.         }
    
43. }

复制代码

2、二叉树的创建
1. #法

1. // #号法  按照给定的先序序列创建二叉树
   
2. BiTNode* CreatBiTree()
   
3. {
   
4.         BiTNode *node = NULL;
   
5. 
   
6.         char h;
   
7.         scanf("%c", &h);
   
8.         if (h == '#')
   
9.         {
   
10.                 return NULL;
    
11.         }
    
12.         else
    
13.         {
    
14.                 node = (BiTNode*)malloc(sizeof(BiTNode));
    
15.                 if (node == NULL)
    
16.                 {
    
17.                         return NULL;
    
18.                 }
    
19.                 node->data = h;
    
20.                 node->lchild = CreatBiTree();   // 递归创建左子树
    
21.                 node->rchild = CreatBiTree();   // 递归创建右子树
    
22.                 return node;
    
23.         }
    
24. }

复制代码

2.   先序+中序   中序+后序
通过先序遍历和中序遍历结构创建二叉树，也可以通过中序遍历和后序遍历结构创建二叉树。
但是不能通过先序和后序遍历创建二叉树。
3、二叉线索树
普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得；若可以将遍历后对应的有关前驱和后继预存起来就可以“顺藤摸瓜”而遍历树。
实质：  把二叉树按照中序遍历的结果存在链表里面。
待续...
4、霍夫曼树
   树的帯权路径长度，组建一个网络，耗费最小WPL(帯权路劲长度)。
霍夫曼树的建立：
        1. 给定 n 个数值（v1, v2, v3, ..., vn）;
        2. 根据这 n  个数值构造二叉树集合 F = (T1, T2, T3 ... Tn),  其中 Ti 的数据域为 vi ,左右子树为空；
        3. 在 F 中选择两颗根结点最小的树作为左右子树构造一颗新的二叉树，这颗新的二叉树的根结点中的值为左右子树根结点值的和；
        4. 在 F 中删除这两颗子树，并将构造的新的二叉树加入 F 中；
        5. 重复 3 和 4 步骤，直到只剩下最后一棵树为止，这棵树就是霍夫曼树。
结论： 霍夫曼树是一种特殊的二叉树；
           霍夫曼树应用于信息编码和数据压缩领域；
           霍夫曼树是现代压缩算法的基础。