线索二叉树以及哈夫曼树

桃扇骨 2023-10-11 17:57 52阅读 0赞

*  线索二叉树有前驱结点和后继节点的概念，

线索二叉树分为中序线索二叉树，前序线索二叉树，后序线索二叉树。中序线索二叉树就是根据中序遍历的结果,把中序遍历的结果看成一个线性表，对于线性表来说，每一个节点都会有一个前驱节点和一个后继节点。

![在这里插入图片描述][f26c5b5c7a1e46e8b5a91d6d5db4cbc4.png]

上图二叉树的中序遍历结果是：DBAGECF。  
D没有前驱节点，F没有后继节点。如果想找一个节点的前驱节点，例如想找E的前驱节点，只能从根节点开始再进行一次中序遍历，用两个指针，一个指向当前节点，一个指向当前节点的上一个遍历的节点。

对普通二叉树结构进行改造，升级为线索二叉树。

typedef struct Node{
        
        int data;
        struct Node * left;
        struct Node * right;
        int ltag;//表示左节点的指向类型 指向的是真正的左节点还是前驱节点
        int rtag;//表示右节点的指向类型 指向的是真正的右节点还是后继节点 （如果指向的不是真正自己节点的指针成为线索指针）
    //两个tag标识为0的时候，表示指向的为其子节点，标识为1的时候表示指向是线索节点。
    }*TreeNode;

最终的目的还是得到二叉树的中序遍历序列后，能够挨个遍历所有节点，如果只是单纯的一个中序遍历序列，则无法根据一个元素找到下一个元素，因为没有指针，而将这些叶子节点的空指针线索化以后，则可以很顺利的遍历二叉树。

理解中序前驱，中序后继，先序前驱，先序后继节点的概念，中序前驱就是在中序遍历的序列中某个节点的前驱节点。

*  中序线索化实现代码

//pre节点，保存中序遍历时某节点的前驱节点
    Tree pre = NULL;
    
    //将tree节点线索化
    void clue(Tree tree) {
        
        //如果当前节点的左节点为空，则应该让当前节点的左节点线索化
        if(tree->left == NULL){
        
            tree->left = pre;
            tree->ltag = 1;
        }
        if(pre != NULL && pre->right == NULL){
        
            //这种情况是当前节点的前驱节点不是NULL（pre指针已经移动过了，并且pre指针的right是NULL，说明是个叶子节点right是NULL，则此时需要将pre节点指向的节点的right）
            pre->right = tree;
            pre->rtag = 1;
        }
        //重新赋值前驱节点
        pre = tree;
    }
    
    void visit(Tree tree) {
        
        if (tree != NULL) {
        
            visit(tree->left);
            //printf("%d,", tree->data);
            clue(tree);//中序线索话二叉树
            visit(tree->right);
        }
    }
    
    void zhongxu(Tree tree) {
        
        visit(tree);
        //判断最后一个节点的rchild指针是否为NULL，如果是则更正为1
        if(pre ->right == NULL){
        
            pre->rtag = 1;
        }
    }
    
    int main() {
        
    
        //定义一个二叉树
        Tree tree;
        tree = NULL;
        //添加元素
        addNode(tree, 20);
        addNode(tree, 15);
        addNode(tree, 33);
        addNode(tree, 42);
        addNode(tree, 1);
        addNode(tree, 9);
    
        //中序遍历
        zhongxu(tree);
        return 0;
    }

处理完所有节点的线索化以后，最后一个节点的线索化要单独处理，在中序遍历的过程中最后一个访问的节点肯定没有子节点了，所以转换成中序线索序列后，该节点肯定也没有后继节点了，所以要让最后一个节点的后继节点设置为null，并将rtag设置为1，表示没有后继节点。

前序遍历时要单独注意，上图二叉树的前序遍历结果是：ABDCEGF。 B的前驱节点是A，后继节点是D，由于在前驱遍历时是先访问根节点再访问左节点，再访问右节点，所以在根节点会被访问2次，此时在访问左节点时需要判断左节点的类型是不是ltag == 0 。

*  中序线索二叉树找后继。

在中序遍历下，访问顺序是左根右，所以一个节点的后继节点应该是该节点的最后一个不为null的左节点。

//找到以p节点为根节点的二叉树在中序遍历序列中最开始的节点
    Tree findNextNode(TNode * p){
        
        Tree lNode = p->left;
        while (lNode->ltag == 0){
        
            lNode = lNode->left;
        }
        return lNode;
    }
    
    Tree nextNode(TNode * p ){
        
        if(p->rtag == 0){
        
            return findNextNode(p->right);
        }
        return p->right;
    }
    
    //使用后继节点遍历这颗树
    void inOrder(Tree tree){
        
        //先找到这颗树在中序遍历序列中的首个节点
        TNode * firstNode = findNextNode(tree);
        //从这个节点开始一次后继遍历
        while (firstNode != NULL){
        
            printf(" %s \n", firstNode->data );
            firstNode = nextNode(firstNode);
        }
    }

