二叉树中序遍历的非递归算法
二叉树的结点结构是:
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
你再对照的书上的算法想想,画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用,后执行完”,或者说“后调用,先执行完”。注意我加一个“完”字
在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构
总结先根遍历得到的非递归算法思想如下:
1)入栈,主要是先头结点入栈,然后visit此结点
2)while,循环遍历当前结点,直至左孩子没有结点
3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1)
先看符合此思想的算法:
[cpp] view plain copy print?
int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空,就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
//定义二叉树链式结构
typedef struct BitNode
{
char data; //数据域
struct BitNode *lchild,*rchild;//左右指针域
}BitNode,*BiTree;
//二叉树进行中序非递归遍历
void NRInorder(BiTree t)
{
BiTree s; //s-指向当前节点
BiTree stack[MAXNODE]; //定义栈
int top=-1; //初始化栈顶指针
if(t==NULL)
return;
stack[++top]=t;//根指针入栈
s=t->lchild; //s指向左子树
while(s!=NULL||top!=-1)//当存在节点(涉及到根下右子树)或者栈不为空,进行遍历
{
while(s!=NULL) //如果存在节点,寻找最左子树并入栈
{
if(top>=MAXNODE-1)
{
printf("栈为满\n");
return;
}
stack[++top]=s;//当前节点入栈
s=s->lchild; //左子树进行遍历
}
if(top==-1)
{
printf("栈为空\n");
return;
}
s=stack[top--]; //弹出栈顶元素到s中
printf("%c ",s->data); //输出当前节点元素值
s=s->rchild; //遍历右子树
}
}
推荐这篇文章,把二叉树的前序、中序和后续的递归和非递归算法都讲了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html
很简单啊 你就把这棵树看成是满二叉树就可以通过满二叉树的性质写出来了
非递归的二叉树前序遍历算法有什么用途
2.1 递归算法会有更多的资源需要压栈和出栈操作(不仅仅是参数,还有函数地址等)2.2 由于编译器对附加的一些栈保护机制会导致递归执行的更加低效 3. 使用循环代替递归算法,通常可以获得更好的执行效率和空间效率,在二叉树层次较深的情况下,采用非递归方式遍历能够有效的提升遍历的性能。
先序遍历二叉树的非递归算法栈是怎么工作的?
首先先序遍历二叉树 ,你要搞清楚访问先后顺序是:根节点->左子树->右子树;然后的话,栈就是把结点一个个压入栈中,碰到左子树中最左下角的结点的时候,从栈中取出一个结点(你可以理解为是往上一层,回到它的父节点那里去),然后检查有无右子树,有的话,继续压栈,依此类推。。。
非递归中序遍历二叉树:要求从键盘输入二叉树各结点的值,并使用二叉链表...
void MyTree::PrePrintf(TreeNode * lpCurNode,typefun lpfun){ MyStack<TreeNode *> stack;while(true){ while (lpCurNode){ if (lpfun!=NULL){ (this->*lpfun)(lpCurNode);stack.Push(lpCurNode);} lpCurNode=lpCurNode->m_lpLeft;} if (!stack.Pop(lpCurNode)){ break;} lpC...
程序改错:非递归先序遍历二叉树
printf("%c\\t",p->data);\/\/它的左子树访问完了,输出自身(中序嘛)p=p->rchild;\/\/开始访问右子树 } \/\/\/如果有右孩子,就以它为树根,重新循环 \/\/\/如果没有右孩子,且栈空(达到了下面一行的退出条件),说明树遍历完成,不能在进入if语句 }while(top>0||p!=null);\/\/--- \/\/---...
二叉树的遍历非递归算法中应注意哪些问题
进一步考虑:对于处理流程中的循环体的直到型、当型+直到型的实现。中序非递归算法 【思路】T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。问题:如何用栈来保存信息,使得在中序遍历过左子树后,能利用栈顶信息获取T指针?方法:先将T入栈,遍历左子树;遍历完左子树...
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉...
由前序遍历,C是二叉树的右根节点,由中序遍历,C不含左子节点,HF为C的右子节点。由前序遍历,F为H的根节点,由中序遍历,H为F的左子节点。在二叉树中,求后序遍历,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。则该二叉树的后序遍历是DGEBHFCA。
二叉树先序非递归遍历C语言算法
printf("先序非递归建立一个二叉树:"); if((ht=createprebitree())!=NULL) \/\/非递归建立 \/\/CreateBiTree(&ht); \/\/if(ht!=NULL) \/\/递归建立 { printf("先序遍历输出二叉树:"); preordertraverse(ht); putchar('\\n'); printf("中序遍历输出二叉树:"); inordertraverse(ht); putchar('\\n...
前序,中序,后序遍历子树,这三种在分别遍历左右子树的时候顺序为什么有的...
二叉树的遍历都是从根->左->右,的顺序的,只是在打印时有些方法会先把前面的保留到后面打印。非递归遍历方法就是用保留的方法实现的。搜索到结点和打印遍历结点的顺序是不同的,下面说一下遍历的特点。前序的特点:我们注意研究一下前序遍历的结果,你会发现,对于每个二叉树(只有根结点,左结点...
先序遍历和后序遍历是什么
2、首先访问根结点然后遍历左子树,最后遍历右子树,在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树;3、也称先根遍历、前序遍历。二、后序遍历 1、后序遍历是二叉树遍历的一种,有递归算法和非递归算法两种。在二叉树中,先左后右再根;2、后序遍历首先遍历左子树,然后...
建立二叉树,层序、先序、中序、后序遍历( 用递归或非递归的方法都需要...
char data;struct node *lchild,*rchild;}BinTNode; \/\/自定义二叉树的结点类型typedef BinTNode *BinTree; \/\/定义二叉树的指针int NodeNum,leaf; \/\/NodeNum为结点数,leaf为叶子数 \/\/===基于先序遍历算法创建二叉树=== \/\/===要求输入先序序列,其中加入虚结点"#"以示空指针的...
宏豪肝太: 有哪位高手帮忙分析下以下程序:#include"iostream.h" #define maxnode 100 typedef char datatype; typedef struct bitnode{ datatype data;//存储数据信息的信息域 struct bitnode *lchild,*rchild;//左右孩子指针 }bitnode,*bitree;void createbitree(...
霞山区18567942258: 二叉树中序遍历非递归算法(c语言实现) - ?
宏豪肝太: 把递归拆开,自己弄个栈来模拟递归就是了 貌似这种技巧没什么实际意义,不过还是写了吧#include <stdio.h> #define MAXN 100 /*节点的最大数量,姑且定为100*/ struct Node//二叉树节点 { int data; Node *left,*right; };Node *root;void Load(...
霞山区18567942258: 非递归中序遍历二叉树:要求从键盘输入二叉树各结点的值,并使用二叉链表来存储二叉树;使用非递归算法遍 - ?
宏豪肝太: 定义栈:stack 操作push(stack, l) 将l压栈 pop(stack,l) stack弹出并赋予l while(l != 0) { while(l->left != 0) {push(stack, l);l = l->left; }pop(stack, l); visit(l); l = l->right; }
霞山区18567942258: 二叉树中序遍历的非递归算法 - ?
宏豪肝太: #define MAXNODE 100 //二叉树最大节点数//定义二叉树链式结构 typedef struct BitNode { char data; //数据域 struct BitNode *lchild,*rchild;//左右指针域 }BitNode,*BiTree;//二叉树进行中序非递归遍历 void NRInorder(BiTree t) { BiTree s; //s-指向...
霞山区18567942258: 二叉树层次和中序遍历算法 - ?
宏豪肝太: 先序非递归算法 【思路】 假设:T是要遍历树的根指针,若T != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空. 问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针? 方法1:访...
霞山区18567942258: 二叉树的中序非递归遍历问题 - ?
宏豪肝太: case 6: {printf("中序非递归遍历 : "); in_order(T); //先序遍历 你这里为什么要写T而不是root呢?你的T指针要不是没有初始化的值,要不是就是空值,写在这里没有任何意义.如果是空值还好,你的in_order函数会退出,如果是未初始化的值,那么程序就会崩溃了 还有在定义指针类型变量的时候最好初始化 BinTree T = NULL,root = NULL; //初始化变量是个好习惯 int i,depth; printf("\n");
霞山区18567942258: 中序遍历二叉树非递归算法的完整程序代码??
宏豪肝太: #include "stdio.h" #include "stdlib.h" #include "string.h" #define null 0 struct node { char data; struct node *lchild; struct node *rchild; }; //先序,中序 建树 struct node *create(char *pre,char *ord,int n) { struct node * head; int ordsit; head=...
霞山区18567942258: 以二叉链表为存储结构,分别写出前序、中序、后序遍历二叉树的递归与非递归算法.(数据结构) - ?
宏豪肝太: #include<iostream.h> #include<stdlib.h>typedef char ElemType;struct BTreeNode {ElemType data;BTreeNode*left;BTreeNode*right; };void InitBTree(BTreeNode*& BT) {BT=NULL; } void CreateBTree(BTreeNode*& BT,char*a) {const int ...
霞山区18567942258: 二叉树的非递归遍历?要有讲解 不要纯程序~!! - ?
宏豪肝太: 我尽量写得详细一点,你再回去自己举个例子应该就容易明白了,这个遍历采用的是中序遍历. struct node{int data;struct node *lchild;struct node *rchild;}/*定义结点,lchild和rchild分别为左右孩子*/ void inorder(struct node *T) {struct node ...
霞山区18567942258: 求二叉树的遍历算法 - ?
宏豪肝太: 这里有一份以前从网上找到的C语言代码,自己测试过,没有问题,写的很好,分享给你,供参考: #include<stdio.h> #include<stdlib.h> #define STACKINITSIZE 100 #define STACKINCREASESIZE 20 typedef char ElemType; //树结构 typedef ...