二叉树的建立与销毁（C语言）_二叉排序树的销毁

二叉树的建立

在讲解二叉树的建立前，请读者务必要先思考一个问题

思考问题：如何确定一个二叉树，如果只看 前序 或 中序 或 后序遍历 三种之一能够确定唯一一个二叉树的形状吗？
其中：
前序遍历结果：ADEBCF
中序遍历结果：DEACFB
后序遍历结果：EDFCBA

================================================
解：
单凭一种遍历的结果，无法确定一个二叉树，当满足以下两种情况即可满足确定。
条件1：前序和中序
条件2：中序和后序

为什么呢？证明如下：
步骤1：通过前序或后序遍历可确定根结点。（前序的第一个遍历结果，后序最后一个遍历结果）
步骤2：通过中序遍历可确定结点下的左子树和右子树部分。（通过前序和后序获得的根结点，在中序遍历中对应的该根节点位置分割左右子树）
以此类推，可确定二叉树的形状,读者不妨验证一下，加深理解。
将已知结果分为三部分，根节点和左右子树的判断，逐渐减少未知结点，重复利用前序或后序判断谁是根节点，在用中序判断谁是左子树或右子树。
二叉树形状：

================================================

ok!下面进入正题

通过输入字符来辨别是非创建对应结点，若输入’#'为空
注意：
1.创建的方式只能为先序，因为子树只有创建了根节点才能访问下层，顺序为：根节点、左子树、右子树
2.销毁的方式只能为后序，原因很简单，从低到高，不能先删除根节点，否则无法删除其对应的左右子树。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct NODE_ST{
	int value;
}node_st;

typedef struct D_TREE{
	node_st cur;
	struct D_TREE *lchild,*rchild;
}d_tree;

void inOrder(void *Node)
{
	d_tree *node = Node;
        if(node == NULL)
                return;
	inOrder(node->lchild);
	printf("%d",node->cur.value);
    inOrder(node->rchild);
}
//通过#字符 创建树
d_tree *tree_Create()
{
	d_tree *tmp = NULL;
	char ch = 0;
	printf("请输入字符：\n");
	scanf(" %c",&ch);//%c前加一个空格，否则会出错，可在我的博客查看相关讲解
	if(ch == '#'){
		return NULL;
	}
	else{
		tmp = (d_tree *)calloc(1,sizeof(d_tree));
		if(tmp == NULL){
			return NULL;
		}
		tmp->cur.value = atoi(&ch);
		tmp->lchild = tree_Create();
		tmp->rchild = tree_Create();
		return tmp;
	}
}

//后序销毁树
void tree_Free(d_tree *T)
{
	if(T == NULL)
		return;
	if(T->lchild != NULL){
		tree_Free(T->lchild);
		T->lchild = NULL;
	}
	if(T->rchild != NULL){
		tree_Free(T->rchild);
		T->rchild = NULL;
	}
	if(T != NULL){
		free(T);
		T = NULL;
	}
}

int main()
{
	d_tree *node = NULL;
	node = tree_Create();
	inOrder(node);
	printf("\n");
	tree_Free(node);

	return 0;
}

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
72
73