树与二叉树

  • 1.树的概念及结构（了解）
  • 2.二叉树概念及结构
  • 3.二叉树常见OJ题练习

1.树的概念及结构（了解）

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像以可倒挂的树，也就是说它是根朝上，而叶朝下的。

  • 有一个特殊的结点，称为根节点，根节点没有前驱结点
  • 除根结点外，其余结点被分为M（M>0）个互不相交的集合T1、T2、T3、......、Tm，其中每一个集合Ti（1<=i<=M）又是一颗结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
  • 因此，树是递归定义的。

image-20220117135720712.png

image-20220117130253112.png

image-20220117130304790.png

image-20220117130321413.png

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6

叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点

非终端节点或分支节点：度不为0的节点：如上图：D、E、F、G...等节点为分支节点

双亲结点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；如上图：树的深度为4

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）颗互不相交的多棵树的集合称为森林；（数据结构中的学习并查集本质就是一个森林）

1.2树的表示

树结构相对线性表就比较复杂了，要存储表示起来就非常麻烦了，实际中树有很多种表示方法，如：双亲表示法，孩子表示法，孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法
image-20220117132914829.png

一种表示方式：


struct TreeNode
{
    int data;
    vector<struct TreeNode*> childs;//C++
}

另一种发送：左孩子右兄弟 如下图所示

typeof int DataType;
struct Node
{
    struct Node* _firstChilds;    //第一个孩子结点
    struct Node* _pNextBrother;    //指向其下一个兄弟结点
    DataType _data;                //结点中的数据域
}

image-20220117133549186.png

第三种表示法：双亲表示法
image-20220117133804531.png

双亲表示法原理：就是存双亲的下标；例如上图：A-0,B-0,C-0、D-1(A)

1.3树在实际中的运用（表示文件系统的目录树结构）
image-20220117134223625.png

2.二叉树概念及结构

2.1概念

一颗二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两颗别称为左子树和右子树的二叉树组成。

二叉树的特点：

  1. 每个结点最多有两颗子树，即二叉树不存在度大于2的结点。
  2. 二叉树的子树有左右之分，其子树的次序不能颠倒。
2.2现实中的二叉树
image-20220117135651078.png
2.3数据结构中的二叉树：
image-20220120134737818.png
2.4特殊的二叉树：
  1. 满二叉树：一个二叉树，如果每一层的结点都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，目结点总数是(2^K^)-1=N，层数则等于log2^N+1^。则它就是满二叉树。

  2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点——对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

    ​ 目结点总数是(2^K^)-1-x=N。K=log2^N+1+x^

image-20220120134717868.png

​ 搜索二叉树(特别适合搜索)：任何一颗数，左子树都比根小，右子树都比根大；(这样的增删查改就有意义了)

  1. 堆：堆的逻辑结构（想象出来的结构）是一个完全二叉树，而物理结构是一个数组。

    堆的两大特征

    1. 结构性：用数组表示的完全二叉树。

    2. 有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）

      • 最大堆(MaxHeap)，也称大顶堆：最大值

        • 要求：树中所有的父亲都要大于等于孩子

      • 最小堆(MinHeap)，也称小顶堆：最小值

        • 要求：树中所有父亲都要小于等于孩子

    那么既然是用数组来表示怎么来确定左右孩子呢？

    • ​ 左孩子：LeftChild = Parent*2+1
    • ​ 右孩子：RightChild = Parent*2+2
    • ​ 父亲：Parent = (Child - 1) / 2 （Parent单数减一，双数减二，但在程序中减一即可）

image-20220120141640655.png

    for (int i = (n-1-1)/2; i >= 0; --i)
    {
        AdjustDwon();
    }
2.5二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构（普通二叉树：不讲普通二叉树的增删查改，在实际中普通二叉树增删查改没有意义。有意义的是搜索二叉树）。

二叉树的性质

  1. 若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个结点。

  1. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1。

    1. 对任何一颗二叉树，如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则有n0 = n2 + 1
  2. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=logN
2.5.1顺序存储：
循序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而实现中使用中只有堆才会使用数组来存储，关于堆我们后面再讲。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。image-20220120131250359.png
2.5.2链式存储：

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每一个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链表结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉树。

image-20220120114103484.png

//二叉链
struct BinaryTreeNode
{
     struct BinTreeNode* pLeft; //指向当前节点左孩子
 struct BinTreeNode* pRight; //指向当前节点右孩子
     BTDataType _data;//当前节点值域
}
//三叉链
struct BinaryTreeNode
{
struct BinTreeNode* pParent; //指向当前节点的双亲
 struct BinTreeNode* pLeft; //指向当前节点左孩子
struct BinTreeNode* pRight; //指向当前节点右孩子
 BTDataType _data;//当前节点值域
}

4.二叉树链式结构的实现

4.1二叉树链式结构的遍历

所谓遍历(Traversal)是指沿着某条搜索路线。依次对树种每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其他运算的基础。

image-20220120115713892.png

前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名

​ 1.NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

​ 2.LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

​ 3.LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

​ 4.前序/中序/后序遍历也称：深度优先遍历

​ 5.层序遍历也称：广度优先遍历

由于被访问的结点必是某子树的根，所有N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

image-20220120115805067.png

层序遍历：除了先序遍历、中序遍历、后序遍历外、还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点。以此类推，自上而下。自左至右逐层访问树的结点的过程就是层序遍历。image-20220121114518460.png

