数据结构学习笔记（3-5）：树

附录：所有blog的链接

数据结构学习笔记（1）：基本概念
数据结构学习笔记（2）：线性结构
数据结构学习笔记（3-5）：树
数据结构学习笔记（6-8）：图
数据结构学习笔记（9-10）：排序
数据结构学习笔记（11）：散列查找
数据结构学习笔记（12）：综合习题选讲

第三讲 树（上）

3.1 树与树的表示

数据管理的基本操作之一：查找

查找的定义： 根据某个给定关键字 K K K，从集合 R R R中找出关键字与 K K K相同的记录

查找的分类：

  • 静态查找：集合中记录是固定的。没有插入和删除操作，只有查找
  • 动态查找：集合中记录是动态变化的。除查找，还可能发生插入和删除

静态查找的实现：

  • 顺序查找：在列表头上在设置一个存储空间等于 K K K，从尾部循环查找，等于 K K K的时候退出，如果发现位置是刚才设置的存储空间时说明没有查找到。
  • 二分查找法：要求有序（引发出二分查找的树）由此引发的思考，以树的形式存储数据，查找插入删除有更高的效率。对动态查找也有着更好的表现。

为什么使用树：

分层次组织在管理上具有更高的效率！

树的定义

树(Tree)： n ( n > 0 ) n(n > 0 ) n(n>0)个结点构成的有限集合。当 n = 0 n=0 n=0时，称为空树。

树的性质：

对于任一棵非空树 ( n > 0 ) (n>0) (n>0)，它具备以下性质：

树中有一个称为“根(Root)”的特殊结点，用 r r r表示；

其余结点可分为 m ( m > 0 ) m(m>0) m(m>0)个互不相交的有限集 T 1 T_1 T1​， T 2 T_2 T2​，…， T m T_m Tm​，其中每个集合本身又是一棵树，称为原来树的“子树(SubTree)”

子树不相交。

除了根节点之外，每个节点有且仅有一个父节点。

一个有 N N N节点的树有 N − 1 N-1 N−1条边。

树是保证结点联通的边最少连接方式。

树的基本术语：

1.结点的度（Degree）：结点的子树个数

2.树的度：树的所有结点中最大的度数

3.叶结点（Leaf）：度为0的结点

4.父结点（Parent）：有子树的结点是其子树的根结点的父结点

5.子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。

6.兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。

7.路径：从结点 n 1 n1 n1到 n k n_k nk​的路径为一个结点序列 n 1 n_1 n1​， n 2 n_2 n2​…， n k n_k nk​； n i n_i ni​是 n i + 1 n_{i+1} ni+1​的父结点。

8.路径长度：路径所包含边的个数为路径的长度。

9.祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。

10.子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙。

11.结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。

12.树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。

树的表示方式

儿子兄弟表示法（旋转45度后启发了二叉树）

image-20200725143809327

3.2 二叉树的定义及性质

二叉树的定义

二叉树 T T T：一个有穷的结点集合。这个集合可以为空若不为空，则它是由根结点和称为其左子树 T L T_L TL​和右子树 T R T_R TR​的两个不相交的二叉树组成。

二叉树具体五种基本形态

