22计算机408考研—数据结构—树定义，遍历，Huffman，并查集

手把手教学考研大纲范围内树定义，遍历，Huffman，并查集
22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，
如有什么建议或者不足欢迎大佬评论区或者私信指出
初心是用最简单的语言描述数据结构

Talk is cheap. Show me the code.
理论到处都有，代码加例题自己练习才能真的学会

树的基本概念
二叉树的基本操作详细解释（非平衡二叉树）
    二叉树的 插入 删除(图解+例题)
    二叉树的先序，中序，后序遍历（递归）
    二叉树的 先 序遍历(图解+例题)
    二叉树的 中 序遍历(图解+例题)
    二叉树的 后 序遍历(图解+例题)
    二叉树的 层 序遍历(图解+例题)
    二叉树根据前序遍历，中序遍历构建二叉树，并输出后序遍历
    二叉树根据中序遍历，后序遍历构建二叉树，并输出前序遍历
    二叉树的例题
Huffman的基本结构和操作
    Huffman树的初始化
    Huffman编码初始化
并查集
    并查集介绍
    并查集例题
二叉树顺序存储(完整代码)
二叉树链式存储(完整代码)
Huffman树+编码(完整代码)

树的基本概念

我们还记得线性表是 一个结点连着一个结点
树相对于线性表来说是 一个结点连着多个结点

1 结点：树中每一个单元就叫一个结点（例如，R，a，b……）
2 结点的度： 拥有子树的数量，换句话说，一个结点连着几个结点，结点的度就是多少（R连着abc R的度就是3，a连着de a的度就是2）
3 树的度： 树内各个结点的度的最大值（该树的度为3，结点的度最大为3）
4 叶子（终端结点）： 度为0的结点称为叶子或者终端结点（叶子为：jkefgmni）
5 非叶子（非终端结点）： 度不为0的结点。除根结点外，非终端结点也称为内部结点。
6 双亲和孩子（父结点和子结点）： 结点的子树的根称为该结点的孩子，该结点称为孩子的双亲双亲也称为父节点，孩子也称为子结点（abc是R的孩子，R是abc的双亲）
7 兄弟： 同一个双亲（父结点）的孩子之间互称兄弟（ghi互称兄弟）
8 祖先： 从根到该结点所经分支上的所有结点（m的祖先为rch）
9 子孙： 以某结点为根的子树中的任一结点都称为该结点的子孙。（a的子孙为de jk）
10 层次： 根结点为第一层，根结点的孩子为第二层依次向下加……
11 堂兄弟： 双亲在同一层的结点互为堂兄弟。（f的堂兄弟为de ghi）
12 树的深度（高度）： 树中结点的最大层次称为树的深度或高度（图示深度为4）
13 有序树和无序树：将数种结点的各子树看成从左到右有次序的（不能互换），则为有序树，否则为无序树 （有序树中最左边的子树的根称为第一个孩子，最右边称为最后一个孩子）

14 森林： m棵互不相交的树的集合，对于每个根结点来说，子树的集合即为森林

15 度，结点，叶子节点的关系：

例题：在一棵度为4的树中，有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，
则树中叶子结点数为？	

设n为结点数量，n0为入度为0的结点数量，n1为入度为1的结点数量，……na为入度为a的结点数量
m为总入度数量（总度的数量）

n = n0 + n1…… + na
m = 1 * n1 + 2 * n2 + …… + a * na
n = m + 1

三个关系的解释：

每个结点无非就是：    度为0，度为1，……度为a
把这些结点的数量加起来就是总结点数量
 
总入度结点为:			各个度×度的数量
例子：度为3的结点代表他有三个子结点，n3代表度为3的结点的数量，3 * n3 代表度为3的结点一共有多少个子孩子
把每个度都按照这种方式加起来，算出来的称作总度

总度，我们算的是子孩子，这里缺少树中的一个根节点（根结点无法通过父结点的度推出），加上根节点即为总结点的数量

例题解析：

n0为度为0的结点，也称作叶子结点
n = n0 + 10 + 1 + 10 + 20
m = 1 * 10 + 2 * 1 + 3 * 10 + 4 * 20
n = m + 1
带入即可得出结果：82

在链式存储中，n个结点的二叉树有n+1个空指针域

（n个结点一共有2n个指针域，除了根结点，这些指针域都包括剩下的结点，也就是说2n个指针域包含 n-1 个结点，剩下的都为空指针域）

16 满二叉树

​ 满二叉树，顾名思义，二叉树已经满了，最后一层是满的，如果在添加只能是在添加一层

​ 满二叉树看起来像是一个三角形

满二叉树的特性：

​

第一层的结点数量为1，

第二层的数量为2

第三层的数量为4

这里可以看作首项为1,公比是2的等比数列

由此可知：

一个层数为K的满二叉树的结点数量：2的K次方 - 1

一个层数为K的满二叉树的叶子结点数量：2的K-1次方

叶结点只能在最后一层

17 完全二叉树

官方解释：
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

换句话说：和满二叉树一样，但是最后一层可能少几个右边的结点，最后一层如果有结点必须靠左

具有n个结点的完全二叉树的深度：[log2k] + 1（注：[ ]表示向下取整）

对一棵完全二叉树有 n 个结点，对任一结点	i(1≤i≤n)	存在：
	i=1，则 i 为二叉树的根结点,如果 i>1，则父结点为 i/2
	如果 2*i > n ，则 i 结点无左子结点，否则左子结点为 2*i
	如果 2*i+1 > n ，则 i 结点无右子结点，否则右子结点为 2*i+1

完全二叉树 的 叶子结点 在 最下层 和 次下层 ，最下层的叶子结点集中在左边，次下层的叶子结点集中在右边

tips： 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

完全二叉树中  叶子结点，非叶子结点，总结点数的关系：

​	a = 总结点数 / 2 ，b = 总结点数 - a

​	a 和 b 中大的是叶子结点，小的是非叶子结点

​

二叉树的基本操作详细解释

每个结点有两个子结点的树

二叉树的插入

以下代码的插入，进入插入方法，从根结点开始，由用户选择左子树和右子树，一直到空结点的位置，根据提示确定插入

插入代码：

  //插入结点
bool treeInsert(Tree &tree, int data) {
    if (tree == NULL) {     //如果根结点为空，把插入的值插入到根结点
        tree = new TreeNode;    //添加结点，设置左子结点和右子结点为空
        tree->data = data;
        tree->leftchild = NULL;
        tree->rightchild = NULL;
        cout << "根节为点空, 插入成功n";
        return true;
    }
    Tree temp = tree;
    while (temp) {
        cout << "输入 1 选择左子结点,";
        cout << "输入 2 选择右子结点,";
        cout << "输入 3 返回上一结点,输入 其他 退出插入操作n";
        int selected;
        cin >> selected;
        if (selected == 1) {
            if (temp->leftchild == NULL) {  //如果左子结点为空，将插入的值放到左子结点
                temp->leftchild = new TreeNode;
                temp->leftchild->data = data;
                temp->leftchild->leftchild = NULL;
                temp->leftchild->rightchild = NULL;
                cout << "插入成功n";
                return true;
            } else {    //如果左子结点不为空，找到左子结点，继续循环
                temp = temp->leftchild;
            }
        } else if (selected == 2) {
            if (temp->rightchild == NULL) { //右子结点为空，将值插入到右子结点
                temp->rightchild = new TreeNode;
                temp->rightchild->data = data;
                temp->rightchild->leftchild = NULL;
                temp->rightchild->rightchild = NULL;
                cout << "插入成功n";
                return true;
            } else {    //右子结点不为空，指向右子结点
                temp = temp->rightchild;
            }
        } else {    //输入其他，自己退出插入操作
            return false;
        }
    }
}

二叉树的删除

和插入差不多的，从根结点开始，用户选择左子树，右子树，或者删除当初结点
删除当前结点，当前结点的子结点会被全部删除
-
顺序存储的是用BFS方法把子树全部删除
链式存储把删除结点的父结点对当前结点的方向的子树附空

删除代码：

 //删除子树
bool treeDelete(Tree &tree) {
    if (tree == NULL) {     //第一次进来tree为根结点
        cout << "根节点为空,无法删除n";
        return false;
    }
    Tree temp = tree;
    Tree fathertemp;    //记录一下父结点，删除时，把删除结点的父结点的左或者右结点附空
    while (true) {
        if (temp->leftchild != NULL) {  //删除左子结点或者右子结点的时候判断一下是否为空
            cout << "输入 1 选择左子结点,";
        }
        if (temp->rightchild != NULL) {
            cout << "输入 2 选择右子结点,";
        }
        cout << "输入 3 删除此结点,输入 其他 退出删除操作n";
        int selected;
        cin >> selected;
        if (selected == 1 && temp->leftchild != NULL) { //选择左子结点或者右子结点的时候需要判断左子结点或者右子结点是否为空
            fathertemp = temp;  //转向左子结点或者右子结点的时候，记录一下父结点
            temp = temp->leftchild;
        } else if (selected == 2 && temp->leftchild != NULL) {
            fathertemp = temp;
            temp = temp->rightchild;
        } else if (selected == 3) {
            if (fathertemp->leftchild == temp) {    //删除结点如果是父结点的左结点，就把父结点的左结点附空
                fathertemp->leftchild = NULL;
            }
            if (fathertemp->rightchild == temp) {   //右结点同理
                fathertemp->rightchild = NULL;
            }
            Tree t = temp;  //保存一下待删除结点，把待删除结点delete，释放空间
            temp = NULL;//直接指向NULL为什么不能删除？？？？？？？？？？？？

            delete t;
            return true;
        } else {
            return false;   //输入其他，退出删除操作
        }

    }
}

二叉树的先序，中序，后序遍历（递归）

递归就是不断的循环调用自己，换一个参数调用自己

对于这三种遍历，不过是左结点，右结点，根结点的访问顺序不一样，其他的都是一样的

当结点为空时，返回结点，当结点不为空，就找左子树右子树，

