利用先序遍历输入法建立二叉树-Toy模板网

这篇具有很好参考价值的文章主要介绍了利用先序遍历输入法建立二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：假设二叉树结点的数据为字符，即

struct TreeNode {

char Data;

struct TreeNode * Left;

struct TreeNode * Right;

};

如果对该二叉树遍历打印，并且以#代表空树，那么可以得到一个字符串，例如下面的二叉树：（注：设二叉树的结点数据不能为字符#）

利用先序遍历输入法建立二叉树

先序遍历结果为：ABC##DE##F###

编写程序，输入一个类似于上面先序遍历结果的字符串，根据此字符串建立二叉树。（算法可参考教材126页）验证该二叉树是否正确。

1.二叉树/二叉排序树结构体：

struct TreeNode{
	int Data;
	struct TreeNode*Left;
	struct TreeNode*Right;
};

2.创建一颗空树：

Struct TreeNode*T；
T=NULL;

3.关于树节点的计算，高度的计算等请看我的另一篇文章（二叉树的实现1）：

https://mp.csdn.net/mp_blog/creation/editor/122858841

4.利用先序遍历输入法建立二叉树：

struct TreeNode* Creat() {//在函数中不能进行传参
	struct TreeNode*T;
	printf("输入一个字符：\n");
	char  ch;
	scanf("%c",&ch);//一个一个字符的边输入边插入法
	getchar(); //消掉在scanf函数中自带的换行符


	if(ch=='#'){
		T=NULL;//如果输入的为‘#’，则代表该结点为空
	}else {
		T=malloc(sizeof(struct TreeNode));//否则创建一个结点
		T->Data=ch;//将输入的内容先存入根结点中
		T->Left=Creat();//再调用本身函数将再次输入的结点存入左子树中
		T->Right=Creat();//最后存入右子树中
	}
return T;	//返回插入内容后的树
}

实验源代码：

#include<stdio.h>
#include<stdlib.h>

struct TreeNode{
	char Data;
	struct TreeNode*Left;
	struct TreeNode*Right;
};
//按先序遍历的顺序建立二叉树 
struct TreeNode* Creat() {
	struct TreeNode*T;
	printf("输入一个字符：\n");
	char ch;
	scanf("%c",&ch);
	getchar(); 


	if(ch=='#'){
		T=NULL;
	}else {
		T=malloc(sizeof(struct TreeNode));
		T->Data=ch;
		T->Left=Creat();
		T->Right=Creat();
	}
return T;	
}
//先序遍历 
void Preorder(struct TreeNode*T){
	if(T!=NULL){
 		printf("%c",T->Data);
 		Preorder(T->Left);
 		Preorder(T->Right);
 	}
 	if(T==NULL)
	 printf("#"); 
}
//中序遍历 
void Inorder(struct TreeNode*T){
	if(T!=NULL){
	 	Inorder(T->Left);
 		printf("%c",T->Data);
 		Inorder(T->Right);
 	}
 	if(T==NULL)
	 printf("#"); 
}
//后序遍历 
void Postorder(struct TreeNode*T){
	if(T!=NULL){
 		Postorder(T->Left);
 		Postorder(T->Right);
 		printf("%c",T->Data);
 	}
	if(T==NULL)
	 printf("#"); 
}
void Print(struct TreeNode*T){
     printf("先序遍历为：");
	Preorder(T);
	printf("\n"); 
	
	printf("中序遍历为：");
	Inorder(T);
	printf("\n");
	
	printf("后序遍历为：");
	Postorder(T);
	printf("\n"); 
}
int  main(){
	struct TreeNode*T;

    T=Creat();
    
    Print(T);
    return 0;
}

实验结果：

利用先序遍历输入法建立二叉树