Question

数据结构（C语言版）问题，求大神解答？

写出非递归中序遍历二叉树算法

Answer 1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TElemType int
int top=-1;
//top变量时刻表示栈顶元素所在位置
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
*T=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data=1;
(*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=6;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=4;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=7;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=8;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=5;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
//前序和中序遍历使用的进栈函数
void push(BiTNode** a,BiTNode* elem){
a[++top]=elem;
}
//弹栈函数
void pop( ){
if (top==-1) {
return ;
}
top--;
}

void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//拿到栈顶元素
BiTNode* getTop(BiTNode**a){
return a[top];
}
//中序遍历非递归算法
void InOrderTraverse1(BiTree Tree){
BiTNode* a[20];//定义一个顺序栈
BiTNode * p;//临时指针
push(a, Tree);//根结点进栈
while (top!=-1) {//top!=-1说明栈内不为空，程序继续运行
while ((p=getTop(a)) &&p){//取栈顶元素，且不能为NULL
push(a, p->lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
}
pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
if (top!=-1) {
p=getTop(a);
pop();
displayElem(p);
push(a, p->rchild);
}
}
}

int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf("中序遍历算法: \n");
InOrderTraverse1(Tree);

}

Answer 2

#include<stdio.h>

#include<malloc.h>

typedef struct st{

char data;

struct st *r;

struct st *l;

}*link,ll;

char s[20]="ABC##DE##F##G##";//二叉树序列 

int i=0;

void create_tree(link &tree)//先序递归建树 

{

if(s[i]=='#') 

tree=NULL,i++;

else

{

tree=(link)malloc(sizeof(ll)); 

tree->data=s[i],i++;

create_tree(tree->l);

create_tree(tree->r);

}

}

void in_1(link tree)//递归中序遍历 

{

if(tree)

{

in_1(tree->l);

printf("%c ",tree->data);

in_1(tree->r);

}

}

void in_2(link tree)//非递归中序遍历 

{

    link s[20];//储存指针结点 

    int top =-1;

    link p = tree;

    while(p!=NULL||top!=-1){

        if(p!=NULL){

            s[++ top] = p;

            p = p->l;

        }else{

            p = s[top --];

printf("%c ",p->data); //出栈时，访问输出

            p = p->r;

        }

    }

}

int main()

{

link T=NULL; 

create_tree(T);//建树 

printf("递归中序遍历\n");

in_1(T);//递归中序遍历 

printf("\n非递归中序遍历\n");

in_2(T);//非递归中序遍历 

return 0;

}