先序遍历

   //前序遍历（递归）
void treePreRecursionPrint(Tree tree) { //先输出根结点，在找左结点，在找右结点
    if (tree != NULL) {
        cout << tree->data << " ";
        treePreRecursionPrint(tree->leftchild);
        treePreRecursionPrint(tree->rightchild);
    }
} 

中序遍历

   //中序遍历（递归）
void treeMidRecursionPrint(Tree tree) { //先输出左结点，在输出根结点，输出右结点
    if (tree != NULL) {
        treeMidRecursionPrint(tree->leftchild);
        cout << tree->data << " ";
        treeMidRecursionPrint(tree->rightchild);
    }
}

后序遍历

   //后序遍历（递归）
void treePostRecursionPrint(Tree tree) {    //先输出左子结点，在输出右子结点，输出根结点
    if (tree != NULL) {
        treePostRecursionPrint(tree->leftchild);
        treePostRecursionPrint(tree->rightchild);
        cout << tree->data << " ";
    }
}

二叉树的前（先）序遍历（非递归）

递归方法代码里面有注释
前序遍历：先输出根结点，在输出左结点，在输出右结点
使用栈，栈后进先出，从根结点向下添加，先把下面的输出，然后在一步一步向上走
先把根结点添加，

然后输出结点的值，结点压栈，找此结点的左子树，重复这个操作一直找到左子树为空的时候
然后从栈里弹出结点，此时弹出的结点为上面最后一个左子树为空的结点（栈后进先	出）
使用弹出结点的右结点循环上面的操作，

LeetCode二叉树前（先）序遍历图解：

1 初始状态

2 1入栈并输出，然后找左子结点

3 2入栈并输出，接着找2的左子结点，但是2没有左子结点

4 2没有左子结点，2出栈，找2的右子结点4

5 4入栈并输出，找4的左子结点，左结点不存在

6 4的左子结点不存在，4出栈，然后找4的右子结点，4的右子结点不存在，返回

7 1出栈，找1的右子结点3

8 3入栈并输出，找3的左子结点5

9 5入栈并输出，找5的左子结点，左结点不存在

10 5出栈，找5的右子结点，右结点不存在，返回

11 3出栈，找3的右子结点6

12 6入栈并输出，找6的左子结点，左结点不存在

13 6出栈，找6的右子结点，右子结点不存在，返回

14 完成，栈空

前序遍历代码：

 //前序遍历（非递归）
void treePrePrint(Tree tree) {
    cout << "前序遍历:";
    stack nodes;  //用栈的原因：后进先出，后面进来的结点是下面的，先弹出这个结点，接着找右子结点
    while (tree != NULL || !nodes.empty()) {    //当前结点不为空，或者结点栈不为空，一直循环，说明还有未输出的结点
        while (tree != NULL) {  //只要结点不为空，一直找左子结点
            nodes.push(tree);
            cout << tree->data << " ";  //输出当前结点，前序遍历，先输出根结点
            tree = tree->leftchild; //不断找左子结点
        }
            //上面循环结束，说明tree结点没有左子树
        if (!nodes.empty()) {   //只要结点队列不为空，就弹出一个结点
            tree = nodes.top(); //弹出没有左子树的结点
            nodes.pop();
            tree = tree->rightchild;    //转到这个树的右子结点，继续循环
        }
    }
    cout << "n";
}

前序遍历例题

Talk is cheap, Show me the Code.
用下面的例题，趁热打铁练习一下前序遍历

前序遍历例题链接

二叉树的中序遍历（非递归）

递归方法代码里面有注释
中序遍历和前序遍历是差不多的
中序遍历：先输出左结点，在输出根结点，在输出右结点
使用栈，栈后进先出，从根结点向下添加，先把下面的输出，然后在一步一步向上走
先把根结点添加，

结点压栈，找此结点的左子树，重复这个操作一直找到左子树为空的时候
然后从栈里弹出结点，此时弹出的结点为上面最后一个左子树为空的结点（栈后进先	出），输出此结点
使用弹出结点的右结点循环上面的操作，

LeetCode二叉树中序遍历图解：

1 初始状态

2 1入栈，然后找左子结点2

3 2入栈，然后找左子结点4

4 4入栈然后找左子结点，4没有左子结点

5 4出栈并输出，然后找右子结点，右子结点不存在，返回

6 2出栈并输出，找2的右子结点5

7 5入栈，然后找5的左子结点，左结点不存在

8 5出栈并输出，然后找5的右子结点，右结点不存在，返回

9 1出栈并输出，找1的右子结点3

10 3入栈，找3的左子结点

11 6入栈，找6的左子结点，6的左子结点为空

12 6出栈并输出，找6的右子结点，右子结点为空，返回

13 3出栈并输出，找3的右子结点，右结点为空，返回

14 中序遍历完成

中序遍历代码：

 //中序遍历（非递归）
void treeMidPrint(Tree tree) {  //与前序遍历大概相同，不过是先输出左子结点
    cout << "中序遍历:";
    stack nodes;
    while (tree != NULL || !nodes.empty()) {
        while (tree != NULL) {
            nodes.push(tree);
            tree = tree->leftchild;
        }
        //当左子结点遍历完后，输出根结点，然后再转到右结点
        if (!nodes.empty()) {
            tree = nodes.top();
            nodes.pop();
            cout << tree->data << " ";
            tree = tree->rightchild;
        }
    }
    cout << "n";
}

中序遍历例题

Talk is cheap, Show me the Code.
用下面的例题，趁热打铁练习一下中序遍历

中序遍历例题链接

二叉树的后序遍历（非递归）

递归方法代码里面有注释
后序遍历：先输出左结点，在输出右结点，在输出根结点
因为后序遍历是最后输出根结点，我们按照左结点压栈，左结点可以到底，但是还要先访问右结点，才能输出根结点，
所以要找一个变量存一下右结点是否被访问（换句话说，存一下上次访问的结点），
如果右结点被访问了，此时可以输出根结点

使用栈，栈后进先出，从根结点向下添加，先把下面的输出，然后在一步一步向上走
先把根结点添加，

步骤：
	结点压栈，找此结点的左子树，重复这个操作一直找到左子树为空的时候
	然后从栈里得到栈顶的结点（栈顶未出栈），此时拿到的结点为上面最后一个左子树为空的结点（栈后进先出），
	判断一下右结点是否为空或者  上次被访问的是否为右结点（被访问）
		如果右结点为空或者被访问：左右结点都被访问了，可以输出根结点，把上次访问的结点改为当前根结点，当前根结点被访问了
		如果右结点不为空并且没有被访问：那么把当前结点改为右结点，
	
	使用弹出结点的右结点循环上面的操作，

LeetCode二叉树后序遍历图解：

1 初始状态

2 3入栈，找3的左子结点9

3 9入栈，找9的左子结点，左结点为空

4 取栈顶值9（不出栈），找9的右结点，右结点为空，9的左结点访问过，右结点为空，9出栈并输出，9成为访问过的上一个结点，返回

5 取栈顶值3（不出栈）， 找3的右结点，

6 右结点4不为空，并且未访问，访问右结点4

7 4入栈，找4的左子结点，左子结点5不为空

8 5入栈，找5的左子结点，左结点为空

9 取栈顶值5（不出栈），5的右子结点为空，

10 5的右结点为空，可以输出根结点，5出栈并输出，5变成上一个访问过的结点

11 取栈顶值4（不出栈）, 找4的右子结点7，右结点7存在并且未访问过，转到右结点7

12 4的右结点7存在并且未访问过，转到右结点7

13 7入栈，找7的左子结点，左子结点为空

14 取栈顶值7（不出栈），找7的右子结点，右结点为空

15 7右结点为空，7出栈并输出，7变成上一个被访问的结点

16 取栈顶值4（不出栈），右子结点7存在，并且是上一个被访问过的

17 4的右子结点是上一个被访问的，4出栈并输出，4变成上一个被访问的结点

18 取栈顶值3（未出栈），3的右子结点是上一个被访问的结点，3出栈并输出

19 栈空，后序遍历完成

后序遍历代码：

 //后序遍历（非递归）
void treePostPrint(Tree tree) { //后序遍历与前两种不太一样，需要找一个变量存一下上一个访问的结点
    cout << "后序遍历:";           //因为要把左右结点都循环完才能输出根结点，
    stack nodes;
    Tree lastnode;
    while (tree != NULL || !nodes.empty()) {
        while (tree != NULL) {  //左结点不为空就一直找到底，把结点保存到栈里面
            nodes.push(tree);
            tree = tree->leftchild;
        }
        tree = nodes.top(); //此结点左子结点不存在，拿到这个根结点
        if (tree->rightchild == NULL || lastnode == tree->rightchild) { //看右结点是否存在或者是否被访问（如果右结点被访问了，可以输出根结点了）
            cout << tree->data << " ";  //当前根结点被访问了
            nodes.pop();
            lastnode = tree;    //当前根结点被访问后，记录最后一个访问的结点
            tree = NULL;    //把访问过的结点附空
        } else {            //如果右结点存在并且没有被访问的话，转到右结点，重复循环把右结点都访问完，
                            // 当结点访问后，lastnode记录的就是每次最后一个访问的结点
            tree = tree->rightchild;
        }
    }
    cout << "n";
}

后序遍历例题

Talk is cheap, Show me the Code.
用下面的例题，趁热打铁练习一下后序遍历

后序遍历例题链接

二叉树的层序遍历（非递归，类似BFS）

简单来说：给二叉树分层，一层一层的输出，输出完本层就从下一层的左边开始输出

把结点存到队列，循环队列
循环到此结点的时候，输出此结点的值，然后把此结点的左右子结点添加到队列

层序遍历的过程：

层序遍历的结果：

层序遍历为什么要用BFS，（BFS与DFS的区别）

层序遍历代码：

  //层序遍历（非递归）
