二叉树的相关操作

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

一.二叉树

本文的数据结构基于C语言练习。

C语言中的二叉树是一种数据结构,用于表示具有层次关系的数据集合。它由一个根节点开始,每个节点最多有两个子节点,分别称为左子节点和右子节点。

二叉树有许多相关性质,其中一些重要的包括:

  1. 深度:指从根节点到某个节点的路径长度。树的深度等于所有节点深度的最大值加上1。
  2. 高度:指从某个节点到其子树中的最远叶子节点的路径长度。树的高度等于根节点的高度。
  3. 节点数:指树中节点的总数。如果树的深度为d,则节点数不超过2^d-1个。
  4. 层次遍历:按照从上到下、从左到右的顺序遍历树中的节点。
  5. 先序遍历:先访问根节点,然后按照先序遍历左子树和右子树。
  6. 中序遍历:先按照中序遍历左子树,然后访问根节点,最后按照中序遍历右子树。
  7. 后序遍历:先按照后序遍历左子树和右子树,然后访问根节点。
  8. 平衡二叉树:指任意节点的左右子树高度差不超过1的二叉树。
  9. 满二叉树:指所有非叶子节点都有两个子节点,且所有叶子节点都在同一层的二叉树。
  10. 完全二叉树:指除最后一层之外,每一层都被填满的二叉树,最后一层从左到右填充。

二.二叉树的遍历

这里通过一个例子来详细介绍:

2023/6/8 09:49:27

二叉树遍历是指按照某个顺序依次访问二叉树的每一个节点,目前比较常用的三种遍历分别是先序遍历、中序遍历和后序遍历。下面举例介绍这三种遍历:

假设有如下一棵二叉树:

        1
       / \
      2   3
     / \   
    4   5  

其中节点1为根节点,节点2和3为节点1的子节点,节点4和5为节点2的子节点。

  1. 先序遍历:

先序遍历指先访问根节点,然后按先序遍历左子树和右子树。对于上述二叉树的先序遍历结果为:1, 2, 4, 5, 3。具体方法是从根节点出发,先输出根节点1,然后递归地遍历左子树2和右子树3,对于左子树2,先输出它的根节点2,然后递归遍历它的左子树4和右子树5。

  1. 中序遍历:

中序遍历指按照中序遍历左子树、访问根节点和中序遍历右子树的顺序来遍历二叉树。对于上述二叉树的中序遍历结果为:4, 2, 5, 1, 3。具体方法是先递归遍历左子树2,输出节点4和2,再输出根节点1,最后递归遍历右子树3,输出节点5。

  1. 后序遍历:

后序遍历指按照后序遍历左子树、后序遍历右子树和访问根节点的顺序来遍历二叉树。对于上述二叉树的后序遍历结果为:4, 5, 2, 3, 1。具体方法是先递归遍历左子树2,输出节点4和5,再递归遍历右子树3,输出节点2,最后输出根节点1。

三.线索二叉树

线索二叉树是一种特殊的二叉树,其每个节点都附带了指向其前驱和后继节点的线索,这些线索可以加速对节点的遍历操作。在线索二叉树中,若左子树存在,则左子树的最右下节点的右孩子会指向该节点的后继节点;若右子树存在,则右子树的最左下节点的左孩子会指向该节点的前驱节点。

线索二叉树的遍历分为前序、中序、后序和按照线索遍历四种方式,下面我们以中序遍历为例进行介绍。

假设有如下一棵二叉树:

        1
       / \
      2   3
     / \   
    4   5  

其中节点1为根节点,节点2和3为节点1的子节点,节点4和5为节点2的子节点。

对于线索二叉树,我们需要首先将其转换成线索二叉树,过程如下:

  1. 先建立一个头结点,其中头结点的左孩子指向根节点,右孩子指向中序遍历的最后一个节点。
  2. 对于每一个节点,如果其左孩子不存在,则将其左孩子设置为前驱节点,并将前驱节点的右孩子指向该节点。如果其右孩子不存在,则将其右孩子设置为后继节点,并将后继节点的左孩子指向该节点。
  3. 对根节点进行中序遍历,递归地对左子树进行线索化,然后处理其前驱指针,随后递归地对右子树进行线索化,然后处理其后继指针。

转换成线索二叉树之后,我们可以使用中序遍历来遍历整棵树。具体方法是从头结点开始,依次访问每个节点的后继节点,直到遇到尾节点即可结束遍历。

