首页 > 代码库 > 二叉树的递归与非递归
二叉树的递归与非递归
二叉树的递归和非递归算法：
(做这个的时候，总是逻辑跟不上，会搞混，做的时候发现自己对结构体指针的使用有些糊涂。)
代码如下：
#include <stdio.h>
#include <stdlib.h>
#define Max 100
typedef struct Node
{
char Date;
struct Node *Lchild; //左孩子
struct Node *Rchild; //右孩子
}BiNode,*BiTree;
typedef struct //树类型的结构体，顺序存储
{
BiTree date[Max];
int top; //控制栈顶
}SeqStack,*PseqStack;
void CreatTree( BiTree *root) ////递归方式创建二叉树
{
char f;
f=getchar();
if(f==‘.‘) //用.来代替孩子是空的情况
*root=NULL;
else
{
*root=(BiTree)malloc(sizeof(BiNode)); //分配空间
(*root)->Date=f;
CreatTree(&((*root)->Lchild));
CreatTree(&((*root)->Rchild));
}
}
//递归
void Visit(char Date)
{
printf("%c ",Date);
}
void PreOrder(BiTree root) // 先序遍历
{
if(root)
{
Visit(root->Date);
PreOrder(root->Lchild);
PreOrder(root->Rchild);
}
}
void InOrder(BiTree root) // 中序遍历
{
if(root)
{
InOrder(root->Lchild);
Visit(root->Date);
InOrder(root->Rchild);
}
}
void PostOrder(BiTree root) // 后序遍历
{
if(root)
{
PostOrder(root->Lchild);
PostOrder(root->Rchild);
Visit(root->Date);
}
}
//非递归
PseqStack Init_SeqStack()
{
PseqStack S;
S=(PseqStack)malloc(sizeof(SeqStack));
S->top=-1;
return S;
}
int IsEmpty(PseqStack S) //判空
{
if(S->top==-1)
return 1;
else
return 0;
}
int Push(PseqStack S,BiTree x) //进栈
{
if(S->top==Max-1)
return 0;
else
S->top++;
S->date[S->top]=x;
return 1;
}
BiTree Pop(PseqStack S) //出栈
{
if (!IsEmpty(S))
return S->date[S->top--];
}
void PreOrder1(BiTree root) //非递归先序
{
PseqStack S;
BiTree p;
p=root;
S=Init_SeqStack();
while(p!=NULL||!IsEmpty(S)) //当树不是空树或栈不是空
{
while(p!=NULL) //当树不是空树时
{
Visit(p->Date); //访问根节点的元素
Push(S,p); //将这个节点压入栈
p=p->Lchild; //然后是左孩子，一直循环，按先序的方式。
}
if(!IsEmpty(S)) //栈不是空的，出栈，然后是右孩子。
{
p=Pop(S);
p=p->Rchild;
}
}
}
void InOrder1(BiTree root) //非递归中须。
{
PseqStack S;
BiTree p;
p=root;
S=Init_SeqStack();
while(p!=NULL||!IsEmpty(S))
{
while(p!=NULL)
{
Push(S,p);
p=p->Lchild;
}
if(!IsEmpty(S))
{
p=Pop(S);
Visit(p->Date);
p=p->Rchild;
}
}
}
void PrintTree(BiTree Root,int n) //输出图形
{
int i;
if(Root==NULL) return; //空树
PrintTree(Root->Rchild,n+1);
for(i=0;i<n;i++) //控制空格
printf(" ");
printf("%c\n",Root->Date);
PrintTree(Root->Lchild,n+1);
}
int main (void)
{
BiTree Root;
int n=0;
printf("please input the bitree:\n");
CreatTree(&Root);
printf("the preorder bitree is \n");
PreOrder(Root);
printf("\nthe InOrder bitree is \n");
InOrder(Root);
printf("\nthe PostOrder bitree is \n");
PostOrder(Root);
printf("\nthe non-recursive tree is (preorder)\n");
PreOrder1(Root);
printf("\nthe non-recursive tree is (inorder)\n");
InOrder1(Root);
printf("\nthe picture of bitree is :\n\n");
PrintTree(Root,n);
getch();
return 0;
}
By：暖暖
2014.11.19
二叉树的递归与非递归