二叉树的子树有左右顺序之分

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F4aWxdA4-1595921200415)(http://qiniu.daidaixiang.xyz/image-20200725144424417.png)]

image-20200725145026035

二叉树的性质：

一个二叉树第i层的最大结点数为： 2 i − 1 ， i ≥ 1 2^{i-1}，i \geq 1 2i−1，i≥1。

深度为 k k k的二叉树有最大结点总数为： 2 k − 1 ， k ≥ 1 2^{k-1}，k \geq 1 2k−1，k≥1。

对任何非空二叉树 T T T，若 n 0 n_0 n0​表示叶结点的个数、 n 2 n_2 n2​是度为2的非叶结点个数，那么两者满足关系 n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1。

二叉树的抽象数据类型定义

类型名称： 二叉树

数据对象集： 一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。

操作集： BT ∈ \in ∈ BinTree，ltem= ElementType

重要操作有：

  • 1、Boolean IsEmpty（BinTree BT）：判别BT是否为空；
  • 2、void Traversal（BinTree BT）：遍历，按某顺序访问每个结点；
  • 3、BinTree CreatBinTree（）：创建一个二叉树。

3.3 二叉树的遍历

常用的遍历方法有：

先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各结点的时机不同。

二叉树遍历的核心问题：二维结构的线性化

从结点访问其左、右儿子结点

需要一个存储结构保存暂时不访问的结点

存储结构：堆栈、队列

先序遍历

遍历过程：访问根结点；先序遍历其左子树；先序遍历其右子树。

image-20200726094351843

先序遍历递归算法

void PreOrder Traversal（Bin Tree BT）

image-20200726095250428

先序遍历非递归算法

遇到一个结点，就把它压栈，并访问它；

去遍历它的左子树；当左子树遍历结束后，从栈顶弹出这个结点并访问它；

然后按其右指针再去中序遍历该结点的右子树。

image-20200726100117995

中序遍历

遍历过程：中序遍历其左子树；访问根结点；中序遍历其右子树。

image-20200726094750568

中序遍历非递归算法

void InOrder Traversal（Bin Tree BT）

image-20200726095309508

中序遍历非递归算法

遇到一个结点，就把它压栈，并去遍历它的左子树；

当左子树遍历结束后，从栈顶弹出这个结点并访问它；

然后按其右指针再去中序遍历该结点的右子树。

后序遍历

遍历过程：后序遍历其左子树；后序遍历其右子树；访问根结点。

image-20200726094950757

后序遍历递归算法

void PostOrder Traversal（Bin Tree BT）

image-20200726095321646

后序遍历非递归算法

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。

第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

void postOrder2(BinTree *root)    //非递归后序遍历
{
    stack s;
    BinTree *p=root;
    BTNode *temp;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)              //沿左子树一直往下搜索，直至出现没有左子树的结点 
        {
            BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
            btn->btnode=p;
            btn->isFirst=true;
            s.push(btn);
            p=p->lchild;
        }
        if(!s.empty())
        {
            temp=s.top();
            s.pop();
            if(temp->isFirst==true)     //表示是第一次出现在栈顶 
             {
                temp->isFirst=false;
                s.push(temp);
                p=temp->btnode->rchild;    
            }
            else//第二次出现在栈顶 
             {
                cout<btnode->data<<"";
                p=NULL;
            }
        }
    }    
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

​ 第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

