二叉树相关操作---纯代码实现详解

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

目录

前言 (很重要)

二叉树的概念

二叉树的相关术语

相关操作菜单

  二叉树的构造

 创建二叉树

先序遍历二叉树  

 中序遍历二叉树

 后序遍历二叉树

 层次遍历二叉树

 二叉树的深度

 二叉树的叶子结点数

 二叉树的结点数

整体代码

结果展示

结束语


前言 (很重要)

        大家好,今天给大家带来的是二叉树的相关操作,希望能够给大家带来帮助。

        另外有很多小伙伴们在学习算法的时候,只去学习一些关于算法理论的知识,并不知道自己的代码实战能力如何也不清楚到底对该算法的了解有多深,所以在这里小张给大家推荐一个很棒的平台,在这里有很多的面试和算法题,也有很多的面试和求职的机会,大家可以点击下方链接进入牛客网刷算法真题,提高自己代码实战能力,早日拿到满意的offer!点击这里进入牛客网刷算法和面试真题提高代码实战能力

二叉树的概念

        二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分 。

二叉树的相关术语

①节点:包含一个数据元素及若干指向子树分支的信息 。

②节点的度:一个节点拥有子树的数目称为节点的度 。

③叶子节点:也称为终端节点,没有子树的节点或者度为零的节点 。

④分支节点:也称为非终端节点,度不为零的节点称为非终端节点 。

⑤树的度:树中所有节点的度的最大值 。

⑥节点的层次:从根节点开始,假设根节点为第1层,根节点的子节点为第2层,依此类推,如果某一个节点位于第L层,则其子节点位于第L+1层 。

⑦树的深度:也称为树的高度,树中所有节点的层次最大值称为树的深度  。

相关操作菜单

//菜单
void menu()
{
	cout << "\t\t\t******************************************************************" << endl;
	cout << "\t\t\t****************  1.输入-1  退出程序           *******************" << endl;
	cout << "\t\t\t****************  2.输入1   初始化二叉树       *******************" << endl;
	cout << "\t\t\t****************  3.输入2   对二叉树先序遍历   *******************" << endl;
	cout << "\t\t\t****************  4.输入3   对二叉树中序遍历   *******************" << endl;
	cout << "\t\t\t****************  5.输入4   对二叉树后序遍历   *******************" << endl;
	cout << "\t\t\t****************  6.输入5   对二叉树层次遍历   *******************" << endl;
	cout << "\t\t\t****************  7.输入6   二叉树深度         *******************" << endl;
	cout << "\t\t\t****************  8.输入7   二叉树叶子结点数   *******************" << endl;
	cout << "\t\t\t****************  9.输入8   二叉树的结点数     *******************" << endl;
	cout << "\t\t\t******************************************************************" << endl;
}

  二叉树的构造

//构造二叉树
typedef struct Binode
{
	//数据域
	char data;
	//定义左孩子和右孩子
	struct Binode*lchid, *rchid;
}Binode, *StrBinode;

 创建二叉树

//先序遍历创建二叉树
void creatBinode(StrBinode&T)
{
	cin >> ch;
	if (ch == '#')
	{
		//如果输入是#的话就说明根结点就是叶子结点
		//就没必要再去进行开辟一个二叉树空间
		T = NULL;
	}
	else
	{
		T = new Binode;
		T->data = ch;
		creatBinode(T->lchid);
		creatBinode(T->rchid);
	}
}

先序遍历二叉树  

//先序遍历二叉树
void visitBinode(StrBinode&T)
{
	if (T!=NULL)
	{
		cout << T->data << " ";
		visitBinode(T->lchid);
		visitBinode(T->rchid);
	}
	if(T==NULL)
	{
		cout << "#" << " ";
	}
}

 中序遍历二叉树

//中序遍历二叉树
void MidvisitBinode(StrBinode&T)
{
	if (T != NULL)
	{
		visitBinode(T->lchid);
		cout << T->data << " ";
		visitBinode(T->rchid);
	}
	if (T == NULL)
	{
		cout << "#" << " ";
	}
}

 后序遍历二叉树

