小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Computer & DL
  4. Data Structure
  5. 正文

数据结构【浙江大学】(第3节)整理

2018年4月24日 1130点热度 0人点赞 0条评论

第三讲 树(上)

3.1 树与树的表示

1.查找

查找是指根据某个给定关键字K,从集合R中找出关键字与K相同的记录。它分为以下两类:

(1)静态查找:集合中记录是固定的,没有插入和删除操作。

(2)动态查找:集合中记录是动态变化的,除了查找,还可能发生插入和删除。

首先举一个顺序查找的例子。此例需要注意,其设置了一个哨兵,因此可以减少判断中的一个条件。这个例子要求是在Element[1]~Element[n]中查找关键字为K的数据元素,其结构体如下:

typedef struct LNode *List;
struct LNode{
       ElementType Element[MAXSIZE];
       int Length;
};

则查找算法代码如下:

int SequentialSearch(List Tb1, ElementType K)
{
       int i;
       Tb1->Element[0]=K;/*建立哨兵*/
       for(i-Tb1->Length;Tb1->Element[i]!=K;i--);
       return i;/*查找成功返回下标,不成功返回0*/
}

时间复杂性O(n)。

再举一个二分查找的例子。二分查找遵循以下要求:假设n个数据元素的关键字满足有序,并且是连续存放。

例如,假设有13个数据元素,按照关键字由小到大顺序存放,二分查找关键字为444的数据。

5

16

39

45

51

98

100

202

226

321

368

444

501

理论步骤是如表1.1所示。

表1.1 二分法步骤

left

right

mid

value

comparsion

1

13

7

100

100<444,右侧

8

13

10

321

321<444,右侧

11

13

12

444

444=444,结束

程序代码如下:

int BinarySearch(List Tbl, ElementType K)
{
       int left, right, mid, NoFount = -1;
       left = 1;/*初始左侧边界*/
       right = Tbl->Length;/*初始右侧边界*/
       while (left <= right)
       {
              mid = (left + right) / 2;
              if (K < Tbl->Element[mid])
                     right = mid - 1;
              else if (K > Tbl->Element[mid])
                     left = mid + 1;
              else return mid;
       }
       return NotFound;
}

时间复杂度是O(logN)。

2.树的定义和术语

树(Tree):n(n≥0)个结点构成的有限集合。当n=0时,称为空树。

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

(1)树种有一个称为根的特殊结点,用r表示;

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

(3)子树是不相交的;

(4)除了根结点外,每个结点有且只有一个父节点;

(5)一棵N个结点的树有N-1条边。

树的一些基本术语:

(1)结点的度:结点子树个数。

(2)树的度:树的所有结点中最大的度数。

(3)叶结点:度为0的结点。

(4)父结点:有子树的结点是其子树的根结点的父结点。

(5)子结点:若A结点是B结点的父结点,则称B结点是A结点的子结点。

(6)兄弟结点:具有同一父结点的各结点彼此是兄弟结点。

(7)路径和路径长度:从结点n1到nk的路径为一个结点序列n1,n2,…nk,其中ni是ni+1的父结点。路径所包含边的个数为路径的长度。

(8)祖先结点:沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。

(9)子孙节点:某一结点的子树中的所有结点是这个结点的子孙。

(10)结点的层次:规定根结点在1层,其它任一结点的层数是其父结点的层数加1。

(11)树的深度:树种所有结点总的最大层次是这棵树的深度。

3.树的表示

    数组、链表都是很难表示树的,因为树的结构是多变的,无法统一规定。因此在这里用“儿子-兄弟表示法”,结构如下面所示。

Element

FirstChild

NextSibling

如图1左所示的树结构可以表示为图1右所示的表示法。

 1524538762128265.jpg

图1

把这个树往右转向45°,可以看出,这是一个度为2的树。这种方法也被称为——二叉树。

3.2 二叉树

1.二叉树的定义

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

二叉树的五种基本形态如图2所示,几种特殊二叉树如图3所示。

1524538779384852.jpg 

图2

1524538792735225.jpg 

图3

对完全二叉树左一个说明。完全二叉树可以是满二叉树缺少最低一层最右侧几个,只要前面都对的起来即可,但是绝不能在中间缺几个(如图3右下角)。

2.二叉树的几个重要性质

(1)一个二叉树第i层的最大结点数为:2i-1,i≥1。

(2)深度为k的二叉树最大节点数是2k-1,k≥1。

