树与二叉树

发表于 更新于 分类于 ， Disqus：

树与森林

image-20220919163736434

这就是两棵树，暂且称左边的为树A,右边的为树B，很明显，我们调换树A的b、c的顺序，两棵树就相同了。

按照这种思路，树可以分为有序树和无序树。

  • 树
    • 有序树
    • 无序树

有序树：树A和树B不同，因为左右有次序，不能颠倒。

无序树：树A和树B相同，可以颠倒次序。

这就是树啦，那么森林顾名思义，就是很多的树。

树A与树B共同在一起就是一个森林。

森林就是这样很多不相交的树组成，同时仅仅一棵树也可以勉强称为森林。即便这有些勉强。。

森林由树组成，如果我们把树研究明白了，森林就会容易很多。所以我们先研究树。

在介绍下面的东西时，我们不得不引入树的一些相关术语，便于我们去进一步讨论。

术语介绍

image-20220919171417169{height=“300px” width=“300px”}

这棵树上的小圆圈，叫结点。

A是B、C、D的父结点。B、C、D是A的子结点。而A没有父结点，又称为根结点。

K、L这些没有子节点的，又称为叶子结点。

还记得之前学过的离散数学吗？有个叫度的东西。这里我们临时先画一棵简单的树

image-20220919171620732{height=“250px” width=“250px”}

这棵树，很像离散数学的有向图。而树中每个结点的度数，就是这里结点的出度。

  • 结点a的度数2
  • 结点c的度数0
  • 结点b的度数0

所以树结点的度数就是[该结点连接的子结点个数]{.red}

树的度就是全部结点中的最大度数。

好，忘掉刚刚那个图，回到之前的图中。

image-20220919171417169{height=“300px” width=“300px”}

树的层数，就是看有几层。

树的深度等于层数。这个数就是4层，深度为4.

C、G这样就是一棵子树，子树的深度，就是从当前的层数往下数有多少层，C、G这个深度就是2。而D、H、M这个就是3。

[重点是树的性质！]{.red}

树的性质

image-20220919171620732{height=“250px” width=“250px”}

因为刚刚说，每个结点的度就是出度，一个出度就对应一条边。

所以，度数=边数。

从下往上看，每个子节点都有一个父节点，即对应一条边连接子、父结点，只有根结点没有父节点。

所以，结点个数-1 = 边数

总结

度数=边数=结点个数-1

不妨来一个简单的小问题

  1. 在一棵度为4的树T中，若有20个度数为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是[]{.gap}。{.quiz}
    • 41
    • 82 {.correct}
    • 113
    • 122
      {.options}

    解析如下
    因为边数=度数，叶子结点度数为0
    所以，边数= 20x4+10x3+1x2+10x2=122，又因为，边数=结点个数-1
    边数 = 20+10+1+10-1 + 叶子结点
    所以，叶子结点 = 122-40 = 82

树的学习暂时告一段落，树在计算机中，并不容易表示，因此有大佬给出了二叉树，它具有唯一性，并且方便计算机操作。

学了这么多，还没有见过代码，请不要失望！下面将带你走进计算机与树。

二叉树

image-20220919180830179{height=“300px” width=“300px”}

二叉树是一棵有序树，树的度为2。

翻译一下

  • 二叉树有序
  • 每个结点的度数最大是2

如果有三个结点，那么会有5种形状的二叉树。

image-20220919181106537{height=“200px” width=“300px”}

二叉树中，有两种值得我们去关注的特殊情况

  • 满二叉树，除最后一层外，其余层结点度数全部为2。

  • 完全二叉树，按照编号顺序排列的二叉树。

举个栗子

满二叉树

image-20220919180830179{height=“300px” width=“300px”}

完全二叉树

image-20220919180830179{height=“300px” width=“300px”}

满二叉树不难理解，完全二叉树就是每层从左到右依次放入结点，从顶层开始。

image-20220919200839322{height=“300px” width=“300px”}

这个就不是，第三层没有按照顺序放。

树的性质同样适用于二叉树。那么我们根据树的性质，很容易得到二叉树的一些性质。

二叉树的性质

  1. 叶子结点个数 = 度为2的结点个数+1

​ 边数 = 结点度数 = n1 + 2xn2

​ 这里n1为度数为1的结点个数，n2为度数为2的结点个数，依次类推。

​ 边数 = 结点个数-1 = n0+n1+n2-1

​ 所以，n0 = n2+1

  1. 第i层，最多有2i−12^{i-1}个结点，一个i层二叉树，最多有2i−12^{i}-1个结点。

    假设有i=3，满二叉树时，结点最多。

    第一层 1个

    第二层 2个

    第三层 4个

    第四层 8个

    第i层 2i−12^{i-1} 个

    …

