非递归.cpp

来自「以先序,中序,后序遍历二叉链表的非递归算法」· C++ 代码 · 共 76 行

#define max 30
#define NULL 0
#include<stdio.h>
#include<stdlib.h>

typedef struct btnode
{
	char data;
	struct btnode *lchild,*rchild;
}bttree;
bttree *cre_tree(char *str,int i,int m)
{
	bttree *p;
	if(i>=m)
		return NULL;
	p=(bttree *)malloc (sizeof(bttree));
	p->data=str[i];
	p->lchild=cre_tree(str,2*i+1,m);
    p->rchild=cre_tree(str,2*i+1,m);
	return p;
}

void preorder(bttree *t)  //先序
{
	if(t!=NULL)
	{
		printf("%c",t->data);
	    preorder(t->lchild);
		preorder(t->rchild);
		}
	}

void inorder(bttree *t)   //中序
{
	if(t!=NULL)
	{
		inorder(t->lchild);
	    printf("%c",t->data);
		inorder(t->rchild);
	}
}
void postorder(bttree *t) //后序
{
	if(t!=NULL)
	{
     postorder(t->lchild);
	 preorder(t->rchild);
	 printf("%c",t->data);
	}
}
void main()
{
	int i,n;
	char str[max];
	bttree *root;
	printf("请输入一颗树的结点长度:\n");
	scanf("%d",&n);
	getchar();
	printf("请输入字符串,长度为:%d\n",n);
	for(i=0;i<n;i++)
		str[i]=getchar();
	printf("\n");
	root=cre_tree(str,0,n);
	printf("树正被建立\n");
	printf("先序后的遍历是:\n");
	preorder(root);
	printf("\n");
	printf("中序后的遍历是:\n");
	inorder(root);
	printf("\n");
	printf("后序后的遍历是:\n");
	postorder(root);
	printf("\n");

}