二叉树递归非递归遍历 C语言可直接运作

二叉树递归非递归遍历 C语言可直接运行
/************************* 声明区 *************************/
#include<stdio.h>
#include<stdlib.h>
#define OK true
#define Nil ' '
#define OVERFLOW false
#define FALSE false
#define ERROR false
#define TRUE true
typedef bool Status;
typedef char TElemType;
 
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
int Length=0;
/************************* 结构体类型部分 *************************/
//n个结点的二叉链表有n + 1个空链域（空的孩子指针域）
typedef struct BiTNode
{
       TElemType data; 
       BiTNode *lchild, *rchild; 
}BiTNode,*BiTree;

typedef BiTree SElemType;    //栈中操作的是指向树节点的指针 

/********************** 结构类型部分 **********************/
typedef struct SqStack
{       
       SElemType *base;       
       SElemType *top;       
       int stacksize;       
}SqStack;  
 
/********************** 构造一个空栈S **********************/
Status InitStack(SqStack &S)
{ 
       if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType))))
              exit(OVERFLOW);         
       S.top = S.base; 
       S.stacksize = STACK_INIT_SIZE; 
       return OK;
}

/********************** 返回栈顶元素 **********************/
Status GetTop(SqStack S, SElemType &e)
{ 
       if (S.top > S.base)
       {
              e = *(S.top - 1);               
              return OK;
       }
       else
              return ERROR;
}

/********************** 插入新的栈顶元素 **********************/
Status Push(SqStack &S, SElemType e)
{ 
       if (S.top - S.base >= S.stacksize) // 注意此处的等号              
       {              
              S.base = (SElemType *) realloc(S.base, 
                     (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); 
             
              if (!S.base)
                     exit(OVERFLOW);           
              
              S.top = S.base + S.stacksize;
              S.stacksize += STACKINCREMENT;
       }
      
       *(S.top)++ = e; 
       return OK;
}

/********************** 删除栈顶元素 **********************/
Status Pop(SqStack &S, SElemType &e)
{ 
       if (S.top == S.base) 
              return ERROR;
      
       e = *--S.top; 
       return OK;
}

/************************* 建立二叉树并输入数值 *************************/
void CreateBiTree(BiTree &T)
{ // 注意此处的 递归函数的终止条件是一棵二叉树完全构建好 ，当二叉树没有构建完成时，递归没有完成 
       TElemType ch;
       scanf("%c", &ch);
       if (ch == Nil) // 空
              T = NULL;
       else
       {
              T = (BiTree) malloc(sizeof (BiTNode));
              if (!T)
                     exit(OVERFLOW);
              T->data = ch; 
              CreateBiTree(T->lchild); 
              CreateBiTree(T->rchild); 
       }
}

/************************* 输出元素函数 *************************/
Status PrintElement(TElemType e)  
{
       printf("%c\t",e);
       return OK;
}

/********************** 判断栈是否是空的 **********************/
Status StackEmpty(SqStack S)
{       
       if (S.top == S.base)
              return TRUE;
       else
              return FALSE;
}
/********************** 输出栈元素 **********************/
void OutList(SqStack S)
{
       S.top=S.base;  
       for(int i=0;i<Length;i++) 
       {
              printf("%d\t",*(S.top)++);
       }
       printf("\n");  
}

/************************* 递归中序遍历*************************/
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e))
{
       if(!T)
       	return ERROR;
      	else
      	{
	    	InOrderTraverse(T->lchild,Visit);
			Visit(T->data);
			InOrderTraverse(T->rchild,Visit);  	
        }
       return OK;
}

/************************* 非递归中序遍历一 *************************/
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e))
{
       SqStack S;
       BiTree p;
       InitStack(S);
       Push(S,T);
       while(!StackEmpty(S))
       {
              while(GetTop(S,p)&&p)
                     Push(S,p->lchild);
              Pop(S,p);
              if(!StackEmpty(S)){
                     Pop(S,p);
                     if(!PrintElement(p->data))
                            return ERROR;
                     Push(S,p->rchild);
              }
       }
       return OK;
}

/************************* 非递归中序遍历二 *************************/
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e))
{
       SqStack S;
       BiTree p;
       InitStack(S);
       p = T;
       while(p||!StackEmpty(S))
       {
              if(p)
              {
              	Push(S,p);
              	p = p->lchild;
              }
              else
              {
              	Pop(S,p);
              	if(!Visit(p->data))
              		return ERROR;
     		    p = p->rchild;
              }
       }
       return OK;
}

/************************* 主函数部分 *************************/
int main(int args[])
{
       /**************** 函数声明区 ******************/
       void CreateBiTree(BiTree &T);
       Status PrintElement(TElemType);
       Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
       /**************** 函数执行区 ******************/
       //测试用例 输入ABC##DE#G##F###，其中#用空格代替 
       BiTree A;
       CreateBiTree(A);
       InOrderTraverse(A,PrintElement);
       printf("\n"); 
       InOrderTraverse1(A,PrintElement);              
       printf("\n"); 
       InOrderTraverse(A,PrintElement);
       return 0;
}
二叉树 递归 非递归 遍历 C语言 可直接运作

相关推荐

二叉树递归非递归遍历 C语言可直接运作
