数据结构详细笔记——二叉树

这篇具有很好参考价值的文章主要介绍了数据结构详细笔记——二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


二叉树的定义和基本术语

二叉树的基本概念

二叉树是n(n>=0)个结点的有限集合
①或者为空的二叉树,即n=0
②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成,左子树和右子树又分别是一颗二叉树

特点:
1、每一个结点至多只有两棵子树
2、左右子树不能颠倒(二叉树是有序树)

注意区别:度为2的有序树与二叉树的区别
度为2的树:肯定是非空树,所有结点的度<=2,至少有一个结点的度为2
二叉树:可以为空树,所有的结点只要<=2就可

特殊的二叉树

满二叉树

定义:一颗高度为n,且有 2ⁿ-1 个结点的二叉树
数据结构详细笔记——二叉树,数据结构,数据结构,笔记

特点:
1、只有最后一层有叶子结点
2、不存在度为1的结点(只存在度为0或者2的结点)
3、按层序从1开始编号,结点 i 的左孩子为 2i,右孩子为 2i+1,结点 i 的父节点为 ⌊ i/2 ⌋;

完全二叉树

定义:当且仅当其每个结点都与高度为 h 的满二叉树中的编号为 1~n 的结点一一对应时,称为完全二叉树
数据结构详细笔记——二叉树,数据结构,数据结构,笔记
特点:
1、只有最后两层有叶子结点
2、最多只有一个度为1的结点
3、按层序从1开始编号,结点 i 的左孩子为 2i,右孩子为 2i+1,结点 i 的父节点为 ⌊ i/2 ⌋;(如果有的话)
4、i <= ⌊ n/2 ⌋ 为分支结点,i > ⌊ n/2 ⌋ 为叶子结点

如果某结点只有一个孩子,那么这个孩子一定是左孩子

二叉排序树

定义:一颗二叉树或者空二叉树具有如下性质的称为二叉排序树
1、左子树上所有结点的关键字均小于根结点的关键字
2、右子树上所有结点的关键字均大于根结点的关键字
3、左子树和右子树又各是一棵二叉排序树

二叉排序树可用于元素的排序和搜索

平衡二叉树

定义:树上任一结点左子树右子树深度之差不超过1

平衡二叉树能有更高的搜索效率

二叉树的常考性质

考点一:设非空二叉树中度为0、1、2的结点个数分别为n0、n1、n2,则 n0 = n2 + 1; ( 叶子结点比二分支结点多一个 )

假设树中结点总数为n,则
① n = n0 + n1 +n2
② n = n1 + 2*n2 + 1 (树的结点数 = 总度数 + 1)
②-①得 n0 = n2 + 1

考点二:二叉树第 i 层至多有 2ⁱ⁻¹ 个结点(i>=1)
源于: m 叉树第 i 层至多有 mⁱ⁻¹ 个结点(i>=1)

考点三:高度为 n 的二叉树至多有 2ⁿ - 1 个结点(满二叉树)
源于: 高度为 n 的 m 叉树至多有 mⁿ - 1/m-1 个结点

完全二叉树的常考性质

数据结构详细笔记——二叉树,数据结构,数据结构,笔记

常考考点2:对于完全二叉树,可以由结点数 n 推出度为0、1、2的结点个数为n0、n1、n2
完全二叉树最多只有一个度为1的结点,所以
n1 = 0或1
n0 = n2 + 1 ----> n0 + n2 = 2*n2 + 1 一定是奇数

若完全二叉树有 2k 个(偶数)个结点,则 n = n1 + n2 + n3,由上面得 n0 + n2 一定是奇数,所以只有 n1 = 1 时, n 才会是偶数
所以 n1 = 1,n0 = k,n2 = k-1

若完全二叉树有 2k-1 个(奇数)个结点,则 n = n1 + n2 + n3,由上面得 n0 + n2 一定是奇数,所以只有 n1 = 0 时, n 才会是奇数
所以 n1 = 0,n0 = k,n2 = k-1

