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

moc

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

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

void preOrder(BiTNode *root)
{
        if (root == NULL)
        {
                return;
        }
        // 遍历根
        printf("%d", root->data);
        // 遍历左子树
        preOrder(root->lchild);
        // 遍历右子树
        preOrder(root->rchild);
}

中序遍历：

void inOrder(BiTNode *root)
{
        if (root == NULL)
        {
                return;
        }
        // 遍历左子树
        inOrder(root->lchild);
        // 遍历根
        printf("%d", root->data);
        // 遍历右子树
        inOrder(root->rchild);
}

后序遍历：

void postOrder(BiTNode *root)
{
        if (root == NULL)
        {
                return;
        }
        // 遍历左子树
        postOrder(root->lchild);
        // 遍历右子树
        postOrder(root->rchild);
        // 遍历根
        printf("%d", root->data);
}

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

// 借助于栈结构
BiTNode* goLeft(BiTNode* t, stack<BiTNode*> &s)
{
        if (!t)
        {
                return NULL;
        }
        while (t->lchild != NULL)
        {
                s.push(t);
                t = t->lchild;
        }
        return t;
}

void inOrder2(BiTNode* tree)
{
        stack<BiTNode*> st;
        BiTNode *tmp;
        if (tree == NULL)
        {
                return;
        }
        
        tmp = goLeft(tree, st);
        while (tmp)
        {
                printf("%d ", tmp->data);
                if (tmp->rchild != NULL)
                {
                        tmp = goLeft(tmp->rchild, st);
                }
                else if (tmp->rchild == NULL && !st.empty())
                {
                        tmp = st.top();
                        st.pop();
                }
                else
                {
                        tmp = NULL;
                }
        }
}

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

// #号法  按照给定的先序序列创建二叉树
BiTNode* CreatBiTree()
{
        BiTNode *node = NULL;

        char h;
        scanf("%c", &h);
        if (h == '#')
        {
                return NULL;
        }
        else
        {
                node = (BiTNode*)malloc(sizeof(BiTNode));
                if (node == NULL)
                {
                        return NULL;
                }
                node->data = h;
                node->lchild = CreatBiTree();   // 递归创建左子树
                node->rchild = CreatBiTree();   // 递归创建右子树
                return node;
        }
}

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 步骤，直到只剩下最后一棵树为止，这棵树就是霍夫曼树。
结论： 霍夫曼树是一种特殊的二叉树；
           霍夫曼树应用于信息编码和数据压缩领域；
           霍夫曼树是现代压缩算法的基础。