还原二叉树(C语言实现)_7-10 还原二叉树c语言

就把这个题目当作建树的练手题了
代码如下

#include<stdio.h>
#include<malloc.h>
typedef struct node{
	char data;
	struct node* left;
	struct node* right;
}Treenode,*NodeP;
char Pre[51],Mid[51];
int Position(char data,char Mid[],int n); 
 
NodeP Insert(NodeP root,char data,int n)
{
	if(!root){//建立根节点 
		NodeP a = (NodeP)malloc(sizeof(Treenode));
		a->data = data;
		a->left = a->right = NULL;
		root = a;
	}else{
		int Pos1 = Position(root->data,Mid,n);//当前根节点在中序序列中的位置 
		int Pos2 = Position(data,Mid,n);//新插入结点在中序序列中的位置 
		if(Pos2 < Pos1){//结点位于左子树 
			if(root->left){//当左子树不为空 
				root->left = Insert(root->left,data,n);
			}else{//当左子树为空直接插入 
				NodeP a = (NodeP)malloc(sizeof(Treenode));
				a->data = data;
				a->left = a->right = NULL;
				root->left = a;
			}
		}else{//结点位于右子树 
			if(root->right){//当右子树不为空
				root->right = Insert(root->right,data,n); 
			}else{//当右子树为空直接插入 
				NodeP a = (NodeP)malloc(sizeof(Treenode));
				a->data = data;
				a->left = a->right = NULL;
				root->right = a;
			}
		}
	}
	return root;
}
int Position(char data,char Mid[],int n)
{
	for(int i = 0;i < n;i++){
		if(data == Mid[i])
			return i;//这是先序序列中元素在中序序列中的位置 
	}
}
int GetHeight(NodeP root){
	int MaxH, HR, HL;
    if(root) {
        HL = GetHeight(root->left);
        HR = GetHeight(root->right);
        MaxH = (HL>HR)?HL:HR;
        return MaxH+1;
    }
    return 0;
}
int main()
{
	int n;
	scanf("%d",&n);
	
	scanf("%s",&Pre);
	scanf("%s",&Mid);
	NodeP root = NULL;
	for(int i = 0;i < n;i++)
		root = Insert(root,Pre[i],n);
	printf("%d",GetHeight(root));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

①题示字符串的输入呢，一开始使用的是gets();但是总是报错，后来改用%s的scanf输入就可以了
②然后就是根据先序和中序序列建树，大体思路是这样
首先先序是 根->左->右，中序是 左->根->右
那么在先序序列中先找到整棵树的根结点，也就是A
那么接下来，通过观察B在中序遍历序列中相对于A的位置，就可以知道B是A的左孩子还是右孩子中，接着找对位置插入即可。例如在中序序列中，B在A的左侧，那么B就是A的左孩子，建立新结点插入B即可。
转化成程序呢，位置就可以通过数组中数组下标的大小来判断，新插入的结点通过递归判断插入位置即可
③最后是返回树高的函数GetHeight();
这个函数要记住，也是通过递归实现，基本思想就是选出左右子树中最高的那一枝作为树的高度输出，将为NULL的结点作为递归出口，其他不为空的结点继续调用函数；递归层数的增加也就可以通过 return MaxH+1;中的+1记录为高度的增加
结果如下

不要再将if判断条件中的’==‘写成’='了… T_T(这种bug是真难找)