​ 等比数列，i层就是等比数列前n项和=a1(1−qn)/(1−q)a1(1-q^{n})/(1-q)

  1. 完全二叉树结点序号除2，结果为父节点序号。

​ image-20220919180830179{height=“300px” width=“300px”}

​ 4/2 = 2

​ 5/2 = 2（地板除）

​ 结点序号/2，结果都为父节点序号。

二叉树的性质，十分简单，到现在为止，你已经知道这个二叉树的理论部分了。此后，我们将一起探索二叉树的使用，最后并制作一个简易计算器，如果时间充足，我们将利用哈夫曼编码，来实现一个压缩程序。

二叉树的存储

就像前面所学的，二叉树也分为顺序存储、链式存储。

顺序存储

image-20220919180830179{height=“300px” width=“300px”}

int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12};

可以这样存储。

如果不是这样完全二叉树，可以用一个特殊字符补成完全二叉树。

image-20220919201655444{height=“180px” width=“180px”}

image-20220919201705283{height=“180px” width=“180px”}

此时就可以存储了

int arr[] = {1,NULL,2,NULL,NULL,NULL,3};

如果是这样的极端情况会很浪费空间，

而链式存储可以很好的解决这个问题。

链式存储

我们需要定义一个结点数据类型

class node{
public:
    int data;
    node * lchild;
    node * rchild;
};

稍后我们会主要使用这种存储方式。

说了这么多，还没有讲如何生成一个二叉树，对二叉树的操作也没有系统化。

但是请你先不要急着写代码，了解完二叉树的遍历，这些东西将迎刃而解。

二叉树的遍历

二叉树的遍历，通常采用递归进行操作，这里主要讲述递归操作，了解完这些主要操作，我知道，你肯定觉得很没意思，到时候将介绍其他遍历方式。如果你以前不知道，将会令你大开眼界。

那么先让我们学习一下三个最常见的遍历操作。

  1. 先序遍历
  2. 中序遍历
  3. 后序遍历

在这里，我不得不放出来一张生动形象的图片，供大家参考。

image-20220919203316683{height=“300px” width=“300px”}

我们使用的递归遍历，每个结点，会经历三次，而先、中、后，三种顺序，分别对应这三次时间段。

所以，先序就是第一次经过的时候访问该结点，中序是第二次经过的时候，后续是第三次经过的时候。

接下来，我将按照此树，给出代码以及运行结果。

//此数的结点
class node{
public:
    int data;
    node * lchild;
    node * rchild;
};

先序遍历

按照第一次经过结点就访问，如图所示的路线经过，依次是根--左--右

void foreachPreOrder(node*tree){
    if(tree== nullptr)return;
    cout<<tree->data;
    foreachPreOrder(tree->lchild);
    foreachPreOrder(tree->rchild);
}

结果=>ABDEFGC

中序遍历

按照第二次经过结点就访问，如图所示的路线经过，依次是左--根--右

void foreachInOrder(node*tree){
    if(tree== nullptr)return;
    foreachInOrder(tree->lchild);
    cout<<tree->data;
    foreachInOrder(tree->rchild);
}

结果=>DBFEGAC

后序遍历

按照第三次经过结点就访问，如图所示的路线经过，依次是左--右--根

void foreachPostOrder(node*tree){
    if(tree== nullptr)return;
    foreachPostOrder(tree->lchild);
    foreachPostOrder(tree->rchild);
    cout<<tree->data;
}

结果=>DFGEBCA

应该不难理解这里的遍历过程。接下来，我们将介绍另一种遍历方式。

层遍历

image-20220919203316683{height=“300px” width=“300px”}

逐层进行遍历。这更直观。

结果=> ABCDEFG。这用大脑太容易写出来了，只需要从第一层到最后一层，每层从左到右排列就可以得到。

那么，我们如何通过计算机进行这样的遍历呢？

上面的递归，其实就是用的栈，这里我们采用队列即可实现这样的效果。

我们先建立一个队列Q。放入tree根结点。

此时Q=[A]

把队首元素的左右结点放入Q=[A,B,C]

再让队首出队Q=[B,C]，result=A

把队首元素的左右结点放入Q=[B,C,D,E]

再让队首出队Q=[C,D,E],result=AB

…依次进行直到Q=[]