二叉树的存储结构

顺序存储

定义一个长度为 MaxSize 的数组t,按照从上至下,从左至右的顺序依次存储完全二叉树中的各个结点

#define MaxSize 100
struct TreeNode{
	ElemType value;   // 结点中的数据元素
	bool isEmpty;     // 结点是否为空
}

// 初始化时所有结点标记为空
for(int i = 0; i < MaxSize; i++){
	t[i].isEmpty = true;
}

TreeNode t[MaxSize]

几个重要的常考的基本操作
i 的左孩子 ———— 2i
i 的右孩子 ———— 2i+1
i 的父节点 ———— ⌊ i/2 ⌋
i 所在的层次 ———— 数据结构详细笔记——二叉树,数据结构,数据结构,笔记

若完全二叉树中共有n个结点,则
判断 i 是否有左孩子? ———— 2i <= n
判断 i 是否有右孩子? ———— 2i+1 <= n
判断 i 是否是叶子/分支结点? ———— i > ⌊ n/2 ⌋

注意:如果不是完全二叉树,依然按照层序将各个结点顺序存储,那么无法从结点编号反映出以上这些逻辑关系,所以一定要把二叉树的结点编号与完全二叉树对应起来,但是会导致出现很多空值的存储单元

最坏情况:高度为 n 且只有 n 个结点的单支树(所有结点只有右孩子),也至少需要 2ⁿ - 1 个存储单元

结论:二叉树的顺序存储结构,只适合存储完全二叉树

链式存储

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;  // 左右孩子指针
}BiTNode,*BiTree;

假设有n个结点,则有2n个指针域,除了根结点,每一个结点头上都会连接一个指针域,那么就有n-1个有值的指针域,得出就会有n+1个空指针域
n个结点的二叉链表共有n+1个空链域

根据实际需求决定要不要加父结点指针(三叉链表——方便找父结点)

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;  // 左右孩子指针
	struct BiTNode *parent;          // 父结点指针
}BiTNode,*BiTree;

二叉树的先中后序遍历

  1. 先序遍历:根左右
  2. 中序遍历:左根右
  3. 后序遍历:左右根

其中这三种遍历方式与前中后缀表达式的关系
先序遍历——>前缀表达式
中序遍历——>中缀表达式(需要加界限符)
后序遍历——>后缀表达式

先序遍历(空间复杂度:O(h))

void PreOrder(BiTree T){
	if(T!=NULL){
		visit(T);     //访问根结点
		PreOrder(T->lchild);   // 递归遍历左子树
		PreOrder(T->rchild);   // 递归遍历右子树
	}
}

中序遍历

void PreOrder(BiTree T){
	if(T!=NULL){
		PreOrder(T->lchild);   // 递归遍历左子树
		visit(T);     //访问根结点
		PreOrder(T->rchild);   // 递归遍历右子树
	}
}

后序遍历

void PreOrder(BiTree T){
	if(T!=NULL){
		PreOrder(T->lchild);   // 递归遍历左子树
		PreOrder(T->rchild);   // 递归遍历右子树
		visit(T);     //访问根结点
	}
}

应用

求树的深度

int treeDepth(BiTree T){
	if(T == NULL)
		return 0;
	else{
		int l = treeDepth(T->lchild);
		int r = treeDepth(T->rchild);
		// 树的深度=Max(左子树深度,右子树深度) + 1
		return l>r ? l+1 : r+1;
	}
}

二叉树的层序遍历

算法思想:
①初始化一个辅助队列
②根结点入队
③若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾(如果有的话)
④重复③直至队列为空

// 二叉树的结点(链式存储)
typedef struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

// 链式队列结点
typedef struct LinkNode{
	BiTNode *data;  // 存指针,而不是结点
	struct LinkNode *next;
}LinkNode;