//后序遍历二叉树
void BackvisitBinode(StrBinode&T)
{
	if (T != NULL)
	{
		visitBinode(T->lchid);
		visitBinode(T->rchid);
		cout << T->data << " ";
	}
	if (T == NULL)
	{
		cout << "#" << " ";
	}
}

 层次遍历二叉树

//二叉树的层次遍历
void Levelorder(StrBinode&HT)
{
	StrBinode T;
	T = new Binode;
	//创建一个队列qu
	queue<StrBinode> qu;
	//将根结点的指针压入队列
	qu.push(HT);
	//当队列不为空的时候就继续进行循环
	while (!qu.empty())
	{
		//让T里面存放队列中第一个元素的值
		T = qu.front();
		//C++自带的队列出队的话是删除值不返回值
		qu.pop();
		//访问出队元素的值
		cout << T->data << " ";
		//当该节点左孩子不为空的时候就让左孩子入队
		if (T->lchid != NULL)
		{
			qu.push(T->lchid);
		}
		//当该节点右孩子不为空的时候就让左孩子入队
		if (T->rchid != NULL)
		{
			qu.push(T->rchid);
		}
	}
	
}

 二叉树的深度

//二叉树的深度
int deep(StrBinode&T)
{
	if (T == NULL)
	{
		return 0;
	}
	else
	{
		int m = deep(T->lchid);
		int n = deep(T->rchid);
		if (m > n)
		{
			return (m + 1);
		}
		else
		{
			return (n + 1);
		}
	}
}

 二叉树的叶子结点数

//求二叉树的叶子结点
int leaf(StrBinode&T)
{
	//如果是空树
	if (T == NULL)
	{
		//返回0
		return 0;
	}
	//如果是叶子结点
	if (T->lchid == NULL && T->rchid == NULL)
	{
		//返回1
		return 1;
	}
	return leaf(T->lchid) + leaf(T->rchid);
}

 二叉树的结点数

//求二叉树的结点数
int Nodecount(StrBinode&T)
{
	//如果是根结点没有数据
	if (T == NULL)
	{
		return 0;
	}
	else
	{
		return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
	}
}

整体代码

#include<iostream>
#include<queue>
using namespace std;
char ch = 0;

//构造二叉树
typedef struct Binode
{
	//数据域
	char data;
	//定义左孩子和右孩子
	struct Binode*lchid, *rchid;
}Binode, *StrBinode;

//先序遍历创建二叉树
void creatBinode(StrBinode&T)
{
	cin >> ch;
	if (ch == '#')
	{
		//如果输入是#的话就说明根结点就是叶子结点
		//就没必要再去进行开辟一个二叉树空间
		T = NULL;
	}
	else
	{
		T = new Binode;
		T->data = ch;
		creatBinode(T->lchid);
		creatBinode(T->rchid);
	}
}

//先序遍历二叉树
void visitBinode(StrBinode&T)
{
	if (T!=NULL)
	{
		cout << T->data << " ";
		visitBinode(T->lchid);
		visitBinode(T->rchid);
	}
	if(T==NULL)
	{
		cout << "#" << " ";
	}
}

//中序遍历二叉树
void MidvisitBinode(StrBinode&T)
{
	if (T != NULL)
	{
		visitBinode(T->lchid);
		cout << T->data << " ";
		visitBinode(T->rchid);
	}
	if (T == NULL)
	{
		cout << "#" << " ";
	}
}

//后序遍历二叉树
void BackvisitBinode(StrBinode&T)
{
	if (T != NULL)
	{
		visitBinode(T->lchid);
		visitBinode(T->rchid);
		cout << T->data << " ";
	}
	if (T == NULL)
	{
		cout << "#" << " ";
	}
}