void treeFloorPrint(Tree tree) {
    cout << "层序遍历:";
    queue q;  //使用队列存结点，同一层的在一块挨着，循环同一层的时候，末尾添加的是下一层的左右子结点
    q.push(tree);   //根结点插入队列
    while (!q.empty()) {    //结点队列不对空，一直循环
        Tree temp = q.front();  //保存队列头结点
        q.pop();
        cout << temp->data << " ";  //输出头结点
        if (temp->leftchild != NULL) {  //左子结点或者右子结点存在，把子结点放入队列
            q.push(temp->leftchild);
        }
        if (temp->rightchild != NULL) {
            q.push(temp->rightchild);
        }
    }
    cout << "n";
}

层序遍历例题

Talk is cheap, Show me the Code.
用下面的例题，趁热打铁练习一下层序遍历

层序遍历例题链接

二叉树根据前序遍历，中序遍历构建二叉树，并输出后序遍历

​ 前序遍历：相对子树的根结点在相对左右子结点靠前的位置，相对根结点都靠前

​ 中序遍历：相对根结点的位置，左面是当前根结点左子树的结点，右面是当前根结点的右子树的结点

​

思路：

​ 从前序遍历前面找到根结点，

​ 在中序遍历找到根结点，根结点左面就是根结点左子树的结点，右面就是根结点右子树的结点

​ 然后继续在前序遍历找下一个根结点（左子树的根结点），在上面的左子树的结点中找左子树的根结点，

​ 继续这种循环，直到左子树的结点为空，返回上一层

​ 如果上面左子树不存在，那么左子树的结点也是不存在的，直接返回上一层了

​

​ 右子树也是，在前序遍历找下一个根结点（刚才的左结点都找完了现在才会是右结点），在上面右子树结点找右子树的根结点

​ 继续循环

思路简化：

前序遍历是前面的都是根结点，前序遍历是根结点的顺序排列

根据前序遍历的根结点，在中序遍历找到根结点位置，

中序遍历中：根结点左面是根结点的左子树的结点，根结点的右面是根结点的右子树的结点

继续找下一个根结点，在左子树结点里找新的根结点，
（如果左子树结点不存在，那么新的根结点就是原根的右结点，就是在右子树结点里找新的根结点）		
	
如果左子树结点或者右子树结点不存在返回上一级

不断循环这个过程

思路图解：

例子：	
		  1
	    /   
	   2     3
	  /    /  
	 4   5 6   7
	 
前序遍历的结果是: [1,2,4,5,3,6,7]
中序遍历的结果是: [4,2,5,1,6,3,7]

先从前序遍历中找到根结点，在中序遍历找到根结点，

根结点左面是左子树结点，根结点右面是右子树结点

然后不断的循环这个操作，在先序遍历中找下一个根结点……

思路动图：

代码+注释

​

//根据前序遍历和中序遍历构建二叉树，求出后序遍历
#include "iostream"
#include "math.h"
#include "queue"
#define MAXSize 100

using namespace std;

int pre[MAXSize];
int mid[MAXSize];

typedef struct TreeNode{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode, *Tree;
    //创建二叉树                    （！！！范围包括起始点不包括终止点，含左不含右！！！）
Tree createTree(int preStart, int preEnd, int midStart, int midEnd) {//前序队列从preStart到preEnd 对应着 中序遍历midStart到midEnd
    if (preStart >= preEnd || midStart >= midEnd) { //如果起始位置大于等于终止位置，则不存在当前点（前序遍历和中序遍历都一样）
        return NULL;
    }
    Tree root = new TreeNode;   //创建当前结点，preStart为根结点（前序遍历就是先访问根结点）
    root->data = pre[preStart];
    int i;
    for (i = midStart; i < midEnd; ++i) {   //在中序遍历中找当前结点的根结点
        if (mid[i] == pre[preStart]) {
            break;
        }
    }
        // i 是当前根结点在中序遍历的下标，   i以左就是根的左子树的结点，i以右就是根的右子树的结点
        // i-midStart 就是 当前根的左子树的结点数量
        //当前树的结点范围：根结点+左子树结点+右子树结点      分左子树和右子树一定要记得这个关系！！！

        //左子树的前序遍历的范围：当前前序遍历的 起始点+1 开始向后找 i-midStart个值
            // （左子点的范围就是，起始点+1 向后找左子点数量个数）
                //  起始点+1 开始是因为当前根结点就是起始点，已经用到了
        //左子树的中序遍历范围： midStart 到 i
            //（中序遍历的起始点 到 根结点的位置）
    root->left = createTree(preStart + 1,preStart + 1 + i - midStart,   midStart, i);
        //右子树的前序遍历范围：从左子树前序范围终止点 到 当前树的前序范围终止点
            //（根据前序遍历的特点（根结点在第一位），当前树子结点范围，除去左子树结点范围，剩下的就是右子树的结点范围）
        //右子树的中序遍历范围： i+1 到 当前树中序遍历的终止点
            //（i为根结点，i以右是右子树的结点，一直到中序遍历的终止点）
    root->right = createTree(preStart + 1 + i - midStart,preEnd,    i + 1, midEnd);
    return root;
}

    //后序遍历
void preOrderPrintTree (Tree tree) {
    if (tree == NULL) return;
    preOrderPrintTree(tree->left);
    preOrderPrintTree(tree->right);
    cout << tree->data << " ";
}

//返回二叉树的深度(递归)
int Depth (Tree tree) {
    if (tree == NULL) {
        return 0;
    }
    return max(Depth(tree->left), Depth(tree->right)) + 1;    //找左或右结点的最大深度 + 1（加一是加上当前这一层）
    //不断循环这种操作
}

//格式化输出二叉树(直接看顺序存储的注释就可以,格式化输出就是找二叉树的规律)
//	顺序存储的注释：    https://blog.csdn.net/weixin_46285416/article/details/120931768#t14
void treePrint(Tree tree) { //与顺序打印二叉树基本相似(如果结点为空的时候,要创建一个0结点，给0结点的左右结点都附空)
    cout << "打印二叉树:n";
    int depth = Depth(tree);
    queue q;
    q.push(tree);
    for (int i = 0; i < depth; i++) {
        int space = 0;
        for (int j = 0; j < depth - 1 - i; j++) {
            space = space * 2 + 1;
        }
        for (int j = 0; j < space; j++) {
            cout << " ";
        }
        for (int j = 0; j < pow(2, i); j++) {
            cout << q.front()->data;
            if (q.front()->left != NULL) {
                q.push(q.front()->left);
            } else {
                TreeNode *t = new TreeNode;
                t->data = 0;
                t->left = NULL;
                t->right = NULL;
                q.push(t);
            }
            if (q.front()->right != NULL) {
                q.push(q.front()->right);
            } else {
                TreeNode *t = new TreeNode;
                t->data = 0;
                t->left = NULL;
                t->right = NULL;
                q.push(t);
            }
            q.pop();

            for (int k = 0; k < space * 2 + 1; k++) {
                cout << " ";
            }
        }
        cout << "n";
    }
    cout << "n";
}

int main() {
    cout << "请输入树的结点数量" << endl;
    int n;
    cin >> n;
    cout << "请输入前序遍历的结果" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> pre[i];
    }
    cout << "请输入中序遍历的结果" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> mid[i];
    }
    Tree tree = createTree(0,n, 0, n);
    treePrint(tree);
    cout << "后序遍历：";
    preOrderPrintTree(tree);
    return 0;
}

输入样例：

7
1 2 4 5 3 6 7 
4 2 5 1 6 3 7

LeetCode例题：105. 从前序与中序遍历序列构造二叉树

题目链接

二叉树根据中序遍历，后序遍历构建二叉树，并输出前序遍历

​ 中序遍历：相对根结点的位置，左面是当前根结点左子树的结点，右面是当前根结点的右子树的结点

​ 后序遍历：相对子树的根结点在相对左右子结点靠后的位置，相对根结点都靠后

​

思路：

​ 从后序遍历后面找到根结点，

​ 在中序遍历找到根结点，根结点左面就是根结点左子树的结点，右面就是根结点右子树的结点

​ 然后继续在后序遍历找下一个根结点（右子树的根结点），在上面的右子树的结点中找右子树的根结点，

​ 继续这种循环，直到右子树的结点为空，返回上一层

​ 如果上面右子树不存在，那么右子树的结点也是不存在的，直接返回上一层了

​

​ 左子树也是，在后序遍历找上一个根结点（刚才的右结点都找完了现在才会是左结点），在上面左子树结点找左子树的根结点

​ 继续循环

思路简化：

后序遍历是后面的都是根结点，后序遍历是根结点的从后向前排序

根据后序遍历的根结点，在中序遍历找到根结点位置，

中序遍历中：根结点左面是根结点的左子树的结点，根结点的右面是根结点的右子树的结点

继续找下一个根结点，在右子树结点里找新的根结点，
（如果右子树结点不存在，那么新的根结点就是原根的左结点，就是在左子树结点里找新的根结点）		
	
如果右子树结点或者左子树结点不存在返回上一级

不断循环这个过程

思路图解：

例子：	
    3
   / 
  9  20
    /  
   15   7
	 
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

1、初始状态：

2、先从后序遍历中找到根结点，在中序遍历找到根结点，

3、中序遍历中根结点右面是右子树结点

4、中序遍历中根结点右面是右子树结点

5、中序遍历中根结点左面是左子树结点

6、当前根结点的左子树右子树都遍历完了，返回上一层，遍历上一层的左子树结点

7、构建完成

代码+注释

​

 //根据前序遍历和中序遍历构建二叉树，求出后序遍历
#include "iostream"
#include "math.h"
#include "queue"
#define MAXSize 100

using namespace std;

int mid[MAXSize];
int post[MAXSize];

