二叉树的递归非递归建立与非递归遍历二叉树的递归非递归建立与非递归遍历
/********二叉树的递归与非递归建立，非递归先序与后序的遍历*****/ /**********编程者:YDLZL ********/
/**本人比较笨,花了一晚上功夫才完全调试好了,为了让更多的人少花点时间,决定共享**/
#include
#define Maxsize 20
typedef char datatype;
typedef struct BTreeNode
{
datatype data;
struct BTreeNode *Lchil...
二叉树的递归非递归建立与非递归遍历
/********二叉树的递归与非递归建立，非递归先序与后序的遍历*****/ /**********编程者:YDLZL ********/
/**本人比较笨,花了一晚上功夫才完全调试好了,为了让更多的人少花点时间,决定共享**/
#include
#define Maxsize 20
typedef char datatype;
typedef struct BTreeNode
{
datatype data;
struct BTreeNode *Lchild;
struct BTreeNode *Rchild;
} BTree;
/****先序递归建立二叉树 *****/
BTree *CreatBTree()
{
BTree *T;
char ch;
scanf("%c",&ch);
getchar();
if(ch=='#') T=NULL ;
else
{
T=(BTree *)malloc(sizeof(struct BTreeNode));
T->data = ch;
T->Lchild=CreatBTree(); /*构造左子树 */
T->Rchild=CreatBTree(); /*构造左子树 */
}
return T;
}
/********************************/ /****先序非递归建立二叉树算法***/
/********************************/
BTree *creatree(char *s)
{ BTree *stack[Maxsize],*p,*T,*q;
int top=-1,k=0,j=0;
char ch;
ch=s[j];
T=(BTree *)malloc(sizeof(struct BTreeNode));
T=NULL;
while(ch!='#')
{ switch(ch)
{
case '(':stack[++top]=p;k=1;break;
case ')': top--;break;
case ',': k=2;break;
default:p=(BTree *)malloc(sizeof(struct BTreeNode));
p->data=ch;p->Lchild=p->Rchild=NULL;
if(T==NULL)
T=p;
else
{ switch(k)
{case 1:q=(BTree *)malloc(sizeof(struct
BTreeNode));q=stack[top];q->Lchild=p;break;
case 2:q=(BTree *)malloc(sizeof(struct
BTreeNode));q=stack[top];q->Rchild=p;break;
}
}
}
j++;
ch=s[j];
}
return T;
}
/****先序非递归遍历算法***/
PreOrder(BTree *T)
{
BTree *p;
BTree stack[Maxsize];
int top=0;
p=T;
/****stack empty,over***/
while(p!=NULL || top!=0)
{
while(p!=NULL)
{
printf("%c", p->data);
stack[top++]=*p;
p=p->Lchild;
}
if (top!=0)
*p=stack[--top];
p=p->Rchild;
}
}
/*************************/ /*后序遍历的非递归算法 */
/************************/ PostOrder(BTree *T)
{
BTree *p,*q;
BTree stack[Maxsize];
char flag;
int top=0;
p=T;
/*q=(BTree *)malloc(sizeof(struct BTreeNode)); */
q=NULL;
while (p||top!=0)
{
if(p!=q)
{
while(p)
{
top++;
stack[top]=*p;
if(p->Lchild)p=p->Lchild;else p=p->Rchild;
}
}
if (top==0)break;
*q=stack[top];
if(q->Rchild==p)
{
*p=stack[top];top--;
printf("%c",p->data);
p=q;
flag= p->data;
}
else
{
p=q->Rchild;
if (flag== p->data)
{
*p=stack[top];top--;
printf("%c",p->data);
p=q;
flag= p->data;
}
}
}
}
main()
{
BTree *T;
char *s;
/* T= CreatBTree();*/
printf("input a tree-string \n");
scanf("%s",s);
T=creatree(s);
PreOrder(T);
getch();
printf("\n") ;
PostOrder(T);
getch();
}
如树:
A
/ \
B C
\ / \
D E F
则输入树串”A(B(,D),C(E,F))# ”
本文档为【二叉树的递归非递归建立与非递归遍历】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483