void foreachFloor(node*tree){
    queue<node*> q;
    q.push(tree);
    while(!q.empty()){
        node* top = q.front();
        if(top->lchild!= nullptr)q.push(top->lchild);
        if(top->rchild!= nullptr)q.push(top->rchild);
        cout<<top->data;
        q.pop();
    }
}

栈和队列，真是让人猝不及防。但不得不说妙啊！

二叉树的遍历，到这已经说完，然而，二叉树的生成，复制，删除，这些操作，还没讲。接下来，就是这些操作了，学习这些操作前，请务必理清楚遍历。

由于操作涉及到二叉树的生成，为了让大家更清晰，这里必须要补充一点，遍历结果与二叉树的关系。

遍历结果确定二叉树

先说结论。

  • 先序+中序，可以确定二叉树
  • 后续+中序，可以确定二叉树

为啥先序+后序不能确定二叉树？我们先将为啥前两种为啥可以确定二叉树

根据上面的遍历结果

先序=>ABDEFGC

中序=>DBFEGAC

先序中可以看出A为根结点

那么在中序,DBFEGAC，A的左边为左子树，右边为右子树。

image-20220919212722920{height=“300px” width=“300px”}

再看DBFEG在先序中，B在前面，B的左边是左子树，右边是右子树。

image-20220919212734273{height=“300px” width=“300px”}

依次类推，就可以得到一个确定二叉树

后序+中序同理

后序=>DFGEBCA

中序=>DBFEGAC

由后序可知A为根节点。

先序中可以看出A为根结点

那么在中序,DBFEGAC，A的左边为左子树，右边为右子树。

DBFEG中B在后序排列最靠后，所以B为分界点…

看懂上面的，可以试一下，如果依靠先序+后续推出二叉树，没办法推出来。

二叉树的操作

生成

我们可以根据前面的遍历来生成特定形状的二叉树。

只需要填充空结点，补成完全二叉树。即可。

例如，我们可以用顺序存储的方式将数据转换成二叉树。

我想介绍递归+先序，来生成树。

例如我们想生成这棵树。

image-20220919225056910{height=“300px” width=“300px”}

需要先写出来先序，注意空结点用#或者特殊符号表示。

//先序 string expression = "ABC##DE#G##F##"
class node{
public:
    char data;
    node * lchild;
    node * rchild;
    node()=default;
    node(char d):data{d}{
        lchild = nullptr;
        rchild = nullptr;
    }
};
string expression = "ABC##DE#G##F##";
int cnt{0};
void createTree(node*&tree){
    if(cnt==expression.length())return;

    if(expression[cnt]=='#'){
        cnt++;
    }else{
        tree = new node(expression[cnt]);
        cnt++;
        createTree(tree->lchild);
        createTree(tree->rchild);
    }

}

删除二叉树

在最后经过这个结点，也就是第三次经过时，delete掉，并且让指针指向nullptr。

void clean(node* &tree){
    if(tree== nullptr)return;

    clean(tree->lchild);
    clean(tree->rchild);
    delete tree;
    tree = nullptr;
}

复制

先序复制，类似于生成。要比生成简单很多。

第一次经过这个节点时，进行复制操作。

void copy(node*& tree,node*&viceTree){
    if(tree== nullptr)return;
    viceTree = new node(tree->data);
    copy(tree->lchild,viceTree->lchild);
    copy(tree->rchild,viceTree->rchild);
}
//主函数
int main() {

    node *root;
    createTree(root);
    foreachPreOrder(root);
    cout<<endl;
    node *viceRoot;
    copy(root,viceRoot);
    clean(root);

    //foreachFloor(root);
    cout<<viceRoot->data;
    foreachFloor(viceRoot);
}

在这里，给出copy以及clean的结果图。

image-20220920103448252{height=“300px” width=“450px”}

可以看到root树已经没有了，而viceroot树是复制的，仍然存在。

到这里，我们已经完成了二叉树的基本操作，但我们不得不继续探索，仅仅这些只能让我们能够了解二叉树的操作与构成，远不能解决实际问题。下面我们将做一些实例应用二叉树。

在此之前，我们还需补充几个有意思的操作，让二叉树的操作熟练于心。

  • 二叉树的深度计算
  • 二叉树叶子结点数

大家可以发现，二叉树的操作基本都与遍历有关，所以，请大家一定要熟悉遍历的三种方式，以及遍历一笔图。在这里，不得不再次引用遍历图，来加强大家的印象。

image-20220919203316683{height=“300px” width=“300px”}

计算二叉树深度

还拿这个图来说

image-20220919225056910{height=“300px” width=“300px”}

用大脑很容易计算出，深度为5。那么计算机应该怎么得到这个呢。

