# 聊一聊悟空编辑器 # > 手把手教学考研大纲范围内树定义,遍历,Huffman,并查集 > 22

2021年11月24日 阅读数:1
这篇文章主要向大家介绍# 聊一聊悟空编辑器 # > 手把手教学考研大纲范围内树定义,遍历,Huffman,并查集 > 22,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

Talk is cheap. Show me the code.
理论处处都有,代码加例题本身练习才能真的学会ios

树的基本概念
二叉树顺序存储的定义数组

<div id = 'index0'>markdown

</div>数据结构

树的基本概念

咱们还记得线性表一个结点连着一个结点
相对于线性表来讲是 一个结点连着多个结点ide

在这里插入图片描述

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 有序树和无序树:将数种结点的各子树当作从左到右有次序的(不能互换),则为有序树,不然为无序树 (有序树中最左边的子树的根称为第一个孩子,最右边称为最后一个孩子) spa

14 森林: m棵互不相交的树的集合,对于每一个根结点来讲,子树的集合即为森林
在这里插入图片描述code

<div id = 'index1'>blog

</div>排序

二叉树顺序存储的定义

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

在这里插入图片描述

//二叉树的顺序存储(相似于彻底二叉树)
//其实就是数组  建议看看堆排序
#include "iostream" 
#include "queue"
#include "stack"
#include "cmath"
#include <algorithm> 

#define MAXSIZE 1000

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

int tree[MAXSIZE] = {0};    //二叉树数组
bool isbool[MAXSIZE] = {0}; //判断当前结点是否有数据 
queue<int> 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<int> 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 <space * 2 + 1; k++) {    //字符和字符的空格数量为  2*space+1
                cout << " ";
            }
        }
        cout << "\n";
    }
}
/*
 *               1
 *       1               1
 *   1       1       1       1
 * 1   1   1   1   1   1   1   1
 *1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 * */

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<int> 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<int> 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<int> 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;
}