(3)对任何非空二叉树T,若n0表示叶结点的个数,n2是度为2的非叶结点个数,那么两者满足n0=n2+1。

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

类型名称:二叉树

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

操作集:BT∈BinTree,Item∈ElementType,重要的操作有:

    (1)Boolean IsEmpty(BinTree BT):判断BT是否为空;

(2)void Traversal(BinTree BT):遍历,按某顺序访问每个结点;

(3)BinTree CreatBinTree():创建一个二叉树。

二叉树常用的便利方法有:

(1)void PreOrderTraversal(BinTree BT):先序——根、左子树、右子树;

(2)void InOrderTraversal(BinTree BT):中序——左子树、根、右子树;

(3)void PostOrderTraversal(BinTree BT):后序:左子树、右子树、根;

(4)void LevelOrderTraversal(BinTree BT):层次遍历:从上到下、从左到右。

4.二叉树的存储结构

(1)顺序存储结构

完全二叉树:按从上至下、从左到右顺序存储,n个结点的完全二叉树的结点父子关系,可以使用顺序存储结果。如图4所示。

 4.jpg

图4

这个完全二叉树很有规律,很容易找到其父结点和子结点。我们可以发现:

①非根节点(序号i>1)的父结点的序号是[i/2](在这里[]表示取整);

②结点(序号为i)的左孩子结点序号为2i(若2i>=n,就没有左孩子);

③结点(序号为i)的右孩子结点序号为2i+1(若2i+1>=n,就没有右孩子)。

推广来说,一般二叉树也可以采用这种结构,方法就是通过补空位使其变成完全二叉树。但这样的结果是会造成空间浪费。

(2)链表存储

一般二叉树的结点可以用下面的方式表示:

Left

Data

Right

其代码表示如下:

typedef struct TreeNode *BinTree;
typedef BinTree Position:
struct TreeNode{
       ElementType Data;
       BinTree Left;
       BinTree Right;
};

5.二叉树的递归遍历

(1)先序遍历

遍历过程为:

①访问根结点;②先序遍历其左子树,先序遍历其右子树。

程序如下所示:

void PreOrderTraversal(BinTree BT)
{
       if(BT){
              printf("%d",BT->Data);
              PreOrderTraversal(BT->Left);
              PreOrderTraversal(BT->Right);
       }
}

(2)中序遍历

遍历过程为:

①中序遍历其左子树;②访问根结点;③中序遍历其右子树。

程序如下所示:

void InOrderTraversal(BinTree BT)
{
       if(BT){
              PreOrderTraversal(BT->Left);
              printf("%d",BT->Data);
PreOrderTraversal(BT->Right);
       }
}

(3)后序遍历

便利过程:

①后续遍历其左子树;②后续遍历其右子树;③访问根结点。

代码如下:

void PostOrderTraversal(BinTree BT)
{
       if(BT){
              PreOrderTraversal(BT->Left);
PreOrderTraversal(BT->Right)
printf("%d",BT->Data);;
       }
}

6.二叉树的非递归遍历(以中序为例)

基本思路:使用堆栈。

如图5所示的二叉树,我们以此未来来介绍利用堆栈进行处理的方法,输出顺序为:DBEFAGHCI。处理的方法见表3.1所示。

5.jpg 

图5

表3.1 使用堆栈算法的表格示意

序号

当前结点

堆栈(从左到右相当于从底到顶)

步骤说明

1

A

[A]

首先把A压入堆栈

2

B

[AB]

B为A的左孩子,压入堆栈

3

D

[ABD]

D为B的左孩子,压入堆栈

4

[AB]

D无孩子,将D推出堆栈

5

[A]

将B推出堆栈

6

F

[AF]

由于F为B右孩子,在B推出时将F压入堆栈

7

E

[AFE]

E为F左孩子,压入堆栈

8

[AF]

E无孩子,将E推出堆栈

9

[A]

将F推出堆栈

10

[]

将A推出堆栈

11

C

[C]

将G压入堆栈

12

G

[CG]

G为C的左孩子,压入堆栈

13

[C]

G没有左孩子,G推出堆栈

14

H

[CH]

将G的右孩子压入堆栈

15

[C]

H无孩子,H推出堆栈

16

 []

将C推出堆栈

17

I

[I]

将I压入堆栈

18

[]

将I推出堆栈

具体执行代码如下:

void InOrderTraversal(BinTree BT)
{
       BinTree T=BT;
       Stack S=CreatStack(MaxSize);/*创建并初始化堆栈S*/
       while(T||!IsEmpty(S)){
              while(T)
              {/*一致向左将沿途结点压入堆栈*/
                     Push(S,T);
                     T=T->Left;
              }
              if(!IsEmpty(S))
              {
                     T= Pop(S);/*结点弹出堆栈*/
                     printf("%5d",,T->Data);/*打印结点*/
                     T=T->Right;/*转向右子树*/
              }
       }
}

同理可得,中序遍历为:

void PreOrderTraversal(BinTree BT)
{
       BinTree T=BT;
       Stack S=CreatStack(MaxSize);/*创建并初始化堆栈S*/
       while(T||!IsEmpty(S)){
              while(T)
              {/*一致向左将沿途结点压入堆栈*/
                     printf("%5d",,T->Data);/*打印结点*/
                     Push(S,T);
                     T=T->Left;
              }
              if(!IsEmpty(S))
              {
                     T= Pop(S);/*结点弹出堆栈*/
                     T=T->Right;/*转向右子树*/
              }
       }
}

7.层序遍历

层次遍历是利用队列的方式进行。遍历从根结点开始,首先将根结点指针入队,然后开始执行下面三个操作:

(1)从队列中取出一个元素;

(2)访问该元素所指结点;

(3)若钙元素所指结点的左、右孩子结点费控,则将其左、右孩子的指针顺序入队。

不断执行这三步操作,直到队列为空,再无元素可取,二叉树的层序遍历就完成了。其代码如下所示:

void LevelOrderTraversal(BinTree BT)
{
       BinTree T;
       Queue Q;
       if(!BT) return;/*空树直接返回*/
       Q = CreatQueue(MaxSize);
       AddQ(Q,BT);
       while(!IsEmptyQ(Q)){
              T = DeleteQ(Q);
              printf("%d\n",T->Data); /*访问取出队列的结点*/
              if(T->Left)
                     AddQ(Q,T->Left);
              if(T->Right)
                     AddQ(Q,T->Right);
       }
}

8.遍历应用的例子

【例1】遍历二叉树的应用:输出二叉树中的叶子结点。

void PreOrderTraversal(BinTree BT)
{
       if(BT){
              if(!BT->Left &&!BT->Right)
                     printf("%d",BT->Data);
              PreOrderTraversal(BT->Left);
              PreOrderTraversal(BT->Right);
       }
}

【例2】求二叉树的高度。

int PostOrderGetHeight(BinTree BT)
{
       int HL,HR,MaxH;
       if(BT){
              HL = PostOrderGetHeight(BT->Left);
              HR = PostOrderGetHeight(BT->Right);
              MaxH = (HL>HR)?HL:HR;
              return MaxH+1;
       }
       else return 0;
}

【例3】二元运算表达式树及其遍历

如图6所示。

6.jpg

图6

三种遍历可以得到三种不同的访问结果:

(1)中序遍历得到中缀表达式:a + b * c + d * e + f * g

(2)先序遍历得到前缀表达式:+ + a * b c * + * d e f g

(3)后序遍历得到后缀表达式:a b c * + d e * f + g * +

由此直接将表达式存入链表就可以了。

【例4】由两种遍历序列确定二叉树:已知三种遍历中的任意两种遍历序列,能否唯一确定一棵二叉树呢?

只需要确保其中一个是中序遍历,就可以唯一确定。如果只有前序遍历、后序遍历,这就不可能找到唯一的。

下面以先序和中序遍历序列来确定一棵二叉树。

先序遍历序列的第一个结点就是根结点。这个根结点能够在中序遍历序列中将其余结点分割成两个子序列,根结点前面部分是左子树上的结点,而根结点后面的部分是右子树上的结点。

根据这两个子序列,在先序序列中找到对应的左子序列和右子序列,它们分别对应左子树和右子树。

然后对左子树和右子树分别递归使用相同的方法继续分解。

9.二叉树的创建

    由于树是非线性结构,创建一棵二叉树必须首先确定树种结点的输入顺序,常用的方法是先序创建和层序创建两种。

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数据结构
最后更新:2018年4月24日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
altium designer常用元件电气符号和封装形式(转) An English eBooks download website 今天我生日咯!!! 凌源高中——鬼娃娃的传说TXT下载 A very interesting View 观赛前一天的感受
标签聚合
leetcode Java linux 高中 算法 python学习 Python 生活 学习 鸟哥的linux私房菜
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 8 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号