//二叉树的层次遍历
void Levelorder(StrBinode&HT)
{
	StrBinode T;
	T = new Binode;
	//创建一个队列qu
	queue<StrBinode> qu;
	//将根结点的指针压入队列
	qu.push(HT);
	//当队列不为空的时候就继续进行循环
	while (!qu.empty())
	{
		//让T里面存放队列中第一个元素的值
		T = qu.front();
		//C++自带的队列出队的话是删除值不返回值
		qu.pop();
		//访问出队元素的值
		cout << T->data << " ";
		//当该节点左孩子不为空的时候就让左孩子入队
		if (T->lchid != NULL)
		{
			qu.push(T->lchid);
		}
		//当该节点右孩子不为空的时候就让左孩子入队
		if (T->rchid != NULL)
		{
			qu.push(T->rchid);
		}
	}
	
}

//二叉树的深度
int deep(StrBinode&T)
{
	if (T == NULL)
	{
		return 0;
	}
	else
	{
		int m = deep(T->lchid);
		int n = deep(T->rchid);
		if (m > n)
		{
			return (m + 1);
		}
		else
		{
			return (n + 1);
		}
	}
}

//求二叉树的叶子结点
int leaf(StrBinode&T)
{
	//如果是空树
	if (T == NULL)
	{
		//返回0
		return 0;
	}
	//如果是叶子结点
	if (T->lchid == NULL && T->rchid == NULL)
	{
		//返回1
		return 1;
	}
	return leaf(T->lchid) + leaf(T->rchid);
}

//求二叉树的结点数
int Nodecount(StrBinode&T)
{
	//如果是根结点没有数据
	if (T == NULL)
	{
		return 0;
	}
	else
	{
		return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
	}
}

//菜单
void menu()
{
	cout << "\t\t\t******************************************************************" << endl;
	cout << "\t\t\t****************  1.输入-1  退出程序           *******************" << endl;
	cout << "\t\t\t****************  2.输入1   初始化二叉树       *******************" << endl;
	cout << "\t\t\t****************  3.输入2   对二叉树先序遍历   *******************" << endl;
	cout << "\t\t\t****************  4.输入3   对二叉树中序遍历   *******************" << endl;
	cout << "\t\t\t****************  5.输入4   对二叉树后序遍历   *******************" << endl;
	cout << "\t\t\t****************  6.输入5   对二叉树层次遍历   *******************" << endl;
	cout << "\t\t\t****************  7.输入6   二叉树深度         *******************" << endl;
	cout << "\t\t\t****************  8.输入7   二叉树叶子结点数   *******************" << endl;
	cout << "\t\t\t****************  9.输入8   二叉树的结点数     *******************" << endl;
	cout << "\t\t\t******************************************************************" << endl;
}

int main()
{
	int n = 0;
	StrBinode T;
	menu();
	while (cin >> n)
	{
		if (n < 0)
		{
			break;
		}
		switch (n)
		{
		case 1:
			//初始化二叉树
			cout << "请输入值对二叉树进行初始化" << endl;
			creatBinode(T);
			cout << "初始化完成" << endl;
			break;
		case 2:
			//先序遍历
			cout << "先序遍历的结果为" << endl;
			visitBinode(T);
			cout << "先序遍历结束" << endl;
			break;
		case 3:
			//中序遍历
			cout << "中序遍历的结果为" << endl;
			MidvisitBinode(T);
			cout << "中序遍历结束" << endl;
			break;
		case 4:
			//后序遍历
			cout << "后序遍历的结果为" << endl;
			BackvisitBinode(T);
			cout << "后序遍历结束" << endl;
			break;
		case 5:
			//层次遍历
			cout << "层次遍历的结果为" << endl;
			Levelorder(T);
			cout << "层次遍历结束" << endl;
			break;
		case 6:
			cout << "二叉树的深度为:";
			cout << deep(T) << endl;
			break;
		case 7:
			cout << "二叉树的叶子结点数为:";
			cout << leaf(T) << endl;
			break;
		case 8:
			cout << "二叉树的结点数为;";
			cout << Nodecount(T) << endl;
			break;
		default:
			cout << "您的输入有误,请重新输入" << endl;
			break;
		}
	}
	return 0;
}