typedef struct{
	LinkNode *front,*rear;  // 队头队尾
}LinkQueue;

// 层序遍历
void LevelOrder(BiTree T){
	LinkQueue(Q);
	InitQueue(Q);  // 初始化辅助队列
	BiTree p;
	EnQueue(Q,T);  // 将根结点入队
	while(!IsEmpty(Q)){
		DeQueue(Q,p);  // 队头结点出队
		visit(p);       // 访问出队结点
		if(p->lchild!=NULL)
			EnQueue(Q,(p->lchild);  // 左孩子入队
		if(p->rchild!=NULL)
			EnQueue(Q,(p->rchild);  // 右孩子入队
	}
}

由遍历序列构造二叉树

若只给出一颗二叉树的前中后序遍历序列中的一种,不能唯一确定一棵二叉树
能构造二叉树的遍历序列组合
1、前序+中序
2、后序+中序
3、层序+中序

线索二叉树

问题1:如何找到指定结点在中序遍历序列中的前驱?
问题2:如何找到结点的中序后继?
找前驱和后继很不方便,遍历操作必须从根开始

还记得之前学到的,n个结点的二叉树,有n+1个空链域,可以用来记录前驱、后继的信息

线索二叉树的存储结构

typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;    // 左右线索标志
}ThreadNode,*ThreadTree;
// tag=0 表示指针指向孩子
// tag=1 表示指针是线索

数据结构详细笔记——二叉树,数据结构,数据结构,笔记

数据结构详细笔记——二叉树,数据结构,数据结构,笔记

二叉树的线索化

中序线索化

// 线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;    // 左右线索标志
}ThreadNode,*ThreadTree;

void visit(ThreadNode *q){
	if(q->lchild==NULL){ //左子树为空,建立前驱线索
		q->lchild=pre;
		q->ltag=1;
	}
	if(pre!=NULL&&pre->rchild==NULL){ //前驱结点的右孩子为空,建立前驱结点的后驱线索
		pre->rchild=q;
		pre->rtag=1;
	}
	pre=q;
}

//中序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T){
	if(T!=NULL){
		InThread(T->lchild);  // 中序遍历左子树
		visit(T);             // 访问根结点
		InThread(T->rchild);  // 中序遍历右子树
	}
}

// 全局变量 pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;

// 中序线索化二叉树T
void CreateInThread(ThreadTree T){
	pre=NULL;   // pre初始化为NULL
	if(T!=NULL){
		InThread(T)  //中序线索化二叉树
		if(pre->rchild==NULL)
			pre->rtag=1;  // 处理遍历的最后一个点
	}
}

先序线索化(与中序遍历有一点不一样:为了防止重复指向,需要判断lchild不是前驱线索)

// 线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;    // 左右线索标志
}ThreadNode,*ThreadTree;

void visit(ThreadNode *q){
	if(q->lchild==NULL){ //左子树为空,建立前驱线索
		q->lchild=pre;
		q->ltag=1;
	}
	if(pre!=NULL&&pre->rchild==NULL){ //前驱结点的右孩子为空,建立前驱结点的后驱线索
		pre->rchild=q;
		pre->rtag=1;
	}
	pre=q;
}

//先序遍历二叉树,一边遍历一边线索化
void PreThread(ThreadTree T){
	if(T!=NULL){
	    visit(T);             // 访问根结点
	    if(T->ltag==0){         // 与中序遍历不一样的地方,为了防止重复指向,需要判断lchild不是前驱线索
			PreThread(T->lchild);  // 与中序遍历不一样的地方,为了防止重复指向,需要判断lchild不是前驱线索
		PreThread(T->rchild);
	}
}

// 全局变量 pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;

// 先序线索化二叉树T
void CreateInThread(ThreadTree T){
	pre=NULL;   // pre初始化为NULL
	if(T!=NULL){
		InThread(T)  //先序线索化二叉树
		if(pre->rchild==NULL)
			pre->rtag=1;  // 处理遍历的最后一个点
	}
}

后序线索化(和中序差不多)

// 线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;    // 左右线索标志
}ThreadNode,*ThreadTree;