typedef struct TreeNode{    //树的结构体
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode, *Tree;
//创建二叉树                     //中序遍历的范围midStart-midEnd       后序遍历的范围postStrat - postEnd
Tree createTree(int midStart, int midEnd, int postStart, int postEnd) { //范围都是包括左边不包括右边（包括起始点不包括终止点）
    if (postStart >= postEnd || midStart >= midEnd) {   //起始点大于等于终止点，范围即为空，返回空
        return NULL;
    }
    Tree root = new TreeNode;
    root->data = post[postEnd - 1]; //后序遍历最后一个就是根结点（后序遍历，遍历顺序为：左结点，右结点，根结点）
    int i;
    for (i = midStart; i < midEnd; ++i) {   //在中序遍历中找到根结点下标 i
        if (mid[i] == post[postEnd - 1]) {      //i左边范围就是左子树结点，i右面范围就是右子树结点
            break;                                  //（中序遍历的顺序：左子树，根结点，右子树）  （根结点以左就是左子树结点，以右就是右子树结点）
        }
    }
        //后序遍历 要先找右子结点（后序遍历中，根结点前面是右子树，所以先找右子结点）
            //中序遍历中右子树的范围：根结点在中序遍历的位置以右，到这段中序范围的结束
            //后序遍历中右子树的范围：根结点在后序遍历中是最后一位，所以右子树后序遍历的结束范围是到当前后序范围终止点的前一位
                               //根结点的起始点是 终止点向前走  右子树数量个位置   （midEnd - i - 1）
                                    //midend - i 是中序遍历中根结点到末尾的数量（范围不包括末尾）   -1 是因为右子树不能包括根结点，要把根结点删除
                                    	//也可以理解为，右子树结点的数量为midEnd-(i+1)  后序列遍历的范围是postEnd - 1  向前走右子树结点的数量位
    root->right = createTree(i + 1, midEnd, postEnd - 1 - (midEnd - i - 1) , postEnd - 1);
            //中序遍历中左子树的范围：中序遍历开始位置 到 根结点位置 i （不包括根结点）
            //后序遍历中左子树的范围： 后序遍历起始位置 到 右子树以前    都是左子树的结点范围
    root->left = createTree(midStart, i,postStart , postEnd - 1 - (midEnd - i - 1) );
    return root;
}

//后序遍历
void preOrderPrintTree (Tree tree) {
    if (tree == NULL) return;
    cout << tree->data << " ";
    preOrderPrintTree(tree->left);
    preOrderPrintTree(tree->right);
}

//返回二叉树的深度(递归)
int Depth (Tree tree) {
    if (tree == NULL) {
        return 0;
    }
    return max(Depth(tree->left), Depth(tree->right)) + 1;    //找左或右结点的最大深度 + 1（加一是加上当前这一层）
    //不断循环这种操作
}

//格式化输出二叉树(直接看顺序存储的注释就可以,格式化输出就是找二叉树的规律)
void treePrint(Tree tree) { //与顺序打印二叉树基本相似(如果结点为空的时候,要创建一个0结点，给0结点的左右结点都附空)
    cout << "打印二叉树:n";
    int depth = Depth(tree);
    queue q;
    q.push(tree);
    for (int i = 0; i < depth; i++) {
        int space = 0;
        for (int j = 0; j < depth - 1 - i; j++) {
            space = space * 2 + 1;
        }
        for (int j = 0; j < space; j++) {
            cout << " ";
        }
        for (int j = 0; j < pow(2, i); j++) {
            cout << q.front()->data;
            if (q.front()->left != NULL) {
                q.push(q.front()->left);
            } else {
                TreeNode *t = new TreeNode;
                t->data = 0;
                t->left = NULL;
                t->right = NULL;
                q.push(t);
            }
            if (q.front()->right != NULL) {
                q.push(q.front()->right);
            } else {
                TreeNode *t = new TreeNode;
                t->data = 0;
                t->left = NULL;
                t->right = NULL;
                q.push(t);
            }
            q.pop();

            for (int k = 0; k < space * 2 + 1; k++) {
                cout << " ";
            }
        }
        cout << "n";
    }
    cout << "n";
}

int main() {
    cout << "请输入树的结点数量" << endl;
    int n;
    cin >> n;

    cout << "请输入中序遍历的结果" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> mid[i];
    }
    cout << "请输入后序遍历的结果" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> post[i];
    }
    Tree tree = createTree(0,n, 0, n);
    treePrint(tree);
    cout << "后序遍历：";
    preOrderPrintTree(tree);
    return 0;
}

输入样例：

5
9 3 15 20 7
9 15 7 20 3

LeetCode例题：106. 从中序与后序遍历序列构造二叉树

题目链接

二叉树的例题

//根据前序遍历和中序遍历构建二叉树，求出后序遍历
#include "iostream"
#include "math.h"
#include "queue"
#define MAXSize 100

using namespace std;

int mid[MAXSize];
int post[MAXSize];

