二叉树的多种建立方式

二叉树有很多种建立方式，此篇整理三种常用的二叉树建立方式（C语言实现）

• 根据先序扩展序列建立二叉树（将空孩子用特殊字符表示出来的先序序列）
• 根据二叉树的先序序列和中序序列，建立二叉树（空孩子没有表示出来）
• 根据层级序列和中序序列建立二叉树
• 释放内存空间

下列函数中使用的二叉树的节点为

typedef struct Node{	//二叉树节点的定义
	char data;
	Node *lchild;
	Node *rchild;
}Node,*Tree;
1
2
3
4
5

根据先序扩展序列建立二叉树

该函数需要根节点作为参数，以传入的根节点为根节点创建二叉树，输入应为正确的先序序列，例如“abc##de#g##f###”，字符间无空格

void createTreeByXianXu(Tree &T){		//输入先序扩展序列创建二叉树,"#"代表空树
	char ch;
	scanf("%c",&ch);
	if(ch == '#')	T = NULL;
	else{
		if(!(T= (Node*) malloc(sizeof(Node))))
			return;
		T->data = ch;
		createTreeByXianXu(T->lchild);
		createTreeByXianXu(T->rchild);	
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

根据二叉树的先序序列和中序序列，建立二叉树。

该函数需要将先序序列和中序序列作为数组pre和mid传入，n表示序列的长度，返回值即为二叉树的根节点。 pre的示例为“ABC” mid的示例为“BAC”

Node* createTree(char *pre,char *mid,int n){	//给定二叉树的先序序列和中序序列，建立二叉树 
	Node* s = (Node*)malloc(sizeof(Node));
	s->data = *pre;
	s->lchild = s->rchild = NULL;
	
	if(n == 1){			
		return s;
	}

	int i = 0;
	for(;i < n;i++){
		if(mid[i] == pre[0])
			break;
	}
	
	if(i)	s->lchild = createTree(pre+1,mid,i);
	if(n-i-1)	s->rchild = createTree(pre+i+1,mid+i+1,n-i-1);	
	return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

根据层级序列和中序序列建立二叉树

这里代码借鉴https://blog.csdn.net/weixin_42545675/article/details/103337658
函数的调用示例为：
Tree * root = createBTree(层级序列、中序序列、0、length-1、0、length-1);

Node* createBTree(char level[], char in[], int l1, int r1, int l2, int r2){		//根据层级序列和中序序列建立二叉树 
	if (l2 > r2)
		return NULL;
	else{
		Node* bt = (Node*)malloc(sizeof(Node));
		
		int i, j;//分别指向level和in中数组的元素
		int flag = 0;
 
		//寻找根结点，若level中第一个与in中元素匹配的即为根结点
		for (i = l1; i <= r1; ++i){
			for (j = l2; j <= r2; ++j){
				if (level[i] == in[j]){
					flag = 1;
					break;
				}
			}
 
			if (flag == 1)
				break;
		}
 
		bt->data = level[i];
		bt->lchild = createBTree(level, in, l1 + 1, r1, l2, j - 1);
		bt->rchild = createBTree(level, in, l1 + 1, r1, j + 1, r2);
 
		return bt;
	}
}
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

释放内存空间

由于以上建立方式都是使用malloc函数创建节点，因此为防止内存泄漏，需要使用free函数释放二叉树的内存空间，建议在主函数最后调用destory函数释放内存空间。

void destory(Tree T){		//释放二叉树的内存空间 
	if(!T)
		return;
	destory(T->lchild);
	destory(T->rchild);
	free(T);
}
1
2
3
4
5
6
7