一个办法是，后序遍历，就是从最左边的最小面开始。统计左右子树的深度。

这个栗子。

C的左子树深度为0，右子树深度为0，C的深度就是两者最大的+1 = 1。

按照后序遍历，需要到第三次路过时，才会进行统计操作。

统计D时，应该先统计E,F。

统计E时，应该先统计G。

G的左子树深度为0，右子树深度为0，G的深度就是两者最大的+1 = 1。

E的左子树深度为0，右子树深度为1，E的深度就是两者最大的+1 = 2。

同C、G，F的深度为1。

D的左子树深度为2，右子树深度为1，D的深度就是两者最大的+1 = 3。

B的左子树深度为1，右子树深度为3，B的深度就是两者最大的+1 = 4。

A的左子树深度为4，右子树深度为0，A的深度就是两者最大的+1 = 5。

int countDeepth(node*tree){
    if(tree== nullptr)return 0;
    int lDeepth = countDeepth(tree->lchild);
    int rDeepth = countDeepth(tree->rchild);
    return max(lDeepth,rDeepth)+1;
}

二叉树叶子结点数

叶子结点的判断是左子树和右子树都是空的，只需要遍历经过结点时，判断左子树和右子树是否为空，如果是叶子结点就返回1。

先序遍历

int countLeaf(node*tree){
    if(tree== nullptr)return 0;
    if(tree->rchild== nullptr&&tree->lchild== nullptr)return 1;
    return countLeaf(tree->lchild)+ countLeaf(tree->rchild);
}

后序遍历

int countLeaf(node*tree){
    if(tree== nullptr)return 0;

    int l = countLeaf(tree->lchild);
    int r = countLeaf(tree->rchild);
    if(tree->rchild== nullptr&&tree->lchild== nullptr)return 1;
    return l+r;
}

中序遍历

int countLeaf(node*tree){
    if(tree== nullptr)return 0;

    int l = countLeaf(tree->lchild);

    if(tree->rchild== nullptr&&tree->lchild== nullptr)return 1;
    int r = countLeaf(tree->rchild);
    return l+r;
}

ok，到这里二叉树的基本操作介绍完毕。大家有兴趣可以去查阅一些其他资料。接下来，将会介绍一些二叉树的应用。二叉搜索、哈夫曼编码等等，这些应用在日常中无处不在，值得我们去学习怎么样使用。

理论必须结合实践，要不然就是空谈了，希望大家把重心放在实践上。

引用

完整代码

#include <iostream>
#include <queue>
using namespace std;
class node{
public:
    char data;
    node * lchild;
    node * rchild;
    node()=default;
    node(char d):data{d}{
        lchild = nullptr;
        rchild = nullptr;
    }
};
void foreachPreOrder(node*&tree){
    if(tree== nullptr)return;
    cout<<tree->data;
    foreachPreOrder(tree->lchild);
    foreachPreOrder(tree->rchild);
}

void foreachFloor(node*&tree){
    queue<node*> q;
    q.push(tree);
    while(!q.empty()){
        node* top = q.front();
        if(top->lchild!= nullptr)q.push(top->lchild);
        if(top->rchild!= nullptr)q.push(top->rchild);
        cout<<top->data;
        q.pop();
    }
}

string expression = "ABC##DE#G##F##";
int cnt{0};


void createTree(node*&tree){
    if(cnt==expression.length())return;

    if(expression[cnt]=='#'){
        cnt++;
    }else{
        tree = new node(expression[cnt]);
        cnt++;
        createTree(tree->lchild);
        createTree(tree->rchild);
    }

}

void clean(node* &tree){
    if(tree== nullptr)return;

    clean(tree->lchild);
    clean(tree->rchild);
    delete tree;
    tree = nullptr;
}

void copy(node*& tree,node*&viceTree){
    if(tree== nullptr)return;
    viceTree = new node(tree->data);
    copy(tree->lchild,viceTree->lchild);
    copy(tree->rchild,viceTree->rchild);
}
int countDeepth(node*tree){
    if(tree== nullptr)return 0;
    int lDeepth = countDeepth(tree->lchild);
    int rDeepth = countDeepth(tree->rchild);
    return max(lDeepth,rDeepth)+1;
}
int countLeaf(node*tree){
    if(tree== nullptr)return 0;

    int l = countLeaf(tree->lchild);

    if(tree->rchild== nullptr&&tree->lchild== nullptr)return 1;
    int r = countLeaf(tree->rchild);
    return l+r;
}
int main() {

    node *root;
    createTree(root);

    cout<< countLeaf(root);

}