二叉树中序遍历递归算法

怎样实现二叉树的前序遍历的非递归算法~

在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
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;
}

真正实用编程中，也没有必要太计较。

if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
以上就是中序遍历二叉树
这段程序我全有，具体如下：
#include <alloc.h>

#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;

typedef int ElemType;
typedef int Status;
typedef int KeyType;

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))

typedef struct BinaryTree //定义二叉树
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;//

BiNode * new()//为新结点开辟空间
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}

CreateSubTree(BiTree *T,ElemType *all,int i)//创建新有子树
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}

CreateBiTree(BiTree *T)//创建新结点
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}

printelem(ElemType d)//输出
{
printf("%d\n",d);
}

PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))//前序遍历
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}

InOrderTraverse(BiTree T,int (*Visit)(ElemType d))//中序遍历
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}

Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){

if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}

Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}

void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {

/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/

q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;

}
}

Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}

main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}

把Visit往下移一行就行了。也就是先遍历lchild，再Visit，最后遍历rchild。

---

章贡区18256667670： 中序递归遍历二叉树的算法?(数据结构) - ？
谭星长春： #include<stdio.h> #include <malloc.h> #define maxsize 100 typedef char elemtype; typedef struct Node {elemtype data;struct Node *lchild;struct Node *rchild; }BitNode; void CreatBiTree(BitNode *&b,char *str) {BitNode *st[maxsize],*p=NULL; int ...

章贡区18256667670： 二叉树中序遍历递归算法 - ？
谭星长春： if(T){ if(InOrderTraverse(T->l,Visit)) if(Visit(T->data)) if(InOrderTraverse(T->r,Visit)) return OK; return ERROR; }else return OK; 以上就是中序遍历二叉树 这段程序我全有,具体如下:#include #define ERROR 0;#define FALSE 0;#define TRUE 1;...

章贡区18256667670： 二叉树的遍历? - ？
谭星长春： 遍历方案从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作:(1)访问结点本身(N),(2)遍历该结点的左子树(L),(3)遍历该结点的右子树(R)...

章贡区18256667670： 二叉树的中序遍历 - ？
谭星长春： 中序遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1)遍历左子树; (2)访问根结点; (3)遍历右子树.中序遍历的算法实现 用二叉链表做为存储结构,中序遍历算法可描述为: void InOrder(BinTree T) { //算法里①~⑥是为了说明执行过程加入的标号 ① if(T) { // 如果二叉树非空 ② InOrder(T->lchild); ③ printf(＂%c＂,T->data); // 访问结点 ④ InOrder(T->rchild); ⑤ } ⑥ } // InOrder

章贡区18256667670： 二叉树层次和中序遍历算法 - ？
谭星长春： 先序非递归算法 【思路】 假设:T是要遍历树的根指针,若T != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空. 问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针? 方法1:访...

章贡区18256667670： 用递归的方式中序遍历二叉树算法描述 - ？
谭星长春： void travser(Node *node) { if(node==NULL) return; travser(node->left); cout<<node->data; travser(node->right); }

章贡区18256667670： 求二叉树的遍历算法 - ？
谭星长春： 这里有一份以前从网上找到的C语言代码,自己测试过,没有问题,写的很好,分享给你,供参考: #include<stdio.h> #include<stdlib.h> #define STACKINITSIZE 100 #define STACKINCREASESIZE 20 typedef char ElemType; //树结构 typedef ...

章贡区18256667670： 二叉树遍历该怎样写?(计算机二级考试) - ？
谭星长春： 前序遍历 是 根左右 中序 是 左根右 后序 是 左右根 都是递归遍历:1.中序遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1)中序遍历左子树; (2)访问根结点; (3)中序遍历右子树. 2.先序(前序)遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1) 访问根结点; (2) 先序遍历左子树; (3) 先序遍历右子树. 3.后序遍历得递归算法定义: 若二叉树非空,则依次执行如下操作: (1)后序遍历左子树; (2)后序遍历右子树; (3)访问根结点

章贡区18256667670： 二叉树的遍历算法 - ？
谭星长春： 怎么又来问了,不是回答过你了吗?很简单,就是一个递归过程.在函数中以先序遍历的第一个结点在中序遍历中为界把中序遍历分为两半,再分别把左一半和右一半作为这个结点的左子树和右子树进行递归.完成递归之后再打印该结点即可....

章贡区18256667670： 按照二叉树的递归定义,对二叉树遍历的常用算法有哪三种? - ？
谭星长春： /*1 、前序遍历二叉树的递归算法 */ void preorder(bintree t) {if (t) {printf(＂%c＂,t->data);preorder(t->lchild);preorder(t->rchild);} } /*2 、中序遍历二叉树的递归算法 */ void inorder(bintree t) {if (t) {inorder(t->lchild);printf(＂%c＂,t->data);...