首页 > 其他分享 >二叉树遍历的操作与实现

二叉树遍历的操作与实现

时间:2023-03-04 21:35:46浏览次数:48  
标签:Status 结点 遍历 return Visit 二叉树 操作 rchild

先序遍历

先序遍历(递归版)
代码展示
/*
先序遍历(递归版)
*/
Status PreOrderTraverse(BiTree T, Status Visit(TElemType e)) {
	if (T)
	{
		Visit(T->data);
		PreOrderTraverse(T->lchild, Visit);
		PreOrderTraverse(T->rchild, Visit);
	}
	return SUCCESS;
}
思路解析

先序遍历,首先判断二叉树T是否为空,若为空则代表二叉树已遍历完成。若非空则代表该结点有值,然后调用Visit方法将结点值打印出来。随后再寻找该结点的左右子结点,再重复上述步骤实现先序遍历。

先序遍历(非递归版)
代码展示
/*
先序遍历(非递归版)
*/
Status PreOrderTraverseStore(BiTree T, Status Visit(TElemType e)) {
	if (T == nullptr)
	{
		return ERROR;
	}
	BiTree p;
	LinkStack S;
	InitStack(S);
	Push(S, T);//根进栈
	while (!StackEmpty(S))
	{
		while ((GetTop(S, p) && p)) {
			if (!Visit(p->data))
			{
				return ERROR;
			}
			Push(S, p->lchild);//左走到尽头
		}
		Pop(S, p);//空指针退栈
		if (!StackEmpty(S))//访问结点
		{
			Pop(S, p);
			Push(S, p->rchild);
		}
	}
	return SUCCESS;
}
思路解析

非递归版是采用栈来实现,初始化将原始二叉树赋值给p,然后让其入栈。之后遍历其左子树所有结点,左子树结点遍历完成后,弹出空指针栈顶,开始遍历右子树结点。每遍历一次便将新的头结点二叉树压入栈中。

中序和后序遍历

中序遍历及后序遍历(递归版)
代码展示
/*
中序遍历
*/
Status InOrderTraverse(BiTree T, Status Visit(TElemType e)) {
	if (T != nullptr)
	{
		InOrderTraverse(T->lchild, Visit);
		Visit(T->data);
		InOrderTraverse(T->rchild, Visit);
	}
	return SUCCESS;
}
/*
后序遍历
*/
Status PostOrderTraverse(BiTree T, Status Visit(TElemType e)) {
	if (T != nullptr)
	{
		PostOrderTraverse(T->lchild, Visit);
		PostOrderTraverse(T->rchild, Visit);
		Visit(T->data);
	}
	return SUCCESS;
}
中序遍历和后序遍历(非递归版)
代码展示
/*
中序遍历(非递归)
*/
Status InOrderTraverseStore(BiTree T, Status Visit(TElemType e)) {
	if (T == nullptr)
	{
		return ERROR;
	}
	BiTree p;
	LinkStack S;
	InitStack(S);
	Push(S, T);
	while (!StackEmpty(S))
	{
		while (GetTop(S, p) && p) {
			Push(S, p->lchild);	//左子树走到尽头
		}
		Pop(S, p);	//空指针退栈
		if (!StackEmpty(S))
		{
			Pop(S, p);
			if (!Visit(p->data))	//访问结点
			{
				return ERROR;
			}
			Push(S, p->rchild);
		}
	}
	return SUCCESS;
}

/*
后序遍历(非递归版)
*/
Status PostOrderTraverseStore(BiTree T, Status(*Visit)(TElemType e)) {
	if (T == nullptr)
	{
		return ERROR;
	}
	BiTree p = T, r = nullptr;
	LinkStack S;
	InitStack(S);
	while (p != nullptr || !StackEmpty(S))
	{
		if (p)
		{
			Push(S, p);
			p = p->lchild;
		}
		else
		{
			GetTop(S, p);
			if (p->rchild && p->rchild != r)
			{
				p = p->rchild;
				Push(S, p);
				p = p->lchild;
			}
			else
			{
				Pop(S, p);
				Visit(p->data);
				r = p;
				p = nullptr;
			}
		}
	}
	return SUCCESS;
}
思路解析