这里要注意的是，使用中序线索序列遍历二叉树的时候，在找下一个节点的时候，也就是后继节点的时候需要判断这个节点的ltag是否是0，如果是0，则需要一次循环找到左子节点的中序遍历序列的首个节点，如果是1，则说明已经被线索化，那么直接返回左子节点即可。

*  树的存储方式

1.（双亲表示法） 这里以广义上的树来说，可以使用顺序存储来实现，定义一个数组，每个元素的parent保存了父节点的下标。这种表示方法为双亲表示法。

typedef struct Node {
        
        int parent = -1;
        int data;
    } ThreadNode;
    
    int main() {
        
    
        ThreadNode threadNode[10];
        threadNode[0].data = 5;
        threadNode[1].data = 10;
        threadNode[1].parent = 0;
    	
    	return 0;
    }

2.（孩子表示法，使用了顺序+链式存储）

同样是有个数组，是一个结构体数组，结构体数组保存了每个树节点的真正的数据，以及一个结构体，结构体是一个孩子结构体，保存了当前是父节点的第几个孩子以及下一个孩子的指针。

struct CTNode{
        
        int child;//当前是父节点的第几个孩子
        struct CTNode *next;//下一个孩子
    };
    
    typedef struct {
        
        int data;
        struct CTNode * firstChild;//第一个孩子指针
    } CTBOX;
    
    typedef struct {
        
        CTBOX nodes[20];//顺序存储方式实现数组
        int n,r;//节点数和根的位置
    };

1.  （孩子兄弟表示法，纯链式存储方式）

typedef struct CSNode{
        
        int data;//节点数据
        struct CSNode * firstchild;//该指针保存第一个孩子节点
        struct CSNode * nextsibling;// 该指针保存当前节点的右兄弟指针
    };

firstchild表示当前节点的第一个孩子节点，而nextsibling保存了当前节点的右兄弟节点。利用这种存储方式可以将多叉树转换为2叉树（树和二叉树相互转换问题）。  
上述过程可以将树转换为二叉树，而根据转换思想，我们也可以逆推出将二叉树转换为树。

*  二叉树和森林转换

森林：森林是m(m >= 0)颗互不相交的树的集合。

将森林转换成二叉树：将每个森林先转换成二叉树，那么每个森林的根节点可以看成是一系列的兄弟节点，将这些兄弟节点连起来就组成了二叉树。

将二叉树转换为森林：可以将二叉树的没一个节点的右节点都看成兄弟节点，依次把这些兄弟节点看成头节点拆开，变成了森林。

*  树和森林的遍历

树的遍历方式有先根遍历，后根遍历，层次遍历。

先根遍历就是先访问树的根节点，如果有下一颗子树，继续访问下一颗子树。其遍历的结果应等于将该树转化为二叉树以后的前序遍历结果。  
***树的后根遍历其遍历结果等同于转换成二叉树以后的中序遍历。***

先根遍历和后根遍历为深度优先遍历 （优先往深处走），而层次遍历是一种广度优先遍历（优先往广度走）。

森林的遍历方式有先序遍历和后序遍历。

对于森林的先序遍历来说，先序遍历就是把森林中的每颗子树用先跟遍历的方式遍历一遍。  
***森林的中序遍历，效果等同于依次对各个子树实现后根遍历，注意是后根遍历！！！！！！！***

##### 哈夫曼树 #####

*  带权路径

1.  节点的权：将树中的某些节点赋值上权重，则带权路径长度就等于从根节点出发到达该节点经过的边 \* 该节点的权重
2.  树的带权路径长度：从根节点出发到每一个***叶子节点***的带权路径长度之和成为树的带权路径长度。成为WPL。
3.  哈夫曼树定义：在含有n个带权叶子节点的二叉树中，其中带权路径长度最小的二叉树成为哈夫曼树，也称最优二叉树。

*  如何构造一个哈夫曼树

将最开始n个带权节点找出两个小的，两两结合，新生成的节点的权重继续和剩余的节点进行凉凉结合，直到把所有节点都结合完成。

*  哈夫曼树的性质

1.  n个带权节点构建的哈夫曼树共有 2n-1个节点。
2.  权重大的节点层级低，权重小的节点层级高。
3.  哈夫曼树中，不存在度为1的节点。
4.  哈夫曼树并不唯一。

*  哈夫曼编码

哈夫曼编码解决的是多次出现的某个东西，以最小综合实现数据传输。编码之后如何表示？ 由于是二叉树，往左走记为0，往右走记为1，那么每个节点就可以得到一个唯一的编码，这就是哈夫曼编码。！

[f26c5b5c7a1e46e8b5a91d6d5db4cbc4.png]: https://img-blog.csdnimg.cn/f26c5b5c7a1e46e8b5a91d6d5db4cbc4.png