1+

来自「1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色」· 代码 · 共 84 行

//按先序扩展序列建立二叉树. 三种递归遍历按先序扩展序列建立二叉树. 三种递归遍历

#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#include <stdio.h>
typedef struct node
{
	char data;
	struct node *lchild;
	struct node *rchild;
}*BiTree;

void creatBT(BiTree &T)//建立一个二叉树的函数
{
	char ch;
	scanf("%c",&ch);
	if(ch=='.')
	{
		T=NULL;//   . 代表空子树；
	}
	else
	{
		T=(node *)malloc(sizeof(node));//分配一个node的空间
		if(!T)exit(0);
		T->data = ch;//给T赋值
		creatBT(T->lchild);//给左子树赋值
		creatBT(T->rchild);//给右子树赋值
	}
}

void pre_order(node *T)//前序遍历二叉树
{
	if(T)
	{
		printf("%c ",T->data);
		pre_order(T->lchild);
		pre_order(T->rchild);
	}

}

void mid_order(node *T)//中序遍历二叉树
{
	if(T)
	{
		mid_order(T->lchild);
		printf("%c ",T->data);
		mid_order(T->rchild);
	}
}

void behind_order(node *T)//后序遍历二叉树
{
	if(T)
	{
		behind_order(T->lchild);
		behind_order(T->rchild);
		printf("%c ",T->data);
	}
}

int main()
{
	node *T;
	printf("请输按先序序列输入一串字符,当子树为空时,用.来代替\n");
	creatBT(T);//建树
	printf("建树成功,T指向二叉树的根!\n");

	printf("\n前序遍历二叉树的结果是:");
	pre_order(T);

	printf("\n中序遍历二叉树的结果是:");
	mid_order(T);

	printf("\n后序遍历二叉树的结果是:");
	behind_order(T);printf("\n");
	
	
	
	
	return 0;
}