void visit(ThreadNode *q){
	if(q->lchild==NULL){ //左子树为空,建立前驱线索
		q->lchild=pre;
		q->ltag=1;
	}
	if(pre!=NULL&&pre->rchild==NULL){ //前驱结点的右孩子为空,建立前驱结点的后驱线索
		pre->rchild=q;
		pre->rtag=1;
	}
	pre=q;
}

//后序遍历二叉树,一边遍历一边线索化
void InThread(ThreadTree T){
	if(T!=NULL){
		InThread(T->lchild);  // 后序遍历左子树
		InThread(T->rchild);  // 后序遍历右子树
		visit(T);             // 访问根结点
	}
}

// 全局变量 pre,指向当前访问结点的前驱
ThreadNode *pre=NULL;

// 后序线索化二叉树T
void CreateInThread(ThreadTree T){
	pre=NULL;   // pre初始化为NULL
	if(T!=NULL){
		InThread(T)  //后序线索化二叉树
		if(pre->rchild==NULL)
			pre->rtag=1;  // 处理遍历的最后一个点
	}
}

二叉树的线索化

中序线索二叉树中找到指定结点*p的中序后继next
① 若 p->rtag=1, 则 next = p->rchild
② 若 p->rtag=0, 则 next = p的右子树中最左下结点

// 找到以p为根的子树中,第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
	// 循环找到最左下结点(不一定是叶结点)
	while(p->ltag==0) p=p->lchild;
	return p;
}

// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
	// 右子树下最左的结点
	if(p->rtag==0) return Firstnode(p->rchild);
	esle return p->rchild;   // rtag ==1 直接返回后继线索
}

// 对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)空间复杂O(1)
void Inorder(TreadNode *T){
	for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)){
		visit(p);
	}
}

中序线索二叉树中找到指定结点*p的中序前驱pre
① 若 p->ltag=1, 则 pre= p->rchild
② 若 p->rlag=0, 则 pre= p的左子树中最右下结点

// 找到以p为根的子树中,最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
	// 循环找到最左下结点(不一定是叶结点)
	while(p->rtag==0) p=p->rchild;
	return p;
}

// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
	// 左子树中最右下结点
	if(p->ltag==0) return Lastnode(p->lchild);
	esle return p->lchild;   // ltag ==1 直接返回前驱线索
}

// 对中序线索二叉树进行逆向中序遍历
void RevInorder(TreadNode *T){
	for(ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p)){
		visit(p);
	}
}

在先序线索二叉树中找到指定结点*p的先序后继next
① 若 p->rtag=1, 则 next = p->rchild
② 若 p->rtag=0,
1、若p有左孩子,则先序后继为左孩子
2、若p没有左孩子,则先序后继为右孩子

在先序线索二叉树中找到指定结点*p的先序前驱pre
① 若 p->ltag=1, 则 next = p->lchild
② 若 p->ltag=0, 需要从头开始遍历

在后序线索二叉树中找到指定结点*p的后序前驱pre
① 若 p->ltag=1, 则 pre= p->lchild
② 若 p->ltag=0,
1、若p有右孩子,则后序前驱为右孩子
2、若p没有右孩子,则后序前驱为左孩子

在后序线索二叉树中找到指定结点*p的后序后继next
① 若 p->rtag=1, 则 next = p->rchild
② 若 p->rtag=0, 需要从头开始遍历文章来源地址https://www.toymoban.com/news/detail-739224.html