typedef struct TreeNode{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode, *Tree;
//创建二叉树                     //中序遍历的范围midStart-midEnd       后序遍历的范围postStrat - postEnd
Tree createTree(int midStart, int midEnd, int postStart, int postEnd) { //范围都是包括左边不包括右边（包括起始点不包括终止点）
    if (postStart >= postEnd || midStart >= midEnd) {   //起始点大于等于终止点，范围即为空，返回空
        return NULL;
    }
    Tree root = new TreeNode;
    root->data = post[postEnd - 1]; //后序遍历最后一个就是根结点（后序遍历，遍历顺序为：左结点，右结点，根结点）
    int i;
    for (i = midStart; i < midEnd; ++i) {   //在中序遍历中找到根结点下标 i
        if (mid[i] == post[postEnd - 1]) {      //i左边范围就是左子树结点，i右面范围就是右子树结点
            break;                                  //（中序遍历的顺序：左子树，根结点，右子树）  （根结点以左就是左子树结点，以右就是右子树结点）
        }
    }
    //后序遍历 要先找右子结点（后序遍历中，根结点前面是右子树，所以先找右子结点）
        //中序遍历中右子树的范围：根结点在中序遍历的位置以右，到这段中序范围的结束
        //后序遍历中右子树的范围：根结点在后序遍历中是最后一位，所以右子树后序遍历的结束范围是到当前后序范围终止点的前一位
            //根结点的起始点是 终止点向前走  右子树数量个位置   （midEnd - i - 1）
                //midend - i 是中序遍历中根结点到末尾的数量（范围不包括末尾）   -1 是因为右子树不能包括根结点，要把根结点删除
                //也可以理解为，右子树结点的数量为midEnd-(i+1)  后序列遍历的范围是postEnd - 1  向前走右子树结点的数量位
    root->right = createTree(i + 1, midEnd, postEnd - 1 - (midEnd - i - 1) , postEnd - 1);
    //中序遍历中左子树的范围：中序遍历开始位置 到 根结点位置 i （不包括根结点）
    //后序遍历中左子树的范围： 后序遍历起始位置 到 右子树以前    都是左子树的结点范围
    root->left = createTree(midStart, i,postStart , postEnd - 1 - (midEnd - i - 1) );
    return root;
}

//后序遍历
void postOrderPrintTree (Tree tree) {
    if (tree == NULL) return;
    cout << " " << tree->data;
    postOrderPrintTree(tree->left);
    postOrderPrintTree(tree->right);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> post[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> mid[i];
    }

    Tree tree = createTree(0,n, 0, n);
    cout << "Preorder:";
    postOrderPrintTree(tree);
    return 0;
}

//根据前序遍历和中序遍历构建二叉树，求出后序遍历
#include "iostream"
#include "math.h"
#include "queue"

#define MAXSize 100

using namespace std;

int mid[MAXSize];
int post[MAXSize];

typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode, *Tree;
int index = 0;
string str;
//  ABC##DE#G##F###
//创建二叉树
Tree createTree() { //先序遍历，
    Tree root = new TreeNode;
    if (str[index] == '#') {    //遇到# 就是空结点
        root->data = NULL;
        return root;
    } else {
        root->data = str[index];
    }
    index++;            // 下标+1,就是左子结点，
    root->left = createTree();
    index++;            //下标+1,就是右子结点
    root->right = createTree();

    return root;
}

//后序遍历
void preOrderPrintTree(Tree tree) {
    if (tree->data == NULL) return;
    preOrderPrintTree(tree->left);
    cout << tree->data;
    preOrderPrintTree(tree->right);
}


int main() {
    cin >> str; //string str;定义在上面  19行
    Tree tree = createTree();
    preOrderPrintTree(tree);
    return 0;
}



	

//根据前序遍历和中序遍历构建二叉树，求出后序遍历
#include "iostream"
#include "math.h"
#include "queue"

#define MAXSize 100

using namespace std;

int mid[MAXSize];
int post[MAXSize];

typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode, *Tree;
int index = 0;
string str;
//  ABC##DE#G##F###
//创建二叉树
Tree createTree() {

    Tree root = new TreeNode;
    if (str[index] == '#') {
        root->data = NULL;
        return root;
    } else {
        root->data = str[index];
    }
    index++;
    root->left = createTree();
    index++;
    root->right = createTree();

    return root;
}

//后序遍历
void preOrderPrintTree(Tree tree) {
    if (tree->data == NULL) return;
    preOrderPrintTree(tree->left);
    cout << tree->data << " ";
    preOrderPrintTree(tree->right);
}

int main() {
    while (cin >> str) {    //不输入后，cin返回0
        index = 0;
        Tree tree = createTree();
        preOrderPrintTree(tree);
        cout << "n";
    }
    return 0;
}
	

Huffman的基本结构和操作

先看下Huffman树的结构图：

Huffman树相对于二叉树每个结点多一个`字符`和一个`权重`
权重越大的，越靠近子结点
右面是Huffman树的编码，其实就是结点相对Huffman树根结点的路径（0是选择左结点，1是选择右结点）

Huffman树的特点

没有度为1的结点（每个结点没有子结点，或者有两个子结点，不存在有一个子结点的）
n个叶子结点的哈夫曼树总共有2n-1个结点（Huffman树只有叶子结点才是真的结点，其他结点都是合成结点）

typedef struct TreeNode {   //定义Huffman树结构体：字符，权重，huffman编码，左子结点，右子结点
    char c;
    int weight;
    char huffman_code[100];
    struct TreeNode *lefttree;
    struct TreeNode *righttree;
}TreeNode, *Tree;

struct cmp{ //定义树结点排序规则，按权重从小到大排序
    bool operator()(Tree a, Tree b) {
        return a->weight > b->weight;
    }
};

//huffman树的初始化
void huffmanTreeInit(Tree &tree,unordered_map words);

 //huffman编码生成         
void huffmanCodeInit(Tree &tree);

//打印huffman编码
void huffmanCodePrint(Tree tree);

 //得到当前huffman树的深度
int getDepth(Tree tree);

//格式化打印huffman树     
void huffmanTreeTypePrint(Tree tree);

Huffman树的初始化

每次都把最小的两个结点合成一个结点，新结点的权值为两个子结点的权值的和，然后把新结点放回原来的地方

我们可以利用层序遍历的方法，把每个结点都放入队列，每次合成取权值最低的两个结点合成，把合成的新结点重新放回队列。
（取最小的两个结点，可以用优先队列，或者每次操作给队列排序，找权值最小的两个结点）

huffman树初始化（代码）

 //huffman树的初始化
void huffmanTreeInit(Tree &tree,unordered_map words) {   //用unordered_map保存每个字符出现的次数
                                    //map和unordered_map差不多的，map是顺序的，unordered_map是按照hash顺序的
                        //！！！优先队列，符合排序的顺序，但是调试的时候里面的顺序不是排序的，弹出的时候是按照排序后的顺序弹出的
                        //！！！优先队列，底层为堆排序，是存储找vector或deque里面，所以调试的时候看到的不是排好序的
    priority_queue,cmp> nodes;
    unordered_map :: iterator words_it;  //创建一个unordered_map的迭代器
    for (words_it = words.begin(); words_it != words.end(); words_it++) {   //循环map里面的内容
        Tree temp = new TreeNode;     //创建树结点，map保存的字符和数量，赋值给树结点
        temp->c = words_it->first;
        temp->weight = words_it->second;
        temp->lefttree = NULL;       //左右子结点赋空值
        temp->righttree = NULL;
        nodes.push(temp);       //把创建的树结点保存到优先队列里
    }
                    //优先队列保证队列内得到元素都是按照自定义的排序规则排序的
    while (!nodes.empty()) {    //只要优先队列不为空，证明还有结点未访问
        if (nodes.size() == 1) {    //当剩下一个结点的时候，无需在合并，把这个结点给tree，从队列弹出结点
            tree = nodes.top();
            nodes.pop();
        } else {
            Tree temp1 = nodes.top();   //取出权重小的两个结点
            nodes.pop();
            Tree temp2 = nodes.top();
            nodes.pop();

            Tree newtemp = new TreeNode;    //把两个权重小的结点合成一个结点
            newtemp->weight = temp1->weight + temp2->weight;
            if (temp1->weight < temp2->weight) {    //权重小的放到左子结点
                newtemp->lefttree = temp1;
                newtemp->righttree = temp2;
            } else {
                newtemp->lefttree = temp2;
                newtemp->righttree = temp1;
            }
            newtemp->c = '0';   //非叶子结点字符赋 0
            nodes.push(newtemp);    //把新结点入优先队列
        }
    }

}

Huffman编码初始化

Huffman的编码每个结点是相对于根结点的路径（0代表左结点，1代表右结点）

比如说：A：0110   根结点 ->左结点权重:42 -> 右结点权重:19 -> 右结点权重:8 -> 左结点权重:5,结点A

层序遍历（0代表左结点，1代表右结点）
每层的左子结点为：父结点+0
每层的右子结点为：父结点+1

huffman编码初始化（代码）

 //huffman编码生成           0代表左子结点，1代表右子结点
void huffmanCodeInit(Tree &tree) {  //用层序遍历，每一层huffman编码多一位
    Tree temp = tree;
    queue nodes;
    nodes.push(temp);
    while (!nodes.empty()) {
        temp = nodes.front();   //访问到当前结点，把当前结点从队列弹出
        nodes.pop();
        if (temp->lefttree != NULL) {   //左子结点不为空，就把左子结点放入优先队列，
            nodes.push(temp->lefttree);
            strcpy(temp->lefttree->huffman_code, temp->huffman_code);   //左结点huffman编码=父结点huffman编码 + 0
            char *str = temp->lefttree->huffman_code;
            while (*str != '') {
                *str++;
            }
            *str = '0';
        }
        if (temp->righttree != NULL) {  //与左子结点同理
            nodes.push(temp->righttree);
            strcpy(temp->righttree->huffman_code, temp->huffman_code);
            char *str = temp->righttree->huffman_code;
            while (*str != '') {
                *str++;
            }
            *str = '1';
        }
    }
}

并查集 并查集介绍

一、概念及其介绍
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

并查集的思想是：用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。

二、适用说明
并查集用在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂，但数据量极大，若用其他的数据结构来描述的话，往往在空间上过大，计算机无法承受，也无法在短时间内计算出结果，所以只能用并查集来处理。

三、并查集的基本数据表示

如上图 0-4 下面都是 0，5-9 下面都是 1，
表示 0、1、2、3、4 这五个元素是相连接的，5、6、7、8、9 这五个元素是相连的。

再如上图 0、2、4、6、8 下面都是 0 这个集合，表示 0、2、4、6、8 这五个元素是相连接的
1、3、5、7、9 下面都是 1 这个集合，表示 0，1、3、5、7、9 这五个元素是相连的。

Talk is cheap, Show me the Code.
用下面的例题，趁热打铁练习一下层序遍历

并查集例题

题目链接（洛谷：P1551 亲戚）

思路：
因为并查集是根据森林处理问题
每个集合就是一个森林，此题把两个集合合起来，
换句话说把每个森林的头结连起来，把一个森林的头结点添加到另一个森林头结点的子结点（把两个森林合起来）

#include "iostream"

using namespace std;

int f[10001];

    //找a结点的祖先
int getfather(int a) {
    if (f[a] == a) {    //如果a的父亲是自己，证明a的祖先就是a，返回a
        return a;
    } else {    //如果a的父亲不是自己
                //就把a的父亲的父亲求出来赋值给a的父亲，f[a]将变成a的爷爷
    // 不断重复调用并赋值给f[a]，f[a]将快要变成a的祖先(f[a]不一定是祖先，但是接近祖先)
        return f[a] = getfather(f[a]);
    }
}

    //把 a 与 b 联系起来
void hb(int a, int b) { //a的祖先的父亲变成b的祖先（把两个森林(集合)联系起来）
    f[getfather(a)] = getfather(b);
}

int main() {
    int n, m, p, a, b;
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++) {
        f[i] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        hb(a, b);   //合并 a 和 b
    }
    for (int i = 0; i < p; i++) {
        cin >> a >> b;
        if (getfather(a) == getfather(b)) { // 看 a b 的祖先是否相等
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

二叉树顺序存储

//二叉树的顺序存储(类似于完全二叉树)
//其实就是数组  建议看看堆排序
#include "iostream" 
#include "queue"
#include "stack"
#include "cmath"
#include  

#define MAXSIZE 1000

using namespace std;
//顺序存储的二叉树本身就是一个数组



int tree[MAXSIZE] = {0};    //二叉树数组
bool isbool[MAXSIZE] = {0}; //判断当前结点是否有数据 
queue prqueue; //保存各个结点的下标  （下标队列） 
int length = 0; //当前二叉树存在元素的长度
int depth = 0;  //表示当前二叉树的深度

//此方法为，一层一层向下选择位置，找到位置后插入
bool treeInsert(int data) { //二叉树插入数据
    int index = 0;
    int tempdeep = 0;   //二叉树深度的临时变量， 插入结点的时候检测深度有没有变化
    while (index < MAXSIZE) {   //判断index是否超过二叉树的容量了，（顺序存储本身是一个数组，方式下标超过数组长度发生异常）

        if (!isbool[index]) {   //如果当前结点不存在可以插入到当前结点
            cout << "此节点为空，输入 1 (或者其他) 确认插入，输入 -2 返回上一结点，输入 -1 退出n";
            int temp;
            cin >> temp;    //输入上面描述的操作数
            if (temp == -2) {   //输入 -2 返回上一结点
                if (index == 0) {   //根节点无法返回上一结点
                    return false;
                }
                index = (index - 1) / 2;    //完全二叉树特点，当前结点的父节点的关系
                tempdeep--; //临时深度-1 向上走了一层
                continue;
            } else if (temp == -1) {    //输入 -1 退出，不插入数据
                return false;
            } else {    //输入其他确定插入
                tree[index] = data; //把传进来的值插入二叉树的当前结点
                isbool[index] = true;   //记录当前结点有值
                length++;   //二叉树结点+1
                tempdeep++; //临时深度+1
                depth = max(depth, tempdeep);   //看此次插入数据的深度是否比以往的深度要深
                prqueue.push(index);    //把当前点对应的下标放到队列中 
                return true;
            }
        }
    //当前结点不为空（当前结点不能插入），选择左子树或右子树
        int leftNode = index * 2 + 1, rightNode = index * 2 + 2;    //左右子树的规律根据完全二叉树来的
//        if (isbool[leftNode]) {
            cout << "输入 1 选择左子树";
//        }
//        if (isbool[rightNode]) {
            cout << "输入 2 选择右子树";
//        }
        if (index != 0) {
            cout << "输入 3 返回上一结点";
        }
        cout << "输入 -1(或其他) 退出插入操作n";
        int selected;
        cin >> selected;    //输入操作
        if (selected == 1) {    //选择左子结点
            index = leftNode;
            tempdeep++;
        } else if (selected == 2) { //选择柚子结点
            index = rightNode;
            tempdeep++;
        } else if (selected == 3) {
            if (index == 0) {   //头结点不能返回上一结点
                return false;
            }
            index = (index - 1) / 2;    //返回父节点
            tempdeep--;
        } else {
            return false;
        }
    }
}

bool treeDelete() {     //删除结点
    int index = 0;  //当前结点下标
    while (index < MAXSIZE) {   //防止结点下标越界
        if (!isbool[index]) {   //当前结点为空
            cout << "当前节点为空，不能删除，返回上一结点n";
            if (index == 0) {   //如果是根节点为空，无法返回上一结点
                return false;
            }
            index = (index - 1) / 2;    //返回上一结点
        }
        int leftNode = index * 2 + 1, rightNode = index * 2 + 2;    //父节点与子结点的关系
        if (isbool[leftNode]) { //先判断是否存在左子树存在，才能提示
            cout << "输入 1 选择左子树";
        }
        if (isbool[rightNode]) {    //先判断是否存在右子树存在，才能提示
            cout << "输入 2 选择右子树 ";
        }
        if (index != 0) {   //不是父结点就能返回上一结点
            cout << "输入 3 返回上一结点 ";
        }
        cout << "输入 4 删除当前结点 输入 -1(或其他) 退出删除操作n";
        int selected;
        cin >> selected;
        if (selected == 1 && isbool[leftNode]) {    //选择左子树要判断左子树是否为空
            index = leftNode;
        } else if (selected == 2 && isbool[rightNode]) {    //右子树同理
            index = rightNode;
        } else if (selected == 3) {
            if (index == 0) {   //头结点不能返回上一结点
                return false;
            }
            index = (index - 1) / 2;    //子结点与父节点的关系
        } else if (selected == 4) { //删除当前结点
            break;
        } else {    //输入 其他 退出删除
            return false;
        }

    }

    //删除结点采用BFS方法   （主要是如果删除某个结点要把他的子树都删除）
    queue q;   //q（删除队列） 中存放要删除的结点
    q.push(index);  //把当前结点添加到删除队列
    int i = 0;
    while (!q.empty()) {
        index = q.front();  //拿到第一位删除元素的下标
        q.pop();    //把当前元素从队列弹出（上面已经拿到了此元素）
        int leftNode = index * 2 + 1, rightNode = index * 2 + 2;    //找到当前删除结点的  左子结点 和 右子结点
        if (isbool[index]) {    //如果存在当前结点才能删除
            isbool[index] = false;  //清除当前结点的存在状态
            tree[index] = 0;    //当前结点值清为0
            int size = prqueue.size();  //获取 删除队列 的大小
            for (int j = 0; j < size; j++) {    //从 删除队列 中删除当前结点
                if (prqueue.front() != index) {  //如果 删除队列的头结点 不是当前结点
                    prqueue.push(prqueue.front());  //把队列的头结点在插入到 删除队列中（头结点存在，队列后面又插入一遍）
                }
                prqueue.pop();  //把队列头结点弹出（删除）  ，如果头结点是当前结点那么上面就不会把头结点在插入到删除队列一遍
            }
            length--;   //二叉树元素数量-1
            if (isbool[leftNode]) { //如果存在左子结点 就把左子结点添加到删除队列
                q.push(leftNode);
            }
            if (isbool[rightNode]) {    //右节点也同理
                q.push(rightNode);
            }
        }
    }
    if (prqueue.empty()) {  //如果 二叉树存下标的队列  为空，深度为0
        depth = 0;
        return true;
    }

    int maxindex = -1; //找到除了删除的结点外最大的结点的位置

    int size = prqueue.size();  //获得 二叉树存下标的队列的大小
    for (int j = 0; j < size; j++) {    //循环此队列，找到最大的下标
        if (prqueue.front() != index) {
            maxindex = max(prqueue.front(), maxindex);
            prqueue.push(prqueue.front());
        }
        prqueue.pop();
    }
    //删除节点后,取位置的最大结点,重构深度
    int sum = 1;
    int start = 1;
    int tempdeep = 1;
    //根据完全二叉树的规律，重构当前二叉树的深度
    //数量从1开始，下标从0开始，  判断的时候需要数量-1 < maxindex
    while (sum - 1 < maxindex) {    //一层一层的加，如果小于最大的下标就一直向下层加，一直加到>=maxindex 能放下当前二叉树
        start *= 2;     //start为每一层的数量
        sum += start;   //sum为数量总和
        tempdeep++;
    }
    depth = tempdeep;   //重新赋值深度

}

void treePrint() {
    cout << "打印二叉树n";
    int index = 0; 
                                             //二叉树空格多找一找规律就能得出
    for (int i = 0; i < depth; i++) {
                                            //每一层前面的空格从上到下的规律是15 7 3 1 0
                                            //不难发现规律就是 本层空格 就是 下层空格*2+1    底层一定是0个
        int space = 0;
                                            //depth是二叉树深度，也就是最底层是多少
        for (int j = 0; j < (depth - i - 1); j++) { //底层循环0次，倒数第二层循环1次，层数靠上循环次数越多
            space = space * 2 + 1;
        }
        for (int j = 0; j < space; j++) {   //输出空格，输出space个
            cout << " ";
        }
        for (int j = 0; j < pow(2,i); j++) { 
                cout << tree[index++]; 
            for (int k = 0; k     //字符和字符的空格数量为  2*space+1
                cout << " ";
            }
        }
        cout << "n";
    }
}


void treeClear() {  //清除二叉树
    int size = prqueue.size();
    for (int i = 0; i < size; i++) {    //循环下标队列中的每一个结点下标
        int index = prqueue.front();
        tree[index] = 0;    //把二叉树当前结点的值清0
        isbool[index] = false;  //二叉树当前结点状态为false
        prqueue.pop();  //清除完当前结点，从下标队列删除头结点
    }
    depth = 0;  //二叉树深度为0
}

int treeDepth() {   //返回二叉树的深度
    return depth;
}

//先序遍历：先输出根结点，在输出左子结点，在输出右子结点
void treePreorderRecursionPrint(int index) {    //先序遍历（递归）
    if (isbool[index]) {    //判断当前结点是否为空
        cout << tree[index] << " ";     //先输出结点，先找到的结点为根结点
        treePreorderRecursionPrint(index * 2 + 1);  //然后找左子结点
        treePreorderRecursionPrint(index * 2 + 2);  //找右子结点
    }
}

void treePreorderPrint() {  //先序遍历（非递归）
    cout << "先序遍历：n";
    stack nodes;   //存放结点的栈，因为先序就是输出根节点，然后先找左下结点，在找右下结点
    int index = 0;      //从根结点压栈，一直到下面，出栈的时候是从下面到上面出栈

    while (isbool[index] || !nodes.empty()) {   //只要栈内还有结点或者当前结点不为空就要继续遍历
        while (isbool[index]) {     //当前结点不为空就输出当前结点，然后把当前结点压栈，指向左子结点
            cout << tree[index] << " ";
            nodes.push(tree[index]);
            index = index * 2 + 1;  //不断指向左子结点，直到左子结点为空为止
        }
                            //上面循环结束，说明左子结点为空
        if (!nodes.empty()) {   //栈不为空，弹出一个元素，去找这个元素的右子结点
            index = nodes.top();    //上面压栈进去的都是根结点，上面循环结束说明左子结点为空，
            nodes.pop();
            index = index * 2 + 2;  //找这个结点的右子结点
        }
    }
    cout << "n";
}

//中序遍历：先输出左子结点，根结点，右子结点
//其实中序遍历和前序遍历是差不多的
void treeMiddleOrderRecursionPrint(int index) { //中序遍历（递归）
    if (isbool[index]) {    //当前结点不为空
        treeMiddleOrderRecursionPrint(index * 2 + 1);   //先找左子结点，把左子结点找完
        cout << tree[index] << " ";                             //输出根结点
        treeMiddleOrderRecursionPrint(index * 2 + 2);   //找右子结点
    }
}

void treeMiddleOrderPrint() {   //中序遍历（非递归）
    cout << "中序遍历n";
    stack nodes;   //用栈保存结点下标
    int index = 0;  //根节点下标
    while (isbool[index] || !nodes.empty()) {   //当前结点存在，或栈内的结点不为空就一直遍历
        while (isbool[index]) {     //只要当前结点存在，就压栈，压入的是根节点
            nodes.push(index);
            index = index * 2 + 1;  //然后一直找左子结点，
        }
                    //循环结束是左子节点为空
        if (!nodes.empty()) {   //栈内的结点是否为空
            index = nodes.top();
            nodes.pop();
            cout << tree[index] << " "; //输出弹出的根节点
            index = index * 2 + 2;  //找根节点的右子结点
        }
    }
    cout << "n";
}

//后序遍历： 先输出左子结点，右子结点，根节点
//后序遍历在递归方式中是和前序中序差不多
//但是非递归情况下 就和前序中序有些不同
void treePostOrderRecursionPrint(int index) {   //后序遍历 （递归）
    if (isbool[index]) {    //判断当前结点是否存在
        treePostOrderRecursionPrint(index * 2 + 1); //先找左子结点
        treePostOrderRecursionPrint(index * 2 + 2); //找右子结点
        cout << tree[index] << " "; //左右子结点都输出后，才输出根节点
    }
}

//当前结点压栈，一直向左子结点访问，一直压栈
//判断右结点是否存在，或者右节点是否被访问了
//如果右节点存在且没访问，那么就访问右节点
void treePostOrderPrint() { //后序遍历 （非递归）
    cout << "后序遍历n";
    stack nodes;
    int index = 0;  //当前结点下标
    int lastindex = 0;  //用此变量记录上一个访问的结点
    while (index != -1 && isbool[index] || !nodes.empty()) { //当前结点存在并且左右结点都访问了（index=-1只有左右结点都被访问才会出现）
                                            //或者nodes栈内结点不为空
        while (isbool[index]) { //当前结点存在，压栈，不断找左子结点（压栈相当于压入的根结点）
            nodes.push(index);
            index = index * 2 + 1;
        }                   //循环结束，左子结点为空
        index = nodes.top();    //保存栈顶值，不出栈

        if(!isbool[index * 2 + 2] || lastindex == index * 2 + 2) {   //右子节点不存在 或者 右子结点上次被访问了
            cout << tree[index] << " "; //证明左结点和右结点都访问过了，然后输出根结点（访问当前根结点）
            nodes.pop();
            lastindex = index;  //记录当前被访问的结点
            index = -1;
        } else {
            index = index * 2 + 2;  //右结点没被访问，访问右结点
        }
    }
}

void treeFloorPrint() { //层序遍历      一层一层的输出
    cout << "层序遍历n";
    int index = 0;  //1 3 7 15 31
    while (index < pow(2, depth) - 1) { //层序遍历每一层的数量都是上一层的二倍（完全二叉树）
        if (isbool[index]) {    //如果当前点存在，就可以输出当前结点
            cout << tree[index] << " ";
        }
        index++;
    }
}



int main() {
    while (true) {
        cout << "输入 1 添加结点  输入 2 输出结点 输出 其他 删除结点 n";
        int temp;
        cin >> temp;
        if (temp == 1) {
            cout << "输入要插入的值n";
            cin >> temp;
            treeInsert(temp);
        } else if(temp == 2) {
//            treePreorderRecursionPrint(0);
            cout << "n";
            treePreorderPrint();
//            treeMiddleOrderRecursionPrint(0);
            cout << "n";
            treeMiddleOrderPrint();
//            treePostOrderRecursionPrint(0);
            treePostOrderPrint();
            cout << "n";
            treeFloorPrint();
            cout << "n";
        } else {
            treeDelete();
        }
        treePrint();
    }
    return 0;
}

二叉树链式存储

#include 
#include "iostream"
#include "queue"
#include "stack"

using namespace std;

typedef struct TreeNode {
    int data;
    struct TreeNode *leftchild, *rightchild;
} TreeNode, *Tree;

    //插入结点
bool treeInsert(Tree &tree, int data) {
    if (tree == NULL) {     //如果根结点为空，把插入的值插入到根结点
        tree = new TreeNode;    //添加结点，设置左子结点和右子结点为空
        tree->data = data;
        tree->leftchild = NULL;
        tree->rightchild = NULL;
        cout << "根节为点空, 插入成功n";
        return true;
    }
    Tree temp = tree;
    while (temp) {
        cout << "输入 1 选择左子结点,";
        cout << "输入 2 选择右子结点,";
        cout << "输入 3 返回上一结点,输入 其他 退出插入操作n";
        int selected;
        cin >> selected;
        if (selected == 1) {
            if (temp->leftchild == NULL) {  //如果左子结点为空，将插入的值放到左子结点
                temp->leftchild = new TreeNode;
                temp->leftchild->data = data;
                temp->leftchild->leftchild = NULL;
                temp->leftchild->rightchild = NULL;
                cout << "插入成功n";
                return true;
            } else {    //如果左子结点不为空，找到左子结点，继续循环
                temp = temp->leftchild;
            }
        } else if (selected == 2) {
            if (temp->rightchild == NULL) { //右子结点为空，将值插入到右子结点
                temp->rightchild = new TreeNode;
                temp->rightchild->data = data;
                temp->rightchild->leftchild = NULL;
                temp->rightchild->rightchild = NULL;
                cout << "插入成功n";
                return true;
            } else {    //右子结点不为空，指向右子结点
                temp = temp->rightchild;
            }
        } else {    //输入其他，自己退出插入操作
            return false;
        }
    }
}

    //删除子树
bool treeDelete(Tree &tree) {
    if (tree == NULL) {     //第一次进来tree为根结点
        cout << "根节点为空,无法删除n";
        return false;
    }
    Tree temp = tree;
    Tree fathertemp;    //记录一下父结点，删除时，把删除结点的父结点的左或者右结点附空
    while (true) {
        if (temp->leftchild != NULL) {  //删除左子结点或者右子结点的时候判断一下是否为空
            cout << "输入 1 选择左子结点,";
        }
        if (temp->rightchild != NULL) {
            cout << "输入 2 选择右子结点,";
        }
        cout << "输入 3 删除此结点,输入 其他 退出删除操作n";
        int selected;
        cin >> selected;
        if (selected == 1 && temp->leftchild != NULL) { //选择左子结点或者右子结点的时候需要判断左子结点或者右子结点是否为空
            fathertemp = temp;  //转向左子结点或者右子结点的时候，记录一下父结点
            temp = temp->leftchild;
        } else if (selected == 2 && temp->leftchild != NULL) {
            fathertemp = temp;
            temp = temp->rightchild;
        } else if (selected == 3) {
            if (fathertemp->leftchild == temp) {    //删除结点如果是父结点的左结点，就把父结点的左结点附空
                fathertemp->leftchild = NULL;
            }
            if (fathertemp->rightchild == temp) {   //右结点同理
                fathertemp->rightchild = NULL;
            }
            Tree t = temp;  //保存一下待删除结点，把待删除结点delete，释放空间
            temp = NULL;//直接指向NULL为什么不能删除？？？？？？？？？？？？

            delete t;
            return true;
        } else {
            return false;   //输入其他，退出删除操作
        }

    }
}

    //层序遍历（非递归）
void treeFloorPrint(Tree tree) {
    cout << "层序遍历:";
    queue q;  //使用队列存结点，同一层的在一块挨着，循环同一层的时候，末尾添加的是下一层的左右子结点
    q.push(tree);   //根结点插入队列
    while (!q.empty()) {    //结点队列不对空，一直循环
        Tree temp = q.front();  //保存队列头结点
        q.pop();
        cout << temp->data << " ";  //输出头结点
        if (temp->leftchild != NULL) {  //左子结点或者右子结点存在，把子结点放入队列
            q.push(temp->leftchild);
        }
        if (temp->rightchild != NULL) {
            q.push(temp->rightchild);
        }
    }
    cout << "n";
}

    //前序遍历（递归）
void treePreRecursionPrint(Tree tree) { //先输出根结点，在找左结点，在找右结点
    if (tree != NULL) {
        cout << tree->data << " ";
        treePreRecursionPrint(tree->leftchild);
        treePreRecursionPrint(tree->rightchild);
    }
}

    //前序遍历（非递归）
void treePrePrint(Tree tree) {
    cout << "前序遍历:";
    stack nodes;  //用栈的原因：后进先出，后面进来的结点是下面的，先弹出这个结点，接着找右子结点
    while (tree != NULL || !nodes.empty()) {    //当前结点不为空，或者结点栈不为空，一直循环，说明还有未输出的结点
        while (tree != NULL) {  //只要结点不为空，一直找左子结点
            nodes.push(tree);
            cout << tree->data << " ";  //输出当前结点，前序遍历，先输出根结点
            tree = tree->leftchild; //不断找左子结点
        }
            //上面循环结束，说明tree结点没有左子树
        if (!nodes.empty()) {   //只要结点队列不为空，就弹出一个结点
            tree = nodes.top(); //弹出没有左子树的结点
            nodes.pop();
            tree = tree->rightchild;    //转到这个树的右子结点，继续循环
        }
    }
    cout << "n";
}

    //中序遍历（递归）
void treeMidRecursionPrint(Tree tree) { //先输出左结点，在输出根结点，输出右结点
    if (tree != NULL) {
        treeMidRecursionPrint(tree->leftchild);
        cout << tree->data << " ";
        treeMidRecursionPrint(tree->rightchild);
    }
}
    //中序遍历（非递归）
void treeMidPrint(Tree tree) {  //与前序遍历大概相同，不过是先输出左子结点
    cout << "中序遍历:";
    stack nodes;
    while (tree != NULL || !nodes.empty()) {
        while (tree != NULL) {
            nodes.push(tree);
            tree = tree->leftchild;
        }
        //当左子结点遍历完后，输出根结点，然后再转到右结点
        if (!nodes.empty()) {
            tree = nodes.top();
            nodes.pop();
            cout << tree->data << " ";
            tree = tree->rightchild;
        }
    }
    cout << "n";
}

    //后序遍历（递归）
void treePostRecursionPrint(Tree tree) {    //先输出左子结点，在输出右子结点，输出根结点
    if (tree != NULL) {
        treePostRecursionPrint(tree->leftchild);
        treePostRecursionPrint(tree->rightchild);
        cout << tree->data << " ";
    }
}

    //后序遍历（非递归）
void treePostPrint(Tree tree) { //后序遍历与前两种不太一样，需要找一个变量存一下上一个访问的结点
    cout << "后序遍历:";           //因为要把左右结点都循环完才能输出根结点，
    stack nodes;
    Tree lastnode;
    while (tree != NULL || !nodes.empty()) {
        while (tree != NULL) {  //左结点不为空就一直找到底，把结点保存到栈里面
            nodes.push(tree);
            tree = tree->leftchild;
        }
        tree = nodes.top(); //此结点左子结点不存在，拿到这个根结点
        if (tree->rightchild == NULL || lastnode == tree->rightchild) { //看右结点是否存在或者是否被访问（如果右结点被访问了，可以输出根结点了）
            cout << tree->data << " ";  //当前根结点被访问了
            nodes.pop();
            lastnode = tree;    //当前根结点被访问后，记录最后一个访问的结点
            tree = NULL;    //把访问过的结点附空
        } else {            //如果右结点存在并且没有被访问的话，转到右结点，重复循环把右结点都访问完，
                            // 当结点访问后，lastnode记录的就是每次最后一个访问的结点
            tree = tree->rightchild;
        }
    }
    cout << "n";
}

    //返回二叉树的深度(递归)
int Depth (Tree tree) {
    if (tree == NULL) {
        return 0;
    }
    return max(Depth(tree->leftchild), Depth(tree->rightchild)) + 1;    //找左或右结点的最大深度 + 1（加一是加上当前这一层）
                                                            //不断循环这种操作
}

    //格式化输出二叉树(直接看顺序存储的注释就可以,格式化输出就是找二叉树的规律)
void treePrint(Tree tree) { //与顺序打印二叉树基本相似(如果结点为空的时候,要创建一个0结点，给0结点的左右结点都附空)
    cout << "打印二叉树:n";
    int depth = Depth(tree);
    queue q;
    q.push(tree);
    for (int i = 0; i < depth; i++) {
        int space = 0;
        for (int j = 0; j < depth - 1 - i; j++) {
            space = space * 2 + 1;
        }
        for (int j = 0; j < space; j++) {
            cout << " ";
        }
        for (int j = 0; j < pow(2, i); j++) {
            cout << q.front()->data;
            if (q.front()->leftchild != NULL) {
                q.push(q.front()->leftchild);
            } else {
                TreeNode *t = new TreeNode;
                t->data = 0;
                t->leftchild = NULL;
                t->rightchild = NULL;
                q.push(t);
            }
            if (q.front()->rightchild != NULL) {
                q.push(q.front()->rightchild);
            } else {
                TreeNode *t = new TreeNode;
                t->data = 0;
                t->leftchild = NULL;
                t->rightchild = NULL;
                q.push(t);
            }
            q.pop();

            for (int k = 0; k < space * 2 + 1; k++) {
                cout << " ";
            }
        }
        cout << "n";
    }
}

int main() {
    Tree tree = NULL;
    int temp;
    while (true) {
        cout << "输入 1 插入结点，输入 2 删除子树，输入 其他 遍历打印二叉树" << endl;
        cin >> temp;
        if (temp == 1) {
            cout << "请输入插入结点的值" << endl;
            cin >> temp;
            treeInsert(tree, temp);
        }else if (temp == 2) {
            treeDelete(tree);
        }
        else {
            treePrePrint(tree);
//            cout << endl;
//            treePreRecursionPrint(tree);
            treeMidPrint(tree);
//            cout << endl;
//            treeMidRecursionPrint(tree);
            treePostPrint(tree);
//            cout << endl;
//            treePostRecursionPrint(tree);
            treeFloorPrint(tree);
            cout << "树的深度:" << Depth(tree) << endl;
            treePrint(tree);
        }
    }
    return 0;
}

Huffman树+编码

#include "iostream"
#include "queue"
#include "unordered_map"
#include "math.h"
#include "string"
#include "string.h"

using namespace std;
typedef struct TreeNode {   //定义Huffman树结构体：字符，权重，huffman编码，左子结点，右子结点
    char c;
    int weight;
    char huffman_code[100];
    struct TreeNode *lefttree;
    struct TreeNode *righttree;
}TreeNode, *Tree;

struct cmp{ //定义树结点排序规则，按权重从小到大排序
    bool operator()(Tree a, Tree b) {
        return a->weight > b->weight;
    }
};

    //huffman树的初始化
void huffmanTreeInit(Tree &tree,unordered_map words) {   //用unordered_map保存每个字符出现的次数
                                    //map和unordered_map差不多的，map是顺序的，unordered_map是按照hash顺序的
                        //！！！优先队列，符合排序的顺序，但是调试的时候里面的顺序不是排序的，弹出的时候是按照排序后的顺序弹出的
                        //！！！优先队列，底层为堆排序，是存储找vector或deque里面，所以调试的时候看到的不是排好序的
    priority_queue,cmp> nodes;
    unordered_map :: iterator words_it;  //创建一个unordered_map的迭代器
    for (words_it = words.begin(); words_it != words.end(); words_it++) {   //循环map里面的内容
        Tree temp = new TreeNode;     //创建树结点，map保存的字符和数量，赋值给树结点
        temp->c = words_it->first;
        temp->weight = words_it->second;
        temp->lefttree = NULL;       //左右子结点赋空值
        temp->righttree = NULL;
        nodes.push(temp);       //把创建的树结点保存到优先队列里
    }
                    //优先队列保证队列内得到元素都是按照自定义的排序规则排序的
    while (!nodes.empty()) {    //只要优先队列不为空，证明还有结点未访问
        if (nodes.size() == 1) {    //当剩下一个结点的时候，无需在合并，把这个结点给tree，从队列弹出结点
            tree = nodes.top();
            nodes.pop();
        } else {
            Tree temp1 = nodes.top();   //取出权重小的两个结点
            nodes.pop();
            Tree temp2 = nodes.top();
            nodes.pop();

            Tree newtemp = new TreeNode;    //把两个权重小的结点合成一个结点
            newtemp->weight = temp1->weight + temp2->weight;
            if (temp1->weight < temp2->weight) {    //权重小的放到左子结点
                newtemp->lefttree = temp1;
                newtemp->righttree = temp2;
            } else {
                newtemp->lefttree = temp2;
                newtemp->righttree = temp1;
            }
            newtemp->c = '0';   //非叶子结点字符赋 0
            nodes.push(newtemp);    //把新结点入优先队列
        }
    }

}

    //huffman编码生成           0代表左子结点，1代表右子结点
void huffmanCodeInit(Tree &tree) {  //用层序遍历，每一层huffman编码多一位
    Tree temp = tree;
    queue nodes;
    nodes.push(temp);
    while (!nodes.empty()) {
        temp = nodes.front();   //访问到当前结点，把当前结点从队列弹出
        nodes.pop();
        if (temp->lefttree != NULL) {   //左子结点不为空，就把左子结点放入优先队列，
            nodes.push(temp->lefttree);
            strcpy(temp->lefttree->huffman_code, temp->huffman_code);   //左结点huffman编码=父结点huffman编码 + 0
            char *str = temp->lefttree->huffman_code;
            while (*str != '') {
                *str++;
            }
            *str = '0';
        }
        if (temp->righttree != NULL) {  //与左子结点同理
            nodes.push(temp->righttree);
            strcpy(temp->righttree->huffman_code, temp->huffman_code);
            char *str = temp->righttree->huffman_code;
            while (*str != '') {
                *str++;
            }
            *str = '1';
        }
    }
}

    //打印huffman编码
void huffmanCodePrint(Tree tree) {
    priority_queue, cmp> nodes;
    queue queue;
    queue.push(tree);
    while (!queue.empty()) {    //先层序遍历，把每个结点都保存到优先队列里面
        Tree temp = queue.front();
        queue.pop();
        if (temp->c != '0') {   //如果字符是 '0' 此结点为非叶子结点，并不是真正的huffman结点
            nodes.push(temp);
        }
        if (temp->lefttree != NULL) {
            queue.push(temp->lefttree);
        }
        if (temp->righttree != NULL) {
            queue.push(temp->righttree);
        }
    }
    while (!nodes.empty()) {    //优先队列（保证队列是有序的）  有序输出每个树结点
        Tree t = nodes.top();
        nodes.pop();
        cout << "字符: " << t->c << " 权值: " << t->weight << " 编码: " << t->huffman_code << endl;
    }
}

    //得到当前huffman树的深度
int getDepth(Tree tree) {

    if (tree == NULL) {
        return 0;
    }
    return max(getDepth(tree->lefttree), getDepth(tree->righttree)) + 1;
}

    //格式化打印huffman树     和链式存储二叉树的格式化输出差不多
void huffmanTreeTypePrint(Tree tree) {
    cout << "打印二叉树:  两行为一层，第一层为字符，第二层为权值 n";
    cout << "   第一层字符： 字符为 0 说明下面有结点， 字符为 N 说明为空结点 n";
    cout << "   第一层权值： 权值为 0 n" << endl;
    int depth = getDepth(tree);
    queue q;
    q.push(tree);
    for (int i = 0; i < depth; i++) {
        int space = 0;
        for (int j = 0; j < depth - 1 - i; j++) {
            space = space * 2 + 1;
        }

        for (int j = 0; j < space; j++) {       //输出huffman字符
            cout << " ";
        }
        queue temp = q;
        for (int j = 0; j < pow(2, i); j++) {
            cout << q.front()->c;
            if (q.front()->lefttree != NULL) {
                q.push(q.front()->lefttree);
            } else {
                TreeNode *t = new TreeNode;
                t->c = 'N';
                t->lefttree = NULL;
                t->righttree = NULL;
                q.push(t);
            }
            if (q.front()->righttree != NULL) {
                q.push(q.front()->righttree);
            } else {
                TreeNode *t = new TreeNode;
                t->c = 'N';
                t->lefttree = NULL;
                t->righttree = NULL;
                q.push(t);
            }
            q.pop();

            for (int k = 0; k < space * 2 + 1; k++) {
                cout << " ";
            }
        }
        cout << "n";


        for (int j = 0; j < space; j++) {       //输出huffman权值
            cout << " ";
        }
        for (int j = 0; j < pow(2, i); j++) {
            cout << temp.front()->weight;
            if (temp.front()->lefttree != NULL) {
                temp.push(temp.front()->lefttree);
            } else {
                TreeNode *t = new TreeNode;
                t->weight = 0;
                t->lefttree = NULL;
                t->righttree = NULL;
                temp.push(t);
            }
            if (temp.front()->righttree != NULL) {
                temp.push(temp.front()->righttree);
            } else {
                TreeNode *t = new TreeNode;
                t->weight = 0;
                t->lefttree = NULL;
                t->righttree = NULL;
                temp.push(t);
            }
            temp.pop();

            for (int k = 0; k < space * 2 + 1; k++) {
                cout << " ";
            }
        }
        cout << "n";
    }
    cout << endl;
}


int main() {
    Tree tree;
    unordered_map words; //用来存每个字符以及字符出现的个数
    string s;
    cin >> s;
    unordered_map :: iterator words_it;  //定义map迭代器，用来表示map的某个结点
    for (int i = 0; i < s.length(); i++) {
        words_it = words.find(s[i]);    //找到s[i]字符的结点
        if (words_it == words.end()) {  //如果找到map结尾，说明不存在当前字符的结点
            words.insert(make_pair(s[i], 1));   //添加当前字符，当前字符出现的次数为1
        } else {    //如果找到了，就把当前字符出现的次数 + 1
            words_it->second++;
        }
    }
    //构建huffman树
    huffmanTreeInit(tree, words);
    //构建完成 huffman树，构建huffman编码
    huffmanCodeInit(tree);
    //格式化输出huffman树
    huffmanTreeTypePrint(tree);
    //输出huffman编码
    huffmanCodePrint(tree);
    return 0;
}