二叉树层次和中序遍历算法

Question

用C语言 非递归算法来写吧！！先序输入 输出层次和中序就100分了 谢谢啦！！！！急！！！！！！！！

Answer 1

先序非递归算法
【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法一
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法二
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。

中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
【算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。

后序非递归算法
【思路】
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。 [Page]
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 设置栈顶标记
T = GetTopPointer(S); // 取栈顶保存的指针
T = T->rchild;
}else break;
}
}

Answer 2

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);
}

Answer 3

我这边有二叉树功能的完整程序（包括建立，遍历等等），我不太方便贴了，你加我QQ吧~

Answer 4

#include<stdlib.h>#include<stdio.h>#define STACK_INIT_SIZE 100//栈初始分配的空间数#define STACKINCREAMENT 10//栈空间不够时增加的空间数typedef char eletype;//二叉树结点信息类型typedef struct BiTNode//二叉树结点类型{ struct BiTNode *lchild,*rchild; eletype data;}BiTNode;typedef BiTNode *elemtype;//elemtype声明为指针类型typedef struct stack//栈的存储类型，采用动态分配{ elemtype *base; elemtype *top; int stacksize;}sqstack; sqstack *initstack()//创建栈{ sqstack *s; if (!(s = (sqstack *)malloc(sizeof(sqstack))))exit(-1); s->base = (elemtype *)malloc(STACK_INIT_SIZE*sizeof(elemtype));//初始化为栈分配STACK_INIT_SIZE个elemtype类型的空间 if (!s->base)//分配空间失败 { exit(-2); printf("栈空间分配失败!\n"); } if (s->base)//分配空间成功 printf("栈空间分配成功!\n"); s->top = s->base;//初始化栈的头尾指针 s->stacksize = STACK_INIT_SIZE; return s;} void push(sqstack *s,elemtype e)//压栈，e要是一个地址{ if (s->top-s->base>=s->stacksize)//栈满 { s->base = (elemtype *)realloc(s->base,(s->stacksize+STACKINCREAMENT)*sizeof(elemtype));//栈满时增加空间 if (!s->base)//增加分配空间失败 exit(-2); s->stacksize += STACKINCREAMENT; } *(s->top) = e; s->top++;} elemtype pop1(sqstack *s)//出栈1，返回的e为栈顶元素是一个地址{ elemtype e; if (s->top == s->base)return 0;//栈空时返回 s->top--; e = *(s->top); return e;} int stackempty(sqstack *s)//判断栈空，栈空返回1，否则返回0{ if (s->base == s->top)return 1; else return 0;} BiTNode *CreateBiTree()//先序递归法建树{ char x; BiTNode *t; scanf("%c",&x); if (x == ' ')t = NULL; else { if (!(t = (BiTNode *)malloc(sizeof(BiTNode))))exit(-1); t->data = x;//建立节点 t->lchild = CreateBiTree();//建左子树 t->rchild = CreateBiTree();//建右子树 } return t;} int InOrder(BiTNode *t)//中序遍历二叉树非递归算法{ sqstack *s; BiTNode *p; s = initstack();//初始化栈 p = t; printf("中序遍历二叉树，字符序列为:\n"); while (p||!stackempty(s)) { while (p)//找最左结点 { push(s,p); p = p->lchild;//p指针顺lchild而下 } p = pop1(s);//栈顶元素出栈以访问最左结点 printf("%c",p->data);//访问最左结点 p = p->rchild; } printf("\n"); return 1;} void main(){ BiTNode *t; printf("请输入建树字符序列,以空格表示NULL:\n"); t = CreateBiTree(); InOrder(t);}