山东青岛网站建设seo优化,wordpress首页置顶推荐问题,遵义住房城乡建设厅网站,百度网址大全 官网提示#xff1a;本篇章主要讲解数据结构中树的相关知识。 文章目录 二叉树的遍历为什么要提出这么多遍历方法#xff1f;先根遍历二叉树#xff08;TLR#xff09;先根遍历二叉树的递归算法#xff08;重点#xff09;先根遍历二叉树的非递归算法(了解#xff0c;但是得… 提示本篇章主要讲解数据结构中树的相关知识。 文章目录 二叉树的遍历为什么要提出这么多遍历方法先根遍历二叉树TLR先根遍历二叉树的递归算法重点先根遍历二叉树的非递归算法(了解但是得会写很有可能找工作的时候让写一个非递归的)先根遍历二叉树的非递归算法 二叉树的遍历
遍历二叉树是指以某种次序访问二叉树中的每个结点并且每个结点仅被访问一次.(沿着某条搜索路线依次访问每个结点)
这里“访问”的含义很广访问结点所做的操作依赖于具体的应用问题。假设遍历时访问结点仅是输出结点数据域的值那么遍历的结果将是得到一个线性序列。 由于二叉树有左、右子树所以遍历的次序不同得到的结果就会不同。 假设 L、T、R 分别代表左子树、根结点、右子树 对一棵二叉树的遍历可以有6种不同的次序TLR、TRL、LTR、RTL、LRT、RLT 如果限定先左后右那么只有三种访问顺序TLR、LTR、LRT。分别称作先根遍历中根遍历后根遍历又称前序遍历中序遍历后序遍历
为什么要提出这么多遍历方法
完全是不同的应用角度出发的。
例如要判断两个二叉树是否相等只要子树的根结点不同那么就不等显然这是可以用先根遍历实现
例如删除二叉树时必须先删除其左、右子树然后才能删除根结点这时就要用后根遍历实现。 可以在具体应用中对遍历方法好好体会接下来进入正题。
先根遍历二叉树TLR
先根遍历二叉树的递归定义为 若二叉树非空则 (1)访问根结点(2)按先根次序遍历左子树(3)按先根次序遍历右子树 否则遍历结束。 简易口诀根左右 如下图所示
※先根遍历的顺序为ABDEGCF
先跟遍历abdgcefhi
先根遍历二叉树的递归算法重点
将访问根结点的操作简化为输出根结点的值
void Preorder ( BTNode * bt )
{ /* 先根遍历以bt为根的二叉树 */ if (bt) {printf(bt-data); /*访问根结点*/ Preorder( bt-lchild ); /*先根遍历左子树*/ Preorder( bt-rchild ); /*先根遍历右子树*/ }}先根遍历二叉树的非递归算法(了解但是得会写很有可能找工作的时候让写一个非递归的) 逻辑过程如下 对于先根遍历二叉树而言在访问根结点之后可以直接找到这个根的左子树进行遍历但是当左子树遍历完毕之后还必须沿着已经走过的路线返回到根结点再通过根结点才能找到它的右子树。 因此在从根结点走向它的左孩子结点之前必须根结点的地址存入栈中暂存起来。
左子树遍历完毕之后再按照后进先出的原则取回栈顶元素才能找到根结点的地址最后遍历根的右子树。 先根遍历二叉树的非递归算法
void Preorder2 ( BTNode *bt )
{
p bt;
InitStack(s);while ( p || !StackEmpty(S) ) { if (p) /*二叉树非空*/ { printf(p-data) ; /*访问根结点*/ Push( s, p ) ; /*根指针进栈*/ p p-lchild ; /*p移向左孩子*/ } else /*栈非空*/ {Pop ( s , p ) ; /*双亲结点出栈/* p p-rchild ; /*p移向右孩子*/ }}
}