对于上述例子,通过中序遍历得到的节点顺序为:4, 2, 5, 1, 3。而在线索二叉树中,4的后继节点是2,2的后继节点是5,5的后继节点是1,1的后继节点是3,最后3的后继节点是尾节点,因此我们依次输出4、2、5、1、3就完成了中序遍历。

四.核心功能实现

1.初始构造一棵二叉树

//我们先初始化构造一个二叉树
void InitBTree(BTnode &T){                  //T是一个结构体指针,指向这个树结点的结构体,而这个结构体又包含两个指针
	T=(BTnode)malloc(sizeof(BTree));
	T->data=50;
	T->lchild=NULL;
	T->rchild=NULL;
	T->ltag=T->rtag=0;
}

//插入一个树结点
void Insert(BTnode &T,int x){             //这里x是我们插入结点需要保存的值
	if(T == NULL){ // 最后结点为空,插入节点
		T = (BTnode)malloc(sizeof(BTree));
		T->data = x;
		T->lchild = NULL;
		T->rchild = NULL;
		T->ltag=T->rtag=0;
	}
	else{
		if(x <= T->data){ // 插入左子树
			Insert(T->lchild, x);
		}
		else{ // 插入右子树
			Insert(T->rchild, x);
		}
	}
}

2.普通二叉树的递归遍历

//访问,也就是输出函数
void Visit(BTnode &T){
	printf("%d\t",T->data);
}

//先序遍历
void Preorder(BTnode &T){
	if(T!=NULL){
		Visit(T);        //在访问函数里面定义我们想要的可视化输出
		Preorder(T->lchild);
		Preorder(T->rchild);
	}
}

//中序遍历
void Inorder(BTnode &T){
	if(T!=NULL){
		Inorder(T->lchild);
		Visit(T);
		Inorder(T->rchild);
	}
}

//后序遍历
void Postorder(BTnode &T){
	if(T!=NULL){
		Postorder(T->lchild);
		Postorder(T->rchild);
		Visit(T);
	}
}

3.二叉树线索化

//中序遍历线索化
void InThread(BTnode &p,BTnode &pre){
	if(p!=NULL){
		InThread(p->lchild,pre);
		if(p->lchild==NULL){
			p->lchild=pre;             //中序遍历左孩子就是根结点的前驱
			p->ltag=1;
		}
		if(pre!=NULL && pre->rchild==NULL){           //刚刚建立了这个结点的前驱,那前驱结点的后继不就是该结点吗
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;                   //这个结点标记完了,换下一个
		//中间这一部分可以改写成visit函数,你就看出来这个简单的递归了
		InThread(p->rchild,pre);
	}
}
/*这只是针对某一个结点线索化的处理过程*/

//构造中序线索二叉树
void createITree(BTnode &T){          //调用刚刚线索化的方法来改造我们原来的二叉树
	BTnode pre=NULL;                //刚开始假设没有pre则为NULL
	if(T!=NULL){
		InThread(T,pre);                //把二叉树进行线索化
		pre->rchild=NULL;               //处理最后一个结点
		pre->rtag=1;
	}
	
}

4.线索二叉树的遍历

//该函数用来找二叉树中序序列的第一个结点
BTNode *Firstnode(BTnode &p){
	while(p->ltag==0)              //第一个结点没有前驱结点,所以其lchild=0,其余原本左孩子为空的结点都变成了左线索
		p=p->lchild;
	return p;
}

//该函数用来找后继结点
BTNode *Nextnode(BTnode &p){
	if(p->rtag==0)
		return Firstnode(p->rchild);      //rtag=0说明还是右孩子,找右子树中的第一个结点为其后继
	else
		return p->rchild;  //ratg=1说明右孩子就是后继,直接返回
}

//最后的大招,中序线索二叉树的遍历
void Inorder1(BTnode &T){
	for(BTNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))          //不要for循环只会i+1
		Visit(p);                
}

五.完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BTNode{
	int data;                          //为了实验简便,这里存储的数据都为整数
	struct BTNode *lchild,*rchild;
	int ltag,rtag;                   //左右线索标志
}BTree,*BTnode;                       //之所以这样是为了区分结点和树

//我们先初始化构造一个二叉树
void InitBTree(BTnode &T){                  //T是一个结构体指针,指向这个树结点的结构体,而这个结构体又包含两个指针
	T=(BTnode)malloc(sizeof(BTree));
	T->data=50;
	T->lchild=NULL;
	T->rchild=NULL;
	T->ltag=T->rtag=0;
}