中序和后序遍历与先序遍历差别不大,只是在与父结点的顺序有关。父结点在最前即为先序遍历,父结点在左右子结点中便是中序遍历,父结点在左右子结点之后便是后序遍历。代码实现类似,使用递归或栈来实现。

层次遍历

代码展示
/*
层次遍历
*/
Status LevelOrderTraverse(BiTree& T) {
	LinkQueue lq;
	InitQueue(lq);
	QElemType q;
	EnQueue(lq, T);
	while (QueueEmpty(lq) != SUCCESS)	//对列不空,则出队
	{
		DeQueue(lq, q);
		printf("%c ", q->data);
		if (q->lchild)
		{
			EnQueue(lq, q->lchild);	//若有左孩子,则入队
		}
		if (q->rchild)
		{
			EnQueue(lq, q->rchild);	//若有右孩子,则入队
		}
	}
	return SUCCESS;
}
思路解析

层次遍历使用队列来进行遍历,首先原始二叉树入队,然后退队,打印结点值。查询该结点是否有左右子结点,若有则入队。循环往复上述步骤,当队列为空时,则层次遍历完成。

标签:Status,结点,遍历,return,Visit,二叉树,操作,rchild
From: https://www.cnblogs.com/homeskating/p/17179202.html

相关文章

  • wsl2出现参考的对象类型不支持尝试的操作的解决方法(win11 永久解决)
    前言更新WIN11后,之前的解决办法不起作用了~之前的解决办法参考:http://blog.happyjava.cn/articles/2e955c6794db474fa08b7bcde6e1dd2c/<!--more-->新的解决办法新的......
  • ES6-ES11 迭代器应用-自定义遍历数据
    原视频<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><titl......
  • 操作系统(1.1)--引论
    目录​​一、操作系统的目标和作用​​​​1.操作系统的目标 ​​​​2.操作系统的作用 ​​​​2.1 OS作为用户与计算机硬件系统之间的接口​​​​2.2OS作为计算机系......
  • 1.服务器系统进行初始化操作
    1.准备3台服务器,系统是centos7关闭3台服务器防火墙systemctlstopfirewalld//临时关闭systemctldisablefirewalld//永久关闭systemctlstatusfirewalld//查看......
  • 操作系统课程笔记
    第一章课后作业在操作系统中,并发性是指若干事件(某一时间间隔内)发生。操作系统结构设计中,层次结构的最大特点是(有利于功能的增加、删减和修改)。操作系统在计算机系......
  • c# 操作注册表
    C#读、写、删除注册表 1.首先,必须导入空间"Microsoft.Win32" 2.利用Registry类,确定注册表的分支(ClassesRoot,CurrentUser,Users,LocalMachine,CurrentConfig)usi......
  • X86平台:多任务操作系统在X86保护模式下两种内存模型下的工作模式及其设计
        本文于2023/3/2,开始写作,因为内容太多了,所以暂时只能拟出标题,我可以根据这个标题进行复习,学习过相关知识的同学也可以根据题目复习。    自学了李忠老......
  • 系统性能问题,不间断慢,所有操作都慢
    排查方法:一般先看服务器的cpu、内存、硬盘读写是否异常;站点是否频繁重启;iis设置是否有不合理的;系统的日志是否异常;看下服务器的日志是否有报错;看下数据库活动监控情......
  • 7.如何处理循环的异步操作
    functiongetMoney(){varmoney=[100,200,300]for(leti=0;i<money.length;i++){compute.exec().then(()=>{console.log(money[i])......
  • js遍历数组和遍历对象属性
    遍历数组letjson={key1:"hello",key2:"world"}//最简洁方法for(letkeyinjson){console.log(key,":",j......