二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。
二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，期望O(log n),最坏O(n)(数列有序,树退化成线性表).
|
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 |
#include<iostream>using
namespace std;typedef
int Type;typedef
struct node{ Type data; struct
node * left; struct
node * right;}BinaryTree;void
findInsertNode(BinaryTree *bt,Type data){ BinaryTree *point=bt; int
FlagL=0,FlagR=0; while(point){//若有子节点继续查找，若没有就退出，然后插值 if(data>point->data) if(point->right) point=point->right; else {FlagR=1;break;} else if(point->left) point=point->left; else {FlagL=1;break;} } BinaryTree *node=new
BinaryTree(); node->data=data; node->left=0; node->right=0; if(FlagR) point->right=node; else point->left=node;}BinaryTree * createSortBT(Type data[],int
length){ BinaryTree *bt=new
BinaryTree(); bt->left=0; bt->right=0; int
i=0; while(i<length){ if(0 == i) bt->data=data[i++];//创建根 else{ findInsertNode(bt,data[i++]);//创建叶子 } } return
bt;}/*中序遍历二叉树bt*/void
PreOrder(BinaryTree * bt) { if
(bt==0) return; PreOrder(bt->left); cout<<bt->data<<" "; PreOrder(bt->right); }int
main(){ Type data[8]={5,4,6,2,10,7,9,8}; BinaryTree *bt=createSortBT(data,8); PreOrder(bt); getchar(); return
0;} |
二叉查找树（Binary Search Tree）,布布扣,bubuko.com
原文：http://www.cnblogs.com/seair/p/3630953.html