void postOrder3(BinTree *root)     //非递归后序遍历
{
    stack s;
    BinTree *cur;                      //当前结点 
    BinTree *pre=NULL;                 //前一次访问的结点 
    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if((cur->lchild==NULL&&cur->rchild==NULL)||
           (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
        {
            cout<data<<"";  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
              s.pop();
            pre=cur; 
        }
        else
        {
            if(cur->rchild!=NULL)
                s.push(cur->rchild);
            if(cur->lchild!=NULL)    
                s.push(cur->lchild);
        }
    }    
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

层序遍历：

先根结点入队

从队列中取出一个元素；

访问该元素所指结点；

若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队。

void LevelOrder Traversal（BinTree BT）：层次遍历，从上到下、从左到右

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dXDtCjOA-1595921200455)(http://qiniu.daidaixiang.xyz/image-20200726102315197.png)]

3.4 二叉树的存储结构

顺序存储结构

完全二叉树：按从上至下、从左到右顺序存储

n n n个结点的完全二叉树的结点父子关系：

非根结点（序号 i > 1 i>1 i>1）的父结点的序号是 [ i / 2 ] [ i/2 ] [i/2]；

结点（序号为 i i i）的左孩子结点的序号是 2 i 2i 2i，（若 2 i ≤ n 2i\leq n 2i≤n，否则没有左孩子）；

结点（序号为 i i i）的右孩子结点的序号是 2 i + 1 2i+1 2i+1，（若 2 i + 1 ≤ n 2i+1\leq n 2i+1≤n，否则没有右孩子）；

一般二叉树也可以采用这种结构，但会造成空间浪费。补充空节点变成完全二叉树。

链表存储结构

两个指针分别指向左子节点右子节点

第四讲 树（中）

4.1 二叉搜索树

定义：

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。

性质：

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

1.非空左子树的所有键值小于其根结点的键值。

2.非空右子树的所有键值大于其根结点的键值。

3.左、右子树都是二叉搜索树。

函数汇总：

Position Find（ElementType X，BinTree BST）：从二又搜索树BST中查找元素X，返回其所在结点的地址；

（Position FindMin（BinTree BST）：从二又搜索树BST中查找并返回最小元素所在结点的地址；

（PPosition FindMax（BinTree BST）：从二叉搜索树BST中查找并返回最大元素所在结点的地址

Bin Tree Insert( ElementType X,BinTree BST)：插入

Bin Tree Delete(ElementType X,BinTree BST)：删除

查找操作：

从根结点开始，如果树为空，返回NULL
若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：

  • 若X小于根结点键值，只需在左子树中继续搜索；
  • 如果X大于根结点的键值，在右子树中进行继续搜索；
  • 若两者比较结果是相等，搜索完成，返回指向此结点的指针。

image-20200726104119388

image-20200726105439953

插入操作：

【分析】关键是要找到元素应该插入的位置，可以采用与Find类似的方法

image-20200726154849088

删除操作：

考虑三种情况：

要删除的是叶结点：直接删除，并再修改其父结点指针—置为NULL

要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点

要删除的结点有左、右两棵子树：用另一结点替代被删除结点：右子树的最小元素或者左子树的最大元素（因为这两种节点必定只有一个子树可以继续使用第二种情况）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lNzP7VaY-1595921200468)(http://qiniu.daidaixiang.xyz/image-20200726155529112.png)]

4.2 平衡二叉树

平衡因子（Balance Factor，简称BF）： B F ( T ) = h L − h R BF(T)=h_L-h_R BF(T)=hL​−hR​，其中 h L h_L hL​和 h R h_R hR​分别为 T T T的左、右子树的高度。

定义

平衡二叉树（Balanced Binary Tree）（AVL树）:

空树，或者任一结点左、右子树高度差的绝对值不超过1，即 ∣ B F ( T ) ∣ ≤ 1 |BF(T)|\leq 1 ∣BF(T)∣≤1

平衡二叉树的调整

调整完后仍然要符合查找树和搜索树的定义左小右大

调整方式1：RR旋转（RR插入，右单旋）

出现不满足 ∣ B F ( T ) ∣ ≤ 1 |BF(T)|\leq 1 ∣BF(T)∣≤1的节点为发现者，麻烦节点在发现者右子树的右边

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AkYRe2Rs-1595921200469)(http://qiniu.daidaixiang.xyz/image-20200726161216728.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0n9F6hck-1595921200470)(http://qiniu.daidaixiang.xyz/image-20200726161635109.png)]

调整方式2：LL旋转（LL插入，左单旋）

出现不满足 ∣ B F ( T ) ∣ ≤ 1 |BF(T)|\leq 1 ∣BF(T)∣≤1的节点为发现者，麻烦节点在发现者左子树的左边

image-20200726161850240

调整方式3：LR旋转（LR插入）

出现不满足 ∣ B F ( T ) ∣ ≤ 1 |BF(T)|\leq 1 ∣BF(T)∣≤1的节点为发现者，麻烦节点在发现者左子树的右边

image-20200726162322113

调整方式3：RL旋转（RL插入）

出现不满足 ∣ B F ( T ) ∣ ≤ 1 |BF(T)|\leq 1 ∣BF(T)∣≤1的节点为发现者，麻烦节点在发现者右子树的左边

image-20200726162530454

第五讲 树（下）

5.1 堆

优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。

image-20200726163022945

使用完全二叉树是为了平衡树的结构使得两边深度近似相等减少查找时间。

image-20200726163213560

image-20200726163419418

最大堆的操作

新建堆

image-20200726190142789

插入元素

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bCZJQMdI-1595921200474)(http://qiniu.daidaixiang.xyz/image-20200726190458244.png)]

最大堆的删除（一定是删除最大值）

取出根结点（最大值）元素，同时删除堆的一个结点。

image-20200726191519570

最大堆的建立

建立最大堆：将已经存在的N个元素按最大堆的要求存放在一个一维数组中

方法1：通过插入操作，将 N N N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为 O ( N l o g N ) O(NlogN) O(NlogN)。

方法2：在线性时间复杂度下建立最大堆。
（1）将 N N N个元素按输入顺序存入，先满足完全二叉树的结构特性（2）调整各结点位置，以满足最大堆的有序特性。

5.2 哈夫曼树与哈夫曼编码

哈夫曼树的定义

根据结点不同的查找频率构造更有效的搜索树

带权路径长度（WPL）：设二叉树有 n n n个叶子结点，每个叶子结点带有权值 W k W_k Wk​，从根结点到每个叶子结点的长度为 l k l_k lk​，则每个叶子结点的带权路径长度之和就是： W P L = ∑ k = 1 n w k l k WPL=\sum_{k=1}^{n}{w_kl_k} WPL=∑k=1n​wk​lk​.

最优二叉树或哈夫曼树：WPL最小的二叉树

特点

image-20200726193931806

哈夫曼编码二叉树

二叉树用于编码用二叉树进行编码：
（1）左右分支：0、1（2）编码字符只在叶结点上，就不会出现二义性

5.3 集合及运算

集合运算：交、并、补、差，判定一个元素是否属于某一集合

并查集：集合并、查某元素属于什么集合

image-20200726203900760

查找运算

image-20200726203931901

并运算

image-20200726204544993

小白专场：堆中的路径 - C语言实现

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60779 人正在系统学习中
注：本文转载自blog.csdn.net的呆呆象呆呆的文章"https://blog.csdn.net/qq_41554005/article/details/107637163"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！