分治算法：分而治之，大问题分成类似子问题，子问题再分成子问题...直到子问题不可再分割

前序：A B D NULL NULL E NULL NULL C NULL NULL

中序：NULL D NULL B NULL E NULL A NULL C NULL

后序：NULL NULL D NULL NULL E B NULL NULL C A

A B NULL D F NULL NULL NULL C E NULL NULL NULL

中序：NULL B NULL F NULL D NULL A NULL E NULL C NULL

4.1 AVL树

4.1.1 AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

高度平衡搜索二叉树

​ 一颗AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

4.2 哈夫曼树

4.2.1 哈夫曼树的概念

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。

在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+...+WnLn），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。

1、路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

image-20220211063251450.png

哈夫曼编码：编码是为了给权值列表中的权值数值分别用0，1编码。在哈夫曼树上，左分支边是0， 右分支边是1。 由此构成编码。如下图，依旧采用上面举例的哈夫曼树：

img

编码后，1： 000，2：001， 3：01， 4：10， 5：11

这样有什么用处呢？ 请看这一穿字符：[ABCABDBBDBEDEED]

A出现2次，B出现5次，C出现1次，D出现4次，E出现3次。这也正好是上面举例的权值列表。

那编了这些码有什么用呢？ 用来压缩。 是哈夫曼树的作用。

没有压缩前一个字符用定长的3位表示， 总共需要45位。压缩后是不定长的，而且你会发现出现次数越多的编码长度越短。比如B出现5次，编码是11， 而C只出现一次编码是000。

压缩后是：001 11 000 001 11 10 11 11 10 11 01 10 01 01 10

总共是33位。压缩了12位。

4.3 红黑树(R-B Tree)

4.3.1 红黑树的概念

1. 红黑树的规则特性：

  1. 节点分为红色或者黑色；
  2. 根节点必为黑色；
  3. 叶子节点都为黑色，且为null；
  4. 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
  5. 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
  6. 新加入到红黑树的节点为红色节点；(其实这个是推断出来的，下面会说)

上面的6条就是红黑树给出的自动维持平衡所需要具备的规则

我们需要注意的是第3条：叶子节点都为黑色，且都为null，我们在java中空置是null，所以我们能看到的都是红色的非叶子节点，但要知道它并不是叶子节点。

我们看一看一个典型的红黑树到底是什么样儿？

image-20220211064957028.png

2、红黑树的规则特点能够推断出什么东西？

从根节点到叶子节点的最长路径不大于最短路径的2倍

  怎么样的路径算最短路径？

  从规则5中，我们知道从根节点到每个叶子节点的黑色节点数量是一样的，那么纯由黑色节点组成的路径就是最短路径；

  什么样的路径算是最长路径？

  根据规则4和规则3，红黑树不可能出现连续的红色节点，若有红色节点，则必然有一个连接的黑色节点，当红色节点和黑色节点数量相同时，就是最长路径，也就是黑色节点（或红色节点）* 2

3、对于第6条：新加入的节点为红色节点，为什么呢？

从规则4中知道，当前红黑树中从根节点到每个叶子节点的黑色节点数量是一样的，此时假如新插入的是黑色节点的话，必然破坏规则(它所在的路径上会多出一个黑色节点)，但加入红色节点却不一定，除非其父节点就是红色节点才会破坏规则，因此加入红色节点，破坏规则的可能性小一些，下面我们也会举例来说明。

三、红黑树的插入操作

我们还是以这个红黑树为例：image-20220211065030005.png

插入步骤：

  1. 根据二叉搜索树的特性，找到新的节点合适的插入位置，也就是找到它的爸爸
  2. 决定将它作为它爸爸的左孩子还是右孩子(还是二叉搜树的特点)
  3. 把它标记为红色节点，因为它可能破坏了原红黑树的规则，所以需要变色+旋转来进行调整

情况一：插入之后不破坏规则，不需要旋转，也不需要变色：

我们来看下面这种情况

当我们插入值为【66】的节点时，红黑树变成了这样image-20220211065111091.png

题目：

1.某二叉树共有个节点399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为（B）

A：不存在这样的二叉树

B：200

C：198

D：199

2.在具有2n个结点的完全二叉树中，叶子结点个数为（A）

A：n

B：n+1

C：n-1

D：n/2

3.一颗完全二叉树的节点数位为531，那么这颗树的高度为（B）

A：11

B：10

C：8

D：12

4.清华大学计算机历年考研复试上机题

image-20220210221748917.png

//题解
#include<stdio.h>

typedef struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
}TNode;

void InOrder(TNode* root) {
    if (root == NULL)
    {
        //printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%c ", root->val);
    InOrder(root->right);
}
TNode* CreateTree(char* a, int* p1) {
    if (a[*p1] == '#')
    {
        ++(*p1);
        return NULL;
    }

    TNode* root = (TNode*)malloc(sizeof(TNode));
    if (root == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }

    root->val = a[*p1];
    ++(*p1);

    root->left = CreateTree(a, p1);
    root->right = CreateTree(a, p1);

    return root;
}

int main (){
    char str[100];
    scanf("%s", str);
    int i = 0;
    TNode* root = CreateTree(str, &i);
    InOrder(root);

    return 0;
}
最后修改：2022 年 03 月 02 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