//插入一个树结点
void Insert(BTnode &T,int x){             //这里x是我们插入结点需要保存的值
	if(T == NULL){ // 最后结点为空,插入节点
		T = (BTnode)malloc(sizeof(BTree));
		T->data = x;
		T->lchild = NULL;
		T->rchild = NULL;
		T->ltag=T->rtag=0;
	}
	else{
		if(x <= T->data){ // 插入左子树
			Insert(T->lchild, x);
		}
		else{ // 插入右子树
			Insert(T->rchild, x);
		}
	}
}
/*为了方便定义插入规则,我们这里实验二叉排序树的规则即可*/
/*虽然这里用二叉排序树的规则方便了定义插入规则,但复杂了删除操作
  我们这里也只是为了演示二叉树的遍历和线索二叉树,所以不定义删除函数*/

//访问,也就是输出函数
void Visit(BTnode &T){
	printf("%d\t",T->data);
}

//先序遍历
void Preorder(BTnode &T){
	if(T!=NULL){
		Visit(T);        //在访问函数里面定义我们想要的可视化输出
		Preorder(T->lchild);
		Preorder(T->rchild);
	}
}

//中序遍历
void Inorder(BTnode &T){
	if(T!=NULL){
		Inorder(T->lchild);
		Visit(T);
		Inorder(T->rchild);
	}
}

//后序遍历
void Postorder(BTnode &T){
	if(T!=NULL){
		Postorder(T->lchild);
		Postorder(T->rchild);
		Visit(T);
	}
}

/*完成了这几个遍历后,我们要开始构造线索二叉树了*/
/*构造三种线索二叉树,前提是这个树以及存在,我们采用的方法是边遍历边构造*/

//中序遍历线索化
void InThread(BTnode &p,BTnode &pre){
	if(p!=NULL){
		InThread(p->lchild,pre);
		if(p->lchild==NULL){
			p->lchild=pre;             //中序遍历左孩子就是根结点的前驱
			p->ltag=1;
		}
		if(pre!=NULL && pre->rchild==NULL){           //刚刚建立了这个结点的前驱,那前驱结点的后继不就是该结点吗
			pre->rchild=p;
			pre->rtag=1;
		}
		pre=p;                   //这个结点标记完了,换下一个
		//中间这一部分可以改写成visit函数,你就看出来这个简单的递归了
		InThread(p->rchild,pre);
	}
}
/*这只是针对某一个结点线索化的处理过程*/

//构造中序线索二叉树
void createITree(BTnode &T){          //调用刚刚线索化的方法来改造我们原来的二叉树
	BTnode pre=NULL;                //刚开始假设没有pre则为NULL
	if(T!=NULL){
		InThread(T,pre);                //把二叉树进行线索化
		pre->rchild=NULL;               //处理最后一个结点
		pre->rtag=1;
	}
	
}
//这样我们就把原来的那棵二叉树改成了线索二叉树,为了查看我们的线索二叉树是否正确,我们又要写对应线索二叉树的方法

/*对线索树进行遍历时,只要先找到序列的第一个结点,然后依次取其后继,知道其后继为空代表整个二叉树遍历完*/
/*这里又有一点,其右线索标志为1,右孩子就指示其后继,但有时候也有其结点原来左右孩子就都不为空,这个时候就选择其右子树中
  第一个访问的结点(右子树中最左下的结点)为其后继*/

//该函数用来找二叉树中序序列的第一个结点
BTNode *Firstnode(BTnode &p){
	while(p->ltag==0)              //第一个结点没有前驱结点,所以其lchild=0,其余原本左孩子为空的结点都变成了左线索
		p=p->lchild;
	return p;
}

//该函数用来找后继结点
BTNode *Nextnode(BTnode &p){
	if(p->rtag==0)
		return Firstnode(p->rchild);      //rtag=0说明还是右孩子,找右子树中的第一个结点为其后继
	else
		return p->rchild;  //ratg=1说明右孩子就是后继,直接返回
}

//最后的大招,中序线索二叉树的遍历
void Inorder1(BTnode &T){
	for(BTNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))          //不要for循环只会i+1
		Visit(p);                
}

int main(){
	BTnode T;
	InitBTree(T);
	int nums[]={20,45,68,54,8};   //初始化二叉树待插入的数据,注意我们初始化定义了根结点的值为50
	for(int i=0;i<5;i++){
		Insert(T,nums[i]);
	}
	//到这里我们脑海里应该有了二叉树的画面了
	printf("先序遍历:");
	Preorder(T);
	printf("\n");
	printf("中序遍历:");
	Inorder(T);
	printf("\n");
	printf("后序遍历:");
	Postorder(T);
	printf("\n");
	//这一行下面开始我们转向线索二叉树
	createITree(T);
	printf("中序线索二叉树遍历:");
	Inorder1(T);
}

