二叉排序树的实现

今天数据结构老师讲到了二叉树，还提了一下二叉排序树，然后我就纠结了，就实现来说，二叉排序树比堆排序简单多了。并且二叉排序树时间复杂度并不比堆排高...为毛排序中没有提到它？然后从教学区走到饭堂一直在想这个问题。。但是想着想着就拿各种排序来进行对比了。。。就没有然后了。。。。

下面我来说说怎么用二叉排序树排序吧。

首先是构建二叉排序树，二叉排序树的特点是：

左节点的所有元素比根节点小，右节点所有元素比根节点大。

那么在构建二叉排序树的时候，插入的元素一定是插某个在叶子上的。在刚听到这个的时候我诧异了下，难道不用再进行像堆排序那样的堆化操作？然后我画了下图发现还真是这样。然后我反应过来，，这样的话也太方便了吧。。我要构造一颗二叉排序树的话，只需要找到某个叶节点然后接到他的左或右节点即可啊。。。

假设已经有如图所示的树：，我要插入3的话，首先 3 < 4，那就在节点4的左边，然后因为3 > 1，所以3 插在节点1的右边。其实更多的元素的话原理是一样的。所以最终你会发现所有的元素都是在叶节点上插入的。所以初始化树的代码如下：

 1 Node* initializeTree(int* arrayL, int len) {
 2     Node *root = new Node(arrayL[0]);
 3     Node *temp;
 4     Node *temp2 = root;
 5     for (int i = 1; i != len; i++) {
 6         temp = root;
 7         Node* newNode = new Node(arrayL[i]);
 8         //temp2记录temp根节点的位置用于下面的插入
 9         while (temp != NULL) {
10             temp2 = temp;
11             if (arrayL[i] >= temp->value)
12                 temp = temp->right;
13             else
14                 temp = temp->left;
15         }
16         if (arrayL[i] >= temp2->value)
17                 temp2->right = newNode;
18             else
19                 temp2->left = newNode;
20     }
21     return root;
22 }

这里我们不能直接这样写：

 1 Node* initializeTree(int* arrayL, int len) {
 2     Node *root = new Node(arrayL[0]);
 3     Node *temp;
 4     for (int i = 1; i != len; i++) {
 5         temp = root;
 6         Node* newNode = new Node(arrayL[i]);
 7         while (temp != NULL) {
 8             if (arrayL[i] >= temp->value)
 9                 temp = temp->right;
10             else
11                 temp = temp->left;
12         }
13         temp = newNode;
14     }
15     return root;
16 }

注意有没有temp2的区别，当temp遍历到值为NULL的时候，也就是说 temp = temp->right; 或 temp = temp->left; 有些人会误以为这样直接将newNode赋给temp就相当于上面那个例子的 temp2->right = newNode; 因为此时temp就等于temp2嘛。但是仔细想想，temp = temp->right;这条式子只是将一个NULL赋给temp而已，并没有其他的作用。那么在 temp = newNode;的时候，未赋值之前的 temp是NULL的。它并没有被分配内存，因为此时它并不是代表着 temp->right或temp->left。

既然二叉排序树构造好了，那就应该排序了。我们观察树的结构可以发现，利用中序遍历得到的结果就是一个从小到大的有序列。那么我们就可以采用简单的递归来完成了。

1 void inOrderTraverse(Node* root) {
2     if (root != NULL) {
3         InOrderTraverse(root->left);
4         printf("%d ", root->value);
5         InOrderTraverse(root->right);
6     }
7 }

所以最终的程序如下：

 1 #include <iostream>
 2 #include <stdio.h>
 3 
 4 using namespace std;
 5 
 6 struct Node{
 7     int value;
 8     Node* left;
 9     Node* right;
10     Node(int temp = 0) {
11         value = temp;
12         left = NULL;
13         right = NULL;
14     }
15 };
16 
17 Node* initializeTree(int* arrayL, int len) {
18     Node *root = new Node(arrayL[0]);
19     Node *temp;
20     Node *temp2 = root;
21     for (int i = 1; i != len; i++) {
22         temp = root;
23         Node* newNode = new Node(arrayL[i]);
24         //temp2记录temp根节点的位置用于下面的插入
25         while (temp != NULL) {
26             temp2 = temp;
27             if (arrayL[i] >= temp->value)
28                 temp = temp->right;
29             else
30                 temp = temp->left;
31         }
32         if (arrayL[i] >= temp2->value)
33                 temp2->right = newNode;
34             else
35                 temp2->left = newNode;
36     }
37     return root;
38 }
39 
40 void inOrderTraverse(Node* root) {
41     if (root != NULL) {
42         inOrderTraverse(root->left);
43         printf("%d ", root->value);
44         inOrderTraverse(root->right);
45     }
46 }
47 void binarySort(int* arrayL, int len) {
48     Node* arrayS = initializeTree(arrayL, len);
49     inOrderTraverse(arrayS);
50 }
51 int main(int argc, char const *argv[])
52 {
53     int lenOfArray;
54     int *arrayL;
55 
56     printf("Enter the len of the array: ");
57     scanf("%d", &lenOfArray);
58 
59     arrayL = new int[lenOfArray];
60     printf("Enter the element of array: ");
61     for (int i = 0; i != lenOfArray; i++)
62         scanf("%d", &arrayL[i]);
63 
64     binarySort(arrayL, lenOfArray);
65     
66     delete []arrayL;
67     return 0;
68 }

View Code

二叉排序树的实现

推荐阅读