到了这里,关于数据结构详细笔记——二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之线索二叉树详细解释

    1.1 线索二叉树的原理 我们现在倡导节约型社会,一切都应该以节约为本。但当我们创建二叉树时我们会发现其中一共有两个指针域,有的指针域指向的结构为空,这也就浪费了很多空间。所以为了不去浪费这些空间我们采取了一个措施。就是利用那些空地址,存放指向结点

    2023年04月20日
    浏览(41)
  • 【数据结构】—搜索二叉树(C++实现,超详细!)

                                                           🎬 慕斯主页 : 修仙—别有洞天                                                        ♈️ 今日夜电波 :消えてしまいそうです—真夜中                                              

    2024年02月05日
    浏览(40)
  • 数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)

    有朋自远方来,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,鞭数十,驱之别院 1.1 二叉树中组分构成名词概念 1.2 二叉树的结构概念 1.3 特殊的二叉树 2.1 顺序存储 2.2 链式存储 前言: 在你的想象中如果有一个“二叉树”会是什么样子呢? 顾名思义,现实中的二叉树我们

    2024年04月13日
    浏览(46)
  • 数据结构初阶之二叉树的详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 1.前言  2.二叉树各个功能代码实现 2.1二叉树结构体 2.2二叉

    2024年02月05日
    浏览(42)
  • 【数据结构】二叉树中的递归问题(超详细画图~)

    和光同尘_我的个人主页 不管风吹浪打,胜似闲庭信步。 --毛泽东 我本来还说上节难来着,没想到这节更难🥲 不过我既然会了保证xdm也能看懂👍 首先回顾下二叉树的概念 二叉树是由:空树 或者非空树(根节点,根节点的左子树、根节点的右子树)组成的 从概念中可以看出

    2024年02月07日
    浏览(38)
  • 数据结构之二叉树(C语言附详细代码)

    目录 一,树和二叉树 1.树 ①定义 ②关于树的一些概念 2.二叉树 ①定义 ②特殊的二叉树 ③二叉树的性质 ④二叉树的存储结构(顺序结构,只适用于完全二叉树) ⑤二叉树的遍历 二,二叉树操作代码 1.头文件 2.函数代码 ①创建二叉树 ②前序遍历二叉树 ③中序遍历二叉树 ④后序

    2024年02月01日
    浏览(33)
  • 数据结构之树与二叉树——算法与数据结构入门笔记(五)

    本文是算法与数据结构的学习笔记第五篇,将持续更新,欢迎小伙伴们阅读学习。有不懂的或错误的地方,欢迎交流 前面章节介绍的都是线性存储的数据结构,包括数组、链表、栈、队列。本节带大家学习一种非线性存储的数据结构,即树(tree)。 不管是在面试时,还是日

    2024年02月08日
    浏览(50)
  • 【数据结构】24王道考研笔记——树与二叉树

    树是n个结点的有限集合,n=0时,称为空树。非空树满足: 除了根节点外,任何一个结点都有且仅有一个前驱 结点的层次(深度):从上往下数 结点的高度:从下往上数 树的高度(深度):总共有多少层 结点的度:有几个孩子(分支) 树的度:各节点的度的最大值 森林:

    2024年02月13日
    浏览(50)
  • 【数据结构】二叉树的创建和四种遍历(附带详细注释)

    《数据结构系列首页》是数据结构系列文章的首页,其中会 逐步更新 各种数据结构的实现,有兴趣的选手可以一看。 首页中不仅有各种数据结构的实现,还有学习数据结构 必备的基础知识 ,如果有选手觉得自己的基础不太牢固,可以先将搞定基础知识,之后再攻克数据结

    2024年02月05日
    浏览(68)
  • 【数据结构】二叉树遍历的实现(超详细解析,小白必看系列)

    目录 一、前言 🍎为何使用链式二叉树   🍐何为链式二叉树  🍉二叉树的构建 💦创建二叉链结构 💦手动构建一颗树  🍓二叉树的遍历 (重点) 💦前序遍历  💦中序遍历  💦后续遍历  🍌二叉树的经典问题(重点) 💦二叉树节点个数  💦二叉树叶子节点的个数  💦

    2024年02月02日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包