/*这里提一嘴,学习了栈和队列后,我们知道递归背地里是通过栈来实现的,所以这里的三种遍历我们如果
  不想使用递归,就得使用栈,比较麻烦,为了快速演示,递归虽然效率低但我们还是选择使用它*/

六.运行结果

二叉树的相关操作文章来源地址https://www.toymoban.com/news/detail-477715.html

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

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

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

相关文章

  • 深入理解数据结构第三弹——二叉树(3)——二叉树的基本结构与操作

    二叉树(1): 深入理解数据结构第一弹——二叉树(1)——堆-CSDN博客 二叉树(2): 深入理解数据结构第二弹——二叉树(2)——堆排序及其时间复杂度-CSDN博客 前言: 在前面我们讲了堆及其应用,帮助我们初步了解了二叉树的一些原理,但那与真正的二叉树仍有不同,

    2024年04月09日
    浏览(49)
  • 数据结构实验4:二叉树的基本操作

    一、问题描述 运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的基本操作。 三、实验内容及要求 1、构造

    2024年01月23日
    浏览(43)
  • 数据结构:二叉树的基本操作(用递归实现)

             本文将通过完成以下内容来展示二叉树的基本操作,代码解释标注全面而且清晰,代码书写也十分规范,适合初学者进行学习,本篇文章算是本人的一些学习记录分享,希望对有需要的小伙伴提供一些帮助~ 本文的内容为: 用递归的方法实现以下算法: 1.以二叉

    2024年02月06日
    浏览(50)
  • 【数据结构】二叉树的构建与基本操作实现

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.前序建立二叉树 2.销毁二叉树 3.统计 4.查找值为x的节点 5.前中后序遍历 6.层序遍历 7.判断二叉树是否

    2024年02月07日
    浏览(45)
  • 【数据结构】二叉树的存储与基本操作的实现

    二叉树的存储结构分为: 顺序存储 和类似于 链表的链式存储 这里博主讲一下链式存储 二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有 二叉和三叉 表示方式 二叉表示: 三叉表示: 这里博主主要讲解一下孩子表示法 在学习二叉树的基本操作前,需

    2024年02月04日
    浏览(48)
  • 二叉树的基本操作-C语言实现-数据结构作业

    目录  (1)二叉树的创建; (2)二叉树的先序、中序和后序遍历输出; (3)输出二叉树的叶子节点和度为2的节点的数量; (4)输出二叉树的深度; (5)将二叉树所有节点的左右子树互换(左子树变右子树,右子树变左子树); (6)参考书上,二叉树按层次输出(一行输出一层); (7)删除二

    2024年02月04日
    浏览(48)
  • 数据结构实验报告,二叉树的基本操作(C语言)

    作者:命运之光 专栏:数据结构 实验六 二叉树的基本操作 实验环境:Visual C++或Dev C++ 实验目的: 1、掌握二叉树创建; 2、掌握二叉树的遍历及常用算法。 实验内容: 通过完全前序序列创建一棵二叉树,完成如下功能: 1)输出二叉树的前序遍历序列; 2)输出二叉树的中序遍

    2024年02月09日
    浏览(37)
  • 数据结构:二叉树及相关操作

    在实现二叉树前,我们要先对树产生一些基本的认识,才可以去实现它。树的用途非常广泛,向文件系统的目录树结构等。 树是一种 非线性的数据结构 ,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 有一个特殊的结点,称为根结点,根节点没有前驱结点。 除根

    2024年02月11日
    浏览(46)
  • 数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)

    目录 二叉树的定义 二叉树具体的五种基本形态 1.空树 2.只有一个节点 3.有左子树,但右子树为空 4.有右子树,但左子树为空  5.左右两子树都不为空 特殊二叉树 斜二叉树 满二叉树  完全二叉树 二叉树的几个重要性质 初识二叉树的几个操作函数  二叉树T: 一个有穷的节点

    2024年02月03日
    浏览(61)
  • 二叉树的相关操作

    本文的数据结构基于C语言练习。 C语言中的二叉树是一种数据结构,用于表示具有层次关系的数据集合。它由一个根节点开始,每个节点最多有两个子节点,分别称为左子节点和右子节点。 二叉树有许多相关性质,其中一些重要的包括: 深度:指从根节点到某个节点的路径

    2024年02月08日
    浏览(25)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包