二叉树后序遍历(非递归)
按照二叉树后序遍历的定义,无论是访问整颗树还是其子树均应该遵循选访问根结点的左子树,然后访问根结点的右子树,最后访问根结点的规律。因此对于一棵树(子树)t ,如果 t 非空,首先应该进入t的左子树访问,此时由于t的右子树及根结点尚未访问,因此必须将t保存起来,放入栈中,以便访问完左子树后,从栈中取出t,进行其右子树及根结点的访问。这里值得注意的是,当一个元素位于栈顶即将处理时,其左子树的访问一定已经完成,如果其右子树尚未遍历,接下来应该进入其右子树的访问,而此时该栈顶元素是不能出栈的,因为其根结点还未被访问;只有等到其右子树也访问完成后,该栈顶元素才能出栈,并输其根结点的值。因此,在二叉树后序遍历的过程中,必须使用seq.stack类型中的数组tag,其每个元素取值为0或1,用于标识栈中每个元素的状态。当一个元素刚进栈时,其对应的tag值置0;当它第一次位于栈顶即将被处理时,其tag值为0,意味着应该访问其右子树,于是将其右子树作为当前处理的对象,此时该栈顶元素仍应该保留在栈中,并将其对应的tag值改为1;当其右子树访问完成后,该元素又一次位于栈顶,而此时其tag值为1,意味着应该访问其根结点,并将其出栈。在整个二叉树后序遍历的过程中,程序要做的工作始终分成两个部分:当前正在处理的树(子树)和保存在栈中待处理的部分。只有这两部分的工作均完成后,程序方能结束。
(以上存手工输入)
后序遍历的非递归步骤类似于中序遍历,在遍历左子树前将根结点指针送入栈中
但是左子树遍历完成后,无法访问根结点,只有在右子树遍历完后,才能访问根结点
如果不使用标志位区分第几次到达根结点,可以利用如下的后序遍历特征来完成:
当栈顶元素(根)的右子树为空(即:无右孩子),或者是右子树非空但是已遍历完,即右孩子恰好是刚才访问过的结点,此时应访问栈顶结点,并在访问后退栈
否则,如果栈顶元素的右孩子非空且未遍历,此时直接访问栈顶元素的右孩子而不退栈
算法要点只是需要记住最近访问过的结点即可,也就是每次访问一个结点后,就记住这个结点
二,从最左边那个没有更左的那个节点,它位于栈顶,因为这时栈顶不是一个右节点,第二个循环跳过,然后把栈顶结点的右节点标记为r并以此作为根节点重复之前的操作
回溯:
因为一直往下层走,总会遇到既没有左节点有没有右节点的节点,就是叶子节点,就开始往回退 取他的右节点,取之前会把该节点标记为r,但是他没有右节点,为null,就会跳过第一个循环,来到第二个,那么这个叶子就从栈中pop掉,新的栈顶结点是那个叶子的父节点,如果没有右节点,那他就成了叶子,更简单,如果有右节点,那么继续二
一步一步推就是这样子,需要考虑所有情况,会把问题想复杂,但是利用递归的思想就好想了
参考递归算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一个函数就是第一个小循环,只走左边,然后把新得到的节点作为根节点,继续调用第一个函数,得到左节点,然后再作为根节点,直到左节点为空;
第二个函数就是最后一个if,非递归算法中是从栈顶取,就是左边走过了的节点,相当于递归中,第一个函数执行完已经返回,然后取他的右节点作为根节点,继续递归
以上回答你满意么?
后序遍历二叉树
后序遍历是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根。巧记:左右根。序遍历的非递归算法是三种顺序中最复杂的,原因在于,后序遍历是先访问左、右子树,再访问根节点,而在非递归算法中,利用栈回退到时,并...
数据结构与算法—二叉树的层序、前序中序后序(递归、非递归)遍历
数据结构与算法—二叉树的层序、前序中序后序遍历详解层序遍历是按层次顺序遍历二叉树,关键在于均衡处理左右子节点,因此,采用队列作为数据结构。其代码实现直观易懂,主要通过逐层添加节点到队列,然后依次取出处理。前序、中序和后序遍历则运用递归方法,类似于深度优先搜索。前序遍历规则是根节点 ->...
干货|二叉树的前序遍历、中序遍历、后序遍历。(递归和非递归)
二叉树的遍历方式包括前序、中序和后序三种。这三种遍历方法在数据结构中起着至关重要的作用。对于树的遍历,递归和非递归是两种常见的实现方式。前序遍历按照“根结点-左孩子-右孩子”的顺序访问节点。在递归实现中,首先访问根节点,然后分别递归地访问左子树和右子树。对于非递归实现,我们使用栈来...
数据结构之二叉树的前序遍历、中序遍历、后序遍历(C语言实现非递归)
1、非递归前序遍历 口诀:根左右。前序遍历首先访问根结点,然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根节点,然后遍历左子树,最后遍历右子树。1.1 具体流程 1.2 具体代码 2、非递归中序遍历 中序遍历是“左根右",即先遍历左子树节点,再遍历根节点,再遍历右子树节点 ...
带你一文看懂二叉树的先(中、后)序遍历以及层次遍历(图解+递归\/非递归...
理解二叉树的遍历方式,包括先序、中序、后序和层次遍历,关键在于掌握它们的访问顺序。先序遍历遵循"根-左-右"的顺序,即先访问根节点,再遍历左子树,最后遍历右子树。例如,给定的二叉树中,先序遍历序列是1 2 4 5 3 6 7。中序遍历则是"左-根-右",先遍历左子树,然后访问根节点,最后遍...
已知一颗二叉树,求后序遍历。
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是DGEBHFCA。前序遍历的第一个节点为根节点,由前序遍历可知,A为根节点。中序遍历的根节点前面的节点均为左子树的节点,所以左子树上的节点为DBGE。去掉根节点和左子树节点,右子数节点为CHF。前序遍历的第二个...
二叉树的遍历有几种方式?
1、先根遍历一般是先序遍历(Pre-order),按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中,先根后左再右。巧记:根左右。首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树,如果二叉树为空则返回。例如,下图所示...
求高手编写二叉树的非递归先序遍历和后序遍历的代码,要求和下面给出的...
{\/\/先序遍历二叉树T的递归算法 if(T){ if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;}else return OK;} void PostOrderTraverse(BiTree bt){\/\/后序遍历二叉树的递归算法 if(bt){ PostOrderTraverse(bt->lchild...
二叉树后序遍历(非递归)
一,大循环中的第一个循环,当前节点一直往左走一直走到头,并且把走过的节点压栈,这个循环遍历完成后,栈里面都是左边走过但是右边还没有走过的节点 二,从最左边那个没有更左的那个节点,它位于栈顶,因为这时栈顶不是一个右节点,第二个循环跳过,然后把栈顶结点的右节点标记为r并以此作为根节点...
怎么判断二叉树的根结点
判断二叉树根结点方法:1、前序遍历:一个输出的就是根节点;2、后序遍历:较后一个输出就是根节点;3、中序遍历:非递归情况可以控制栈的输出,若是层遍历,即一个输出的就是根节点。根结点:树的一个组成部分,也叫树根,所有非空的二叉树,都有且仅有一个根结点,它是同一棵树中除本身外...
旗皇阿苯: /*后序非递归遍历二叉树函数*/ Status PostOrderTree(BiTLink T){struct {BiTLink nodeptr[STACK_INIT_SIZE]; /*存放树中结点的指针*/int subtreetag[STACK_INIT_SIZE]; /*存放左右子树标志*/int top;}stack;stack.top=-1;do{while(...
池州市19777567683: 求二叉树的非递归后序遍历的c语言代码? - ?
旗皇阿苯: #include<iostream> #include<stdio.h> #define N 10 using namespace std;char *a;typedef struct NODE{char data;struct NODE *lch, *rch,*parent; } *BINTREE,Node;void visit(char data){ printf("%5c",data); }void preorder(BINTREE T){ // 先...
池州市19777567683: 二叉树后序遍历非递归算法程序跪求解释 - ?
旗皇阿苯: 一,大循环中2113的第一个循环,当5261前节点一直往左走一直走到头,并且4102把走过的节点压栈,这个循1653环遍历完成后,栈里面都是左边走过但是右边还没有走过的节点 二,从最左边那个没有更左的那个节点,它位于栈顶,因为这时...
池州市19777567683: 二叉树非递归后序遍历的思想是什么 越详细越好 急急!!!! - ?
旗皇阿苯: 按照二叉树后序遍历的定义,无论是访问整颗树还是其子树均应该遵循选访问根结点的左子树,然后访问根结点的右子树,最后访问根结点的规律.因此对于一棵树(子树)t ,如果 t 非空,首先应该进入t的左子树访问,此时由于t的右子树及根...
池州市19777567683: 二叉树非递归后序遍历的思路是什么 - ?
旗皇阿苯: 前序:根-左-右;中序:左-根-右;后序:左-右-根.遍历的思路有3个重点:1)利用堆栈实现递归2)树中结点要有指向父结点的指针 //后序遍历用不上这一条3)树中结点要有标志记录是否已被访问过 上述3点其实就是自己来完成原来递归实现...
池州市19777567683: 二叉树的后序遍历非递归算法 - ?
旗皇阿苯: typedef struct node { //定义树的结点 int data; struct node *left; struct node *right;} *btree;void AfterTraverseNotRecursive(node *root) //非递归后序遍历{ b...
池州市19777567683: 求一个二叉树的后序遍历非递归算法 - ?
旗皇阿苯: // 中序遍历伪代码:非递归版本,用栈实现,版本2 void InOrder2(TNode* root) { Stack S; if( root != NULL ) { S.push(root); } while ( !S.empty() ) { TNode* node = S.pop(); if ( node->bPushed ) { // 如果标识位为true,则表示其左右子树都已经入栈,...
池州市19777567683: 一个二叉树的后序遍历的非递归算法代码是多少?
旗皇阿苯: #include <stdio.h> #include <stdlib.h> //#include <conio.h> struct TREE //二叉树结点结构 { char data; struct TREE *lsubtree; struct TREE *Rsubtree; }; struct TREE *tree; void createtree(struct TREE *&p) //先序创建二叉树 { char ch; ch = getchar(); if (...
池州市19777567683: c语言 数据结构 非递归遍历二叉树 - ?
旗皇阿苯: /* 非递归法遍历二叉树 C语言 VC 6.0 */#include "stdio.h"#include "stdlib.h" typedef char Datatype; typedef struct BinTNode{ Datatype data; struct BinTNode *lchild, *rchild; }BinTree,*PBinTree; typedef struct stnode{ //栈的结构 Datatype data; ...
池州市19777567683: c++ 采用二叉链表作存储结构,实现二叉树非递归后序遍历算法 - ?
旗皇阿苯: 链接存储的二叉树类型和结构定义如下:typedef struct bnode { ElemType data; struct bnode *lchild, *rchild; } btree; 后序遍历 void postorder(btree *bt) { btree *p=bt, *stack[MAX];//p表示当前结点,栈stack[]用来存储结点int tag[MAX]; int ...