二叉排序树简单实现【C风格】

二叉赛普树

把数据按照二叉树的结构保存，按照顺序放入，小的节点放左边，大的节点放右边。
难点是删除数据。

//二叉排序树 数据结构和算法
#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;//状态类型
typedef int ElemType;//元素类型
//定义一个二叉搜索树
typedef struct SearchBiTreeNode
{
	int data;
	SearchBiTreeNode* lchild, * rchild;
}BiNode, *BiTree;

//搜索算法
//T 是待搜索的树，target是搜索的目标，f是树T的父节点，p保存搜索的节点
Status SearchBiT(BiTree T, int target, BiTree f, BiTree* p)
{
	//如果当前树为空
	if (T == NULL)
	{
		*p = f;//将树的父节点传回去，此时父节点为空
		return FALSE;
	}
	//如果在当前树找到了目标
	if (T->data == target)
	{
		*p = T;
		return TRUE;
	}
	//如果比当前值小,在左边节点找
	if (target < T->data)
		return SearchBiT(T->lchild, target, T, p);

	//如果比当前值大，在右边节点找
	return SearchBiT(T->rchild, target, T, p);
}

//插入数据到二叉搜索树，按照大小排序插入
//不能插入相同的数据
Status InsertBiT(BiTree* T, int data)
{
	BiTree p, s;
	//先搜索有没有相同的数据，如果存在不能插入
	if (SearchBiT(*T, data, NULL, &p) == TRUE)
	{
		return FALSE;
	}
	//如果没有找到
	else
	{
		//分配内存
		s = (BiTree)malloc(sizeof(BiNode));
		
		//初始化
		s->data = data;
		s->lchild = NULL;
		s->rchild = NULL;

		//判断放在哪个位置,返回的p是父节点，下面肯定有一边为空
		if (p == NULL)//如果搜索到的树节点为空
			*T = s;
		//如果树不为空,并且小与搜索到的树节点的当前值
		else if (data < p->data)
			p->lchild = s;
		else//大与搜索到的树节点的当前值
			p->rchild = s;
		return TRUE;
	}

}

Status Delete(BiTree* T)
{
	BiTree p, s;
	//判断树的状态
	//空树,下面函数会判断
	//左节点和（或）右节点为空
	if ((*T)->rchild == NULL)//右边节点为空
	{
		p = *T;
		*T = (*T)->lchild;//把左节点提上去
		free(p);
		return TRUE;
	}
	if ((*T)->lchild == NULL)//左边节点为空
	{
		p = *T;
		*T = (*T)->rchild;//把右节点提上去
		free(p);
		return TRUE;
	}
	//找到左子树节点，对左子树操作
	p = *T;
	s = (*T)->lchild;

	//找左子树的最右边的节点
	while (s->rchild)
	{
		p = s;//保证p是s的父节点
		s = s->rchild;
	}
	//先把找到的s的值赋给*T，再删除s，也就相当于删除了*T
	(*T)->data = s->data;
	//判断是不是左子树真的有右节点
	if (p == *T)//如果没有
		(*T)->lchild = s->lchild;//把s的左边所有接到根上，跳过s，后面删除
	else//左子树真的有右节点,那么把最后一个右节点的值给*T后，让s的父节点右边接s的左边
		p->rchild = s->lchild;
	free(s);//把s删除，相当于删除了*T，s现在为*T
	return TRUE;
}

//删除节点
Status DeleteBiT(BiTree* T, int target)
{
	//树为空
	if (*T == NULL)
		return FALSE;
	//目标值为当前的树
	if ((*T)->data == target)
		return Delete(T);
	//递归向下删除
	if (target < (*T)->data)//左
		return DeleteBiT(&(*T)->lchild, target);
	return DeleteBiT(&(*T)->rchild, target);//右

}
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130