结果展示

二叉树相关操作---纯代码实现详解二叉树相关操作---纯代码实现详解

结束语

        到这里今天的内容就已经全部结束了,这里的代码是运用C++语言实现的,其他语言的话也大同小异,只要相关的思想掌握了,就能写出来相应的代码最后小张在这里感谢大家的支持 !文章来源地址https://www.toymoban.com/news/detail-408755.html

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

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

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

相关文章

  • 数据结构:二叉树及相关操作

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

    2024年02月11日
    浏览(44)
  • 【数据结构】【算法】二叉树、二叉排序树、树的相关操作

    树结构是以分支关系定义的一种层次结构,应用树结构组织起来的数据,逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。 树 Tree 是由n个节点组成的有限集合。在任意一颗非

    2024年02月04日
    浏览(50)
  • 【数据结构】二叉树的相关操作以及OJ题目

    当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因

    2024年03月19日
    浏览(48)
  • 链式二叉树及相关操作(前,中,后,层序遍历)

    欢迎来到 Claffic 的博客  💞💞💞 “春来无事,只为花忙。” 前言: 上一期给大家介绍了二叉树的一种顺序结构:堆,这一期承接上一期,给大家继续介绍二叉树的另一种结构:链式结构。 目录 🐽Part1:链式二叉树?  1.前情提要  2.创建一颗二叉树 🐷Part2:相关操作实现 1

    2023年04月16日
    浏览(30)
  • 【数据结构】——树和二叉树相关概念(全网超级详解)

       创作不易,家人们来一波三连吧?! 世界上最大的树--雪曼将军树,这棵参天大树不是最长也不是最宽,是不是很奇怪,大只是他的体积是最大的,看图片肯定是感触不深,大家可以自己去看看  扯远了,这次我们介绍的是一种新的数据结构--树 之前的栈和队列,都是一

    2024年04月08日
    浏览(67)
  • 【二叉树】大学有棵树叫高数,数据结构也有棵二叉树-代码详解

    普通二叉树增删查改没有什么价值,因为用来存数据,太复杂了 价值体现 1.搜索二叉树(最多查找高度次) ,平衡搜索二叉树,ALV树 红黑树 B 树 -最坏情况O(N) 2.哈夫曼树 二叉树结构 以存放字符为例子 快速构建一颗二叉树 树的结构 前序遍历 前序遍历(Preorder Traversal 亦称先序遍

    2023年04月08日
    浏览(41)
  • 【树与二叉树】二叉树顺序结构实现以及堆的概念及结构--详解介绍

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 普通二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而 完全二叉树适合使用顺序结构存储 。现实中我们通常把 堆

    2023年04月24日
    浏览(40)
  • 递归详解,斐波那契数列、二叉树遍历、汉诺塔问题的递归代码

    一、递归详解 [1] 递归是一种编程技巧,通过函数调用自身来解决问题。递归中包含三个要素:递归定义、递归出口和递归调用。 [2] 递归定义指的是问题可以被分解为同类且更小规模的子问题。在递归过程中,问题会不断被分解为规模更小的子问题,直到达到一个基本情况,

    2024年02月08日
    浏览(38)
  • 【数据结构】二叉树链式结构的实现及其常见操作

    目录 1.手搓二叉树 2.二叉树的遍历 2.1前序、中序以及后序遍历 2.2二叉树的层序遍历 3.二叉树的常见操作 3.1求二叉树节点数量 3.2求二叉树叶子节点数量 3.3求二叉树第k层节点个数 3.3求二叉树的深度 3.4二叉树查找值为x的节点 4.二叉树的销毁 在学习二叉树的基本操作前,需先要

    2024年02月12日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包