原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/2018/1012/65.html

今天我们常州网站开发与设计专家-幻天网络来简单讨论一下二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

定义：

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

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

下面是实现：

 1 #include <iostream>

 2 using namespace std;

 3 

 4 struct BiTNode

 5 {

 6     int data;

 7     BiTNode *lchild, *rchild;

 8     BiTNode(int x) :data(x), lchild(NULL), rchild(NULL){}

 9 };

10 

11 void Insert(BiTNode *&root, int key)

12 {

13     if (root == NULL)

14         root = new BiTNode(key);

15     else if (key < root->data)

16         Insert(root->lchild, key);

17     else if (key > root->data)

18         Insert(root->rchild, key);

19 }

20 

21 void Create(BiTNode *&root)

22 {

23     int key;

24     while (cin >> key)

25     {

26         if (key == -1)

27             break;

28         Insert(root, key);

29     }

30 }

31 

32 //中序遍历

33 void InorderTraversal(BiTNode *root)

34 {

35     if (root)

36     {

37         InorderTraversal(root->lchild);

38         cout << root->data << ' ';

39         InorderTraversal(root->rchild);

40     }

41 }

42 

43 //获得最小值结点

44 BiTNode *GetMinValue(BiTNode *root)

45 {

46     if (root == NULL)

47         return NULL;

48     if (root->lchild == NULL)

49         return root;

50     return GetMinValue(root->lchild);

51 }

52 

53 //获得最大值结点

54 BiTNode *GetMaxValue(BiTNode *root)

55 {

56     if (root == NULL)

57         return NULL;

58     if (root->rchild == NULL)

59         return root;

60     return GetMaxValue(root->rchild);

61 }

62 

63 bool IsContains(BiTNode *root, int key)

64 {

65     if (root == NULL)

66         return false;

67     else if (key < root->data)

68         IsContains(root->lchild, key);

69     else if (key > root->data)

70         IsContains(root->rchild, key);

71     else

72         return true;

73 }

74 

75 int main()

76 {

77     BiTNode *root = NULL;

78     int toFindVal;

79     cout << "请输入值建立二叉树（-1代表结束）";

80     Create(root);

81     cout << "中序遍历：";

82     InorderTraversal(root);

83     cout << "\n最小值：" << GetMinValue(root)->data;

84     cout << "\n最大值：" << GetMaxValue(root)->data;

85     cout << "\n请输入要查找的结点值";

86     cin >> toFindVal;

87     if (IsContains(root, toFindVal))

88         cout << "结点已查找到" << endl;

89     else

90         cout << "结点未查找到" << endl;

91 }

测试结果：

例如输入上图所示的二叉树：8 3 10 1 6 14 4 7 13

结果如下