二叉排序树

发表于 | 分类于
字数统计: 352 word | 阅读时长 ≈ 1 min
理解：

二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：

(1):若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值

(2):若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值

(3):它的左、右子树也分别为二叉排序树

code：
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
 #include<iostream>
 #include<algorithm>
using namespace std;
typedef struct node{
	int data;
	struct node* left;
	struct node* right;
}*tree;
int n;    //含有n个结点
//插入
void Inserttree(tree &t, int key){
	tree f, p = t;
	//寻找待插入的节点的位置，用f记录待插入节点的父结点
	while (p){
		if (p->data == key){
			return;
		}
		else{
			f = p;
			if (p->data > key){
				p = p->left;
			}
			else{
				p = p->right;
			}
		}
	}
	//创建新结点，插入
	p = (tree)malloc(sizeof(node));
	p->data = key;
	p->left = p->right = NULL;
	if (t == NULL){
		t = p;
	}
	else{
		if (f->data > key){
			f->left = p;
		}
		else{
			f->right = p;
		}
	}
}
//创建二叉排序树
tree CreateTree(){
	tree t = NULL;
	int key;
	for (int i = 0; i < n; i++){
		cin >> key;
		Inserttree(t, key);
	}
	return t;
}
//中序遍历
void traveltree(tree t){
	if (t != NULL){
		traveltree(t->left);
		cout << t->data << " ";
		traveltree(t->right);
	}
}
int main(){
	tree t = NULL;
	cin >> n;
	t = CreateTree();
	traveltree(t);
	cout << endl;
}
0%