.
先序遍历二叉树的递归算法怎样理解
二叉树的结点结构是:
1、根结点(存放结点数据)
2、左子树指针
3、右子树指计
对二叉树的遍历就是访问各个结点中根结点里存放的数据。例如:
如果结点A有左结点B,右结点C,记作A(B,C),不同结点我用"\"隔开。那么有这样一个(BitTree)二叉树表A(B,C) \B(D,E)\E(F.G)\C(空,H)\H(I.空), 自己画出来,不然我后面白讲了。
要想把所有的数据都访问到则必需按照一定的原则,即当前结点的下一个结点是哪个结点。
无论是先、中还是后序算法都是先将左结点视为下一个结点,当左结点不存在(即为空时)才将右结点视作下一个结点,如果右结点也不存在就返回当前结点的上层结点再向右访问,如此类推。
于是对二叉树的遍历问题就被抽象成三个基本步骤:
1、访问根结点。
2、访问该点的所有左子树。
3、访问该点的所有右子树。
先序遍历的策略是按123的步骤执行,中序是按213来,后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。
看着你刚画好的那个BitTree跟着我的思路走。在先序遍历算法PriorOrder中,先将BitTree的头结点A传进来,按步骤123的处理。123是抽象实现,记住所表达的思想,下面是具体实现。为了避免混乱用中文数字记录步骤。
一、即是读取结点A的数据内容A(此时A为当前函数处理结点),将A的右结点C放入栈S中,S中的内容为S(C)[注意这一步是算法的一个辅助,并不是先向右访问,下同],将左结点B传给PriorOrder处理。此时读取了A
二、读取B的内容B(此时B为当前结点),将B的右结点E放入S中,S中的内容为S(C,E),将B的左结点D传给PriorOrder处理。此时读取了AB
三、D为当前结点,D的右为空没有东西放入S,S中的内容仍为S(C,E),D的左也为空,没有访问可访问的。此时就从S中取出E(因为栈是先进后出的所以取的就是E,此时S中的内容为S(C),正好是上一层没访问过的右子树),将E传给PriorOrder处理。此时读取了AB D
四、E为当前结点,对于结点E类似的有S(C,G),读取了ABDE,将F传入PriorOrder
五、F为当前结点,右为空,左也为空,读取了ABDEF,从栈中取出G传给PriorOrder处理,S的内容为S(C);
六、类似的读取了ABDEFG,从S中取出了C,传给PriorOrder处理。此时S()。
七、当前结点为C,从将C的右结点放入S,S中内容为S(H),C的左为空,从S取出H,将H传给PriorOrder处理。此时S为S().于是就读取了ABDEFGC
八,类似的读取了ABDEFGCH
九,最后ABDEFGCHF
你再对照的书上的算法想想,画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用,后执行完”,或者说“后调用,先执行完”。注意我加一个“完”字
.
分享到:
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
本文将详细介绍二叉树的先序遍历非递归算法,包括其原理、实现代码和相关知识点。 知识点1:二叉树的概念 二叉树是一种特殊的树形结构,每个节点最多有两个孩子节点:左孩子和右孩子。二叉树可以用于表示各种树形...
编写先序遍历二叉树的非递归算法程序,要求: (1)以二叉链表建立二叉树。 (2)输出遍历的结点序列。 (3)有实例验算。
根据给定的信息,本文将详细解释三种二叉树非递归遍历算法的实现方法:先序遍历、中序遍历以及后序遍历,并重点介绍先序遍历的非递归算法在C语言中的具体实现。 ### 先序遍历非递归算法(C语言) #### 1. 算法概述...
### 二叉树先序、中序、后序遍历非递归算法 #### 前言 在计算机科学中,二叉树是一种常见的数据结构,它被广泛应用于各种算法和程序设计中。二叉树的遍历是理解并操作二叉树的基础,通常有三种主要的遍历方式:...
先序遍历是一种遍历二叉树的基本方法,它按照“根-左-右”的顺序访问树中的每一个节点。在二叉树的遍历中,通常有三种方式:前序遍历、中序遍历和后序遍历。先序遍历在数据结构和算法领域中有着广泛的应用,例如在...
先序遍历非递归算法 先序遍历是一种典型的深度优先搜索策略,其顺序是“根节点 -> 左子树 -> 右子树”。非递归实现主要依赖于辅助栈来保存遍历过程中的节点信息。 ```c #define maxsize 100 typedef struct { ...
"按层次遍历二叉树的算法" 按层次遍历二叉树的算法是指从树的根结点开始,逐层遍历树的所有结点,直到遍历完整个树。这种遍历方式可以分为两种:宽度优先遍历(Breadth-First Traversal)和深度优先遍历(Depth-...
接下来,我们讨论遍历二叉树的方法。主要有三种遍历方式:前序遍历、中序遍历和后序遍历。对于本问题,我们关注的是层序遍历和前序遍历。 层序遍历,也叫广度优先遍历,按照从上到下、从左到右的顺序访问每一层的...
用户以先序遍历的方式键入二叉树各结点的数据域值(字符型),程序建立二叉树,然后分别用递归和非递归算法对二叉树进行遍历。每访问一个结点即打印该结点的数据域值。
//二叉树的二叉链表存储表示 typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; //左右孩子指针 } BiTNode, *BiTree; typedef struct { BiTree *base; BiTree *top; int stacksize; //当前...
递归遍历是指使用递归函数来遍历二叉树的每个结点。递归遍历的优点是代码简洁易懂,但缺点是可能会导致堆栈溢出。在本文的示例代码中,我们使用了递归函数来实现先序遍历、中序遍历和后序遍历。 先序遍历是指先访问...
总之,中序遍历二叉树的非递归算法是IT专业人员必须掌握的核心技能之一,它不仅加深了对数据结构的理解,还提高了处理实际问题的能力。通过不断实践和探索,可以进一步提升算法的效率和灵活性。
二叉树三种遍历非递归算法 二叉树是一种常用的数据结构,它广泛应用于计算机科学和软件工程中。二叉树的遍历是指对二叉树中的每个结点进行访问的过程。常见的二叉树遍历方法有三种:先序遍历、中序遍历和后序遍历。...
`:用先序遍历算法遍历二叉树。 - `voidmidorder(const BiTree bt);`:用中序遍历算法遍历二叉树。 - `voidlasorder(const BiTree bt);`:用后序遍历算法遍历二叉树。 - `intLayerTraval(BiTree bt);`:层次遍历...
递归算法的基本思想是将问题分解为更小的子问题,直至子问题可以直接解决,然后将结果合并以得到原问题的解。 以下是一个简单的C语言实现先序遍历的代码示例: ```c #include // 定义二叉树节点 typedef struct ...
遍历二叉树有多种方法,其中前序、中序和后序遍历是最常见的三种。通常,这些遍历算法是以递归方式实现的,但递归虽然简洁,却可能带来栈溢出的问题,尤其是在处理大规模数据时。因此,了解和掌握二叉树的非递归遍历...