二叉排序樹的構建（二叉排序樹怎么構造）

大家好，我是小夏，我來為大家解答以上問題。二叉排序樹的構建，二叉排序樹怎么構造很多人還不知道，現在讓我們一起來看看吧！

1、二叉排序樹的構造過程：按照給定序列，以此將結點插入二叉排序樹中，在二叉排序樹中插入新結點，要保證插入后的二叉樹仍符合二叉排序樹的定義。

2、　　插入過程：若二叉排序樹為空，則待插入結點*S作為根結點插入到空樹中；

3、　　當非空時，將待插結點關鍵字S->key和樹根關鍵字t->key進行比較，

4、　　若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，

5、　　若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，

6、　　如此進行下去，直到把結點*s作為一個新的樹葉插入到二叉排序樹中，或者直到發現樹已有相同關鍵字的結點為止。

7、　　說明：

8、　　① 每次插入的新結點都是二叉排序樹上新的葉子結點。

9、　　② 由不同順序的關鍵字序列，會得到不同二叉排序樹。

10、　　③ 對于一個任意的關鍵字序列構造一棵二叉排序樹，其實質上對關鍵字進行排序。

11、查找的過程類似，從根結點開始進行比較，小于根結點的在左子樹上，大于根結點的在右子樹上，以此查找下去，直到查找成功或不成功（比較到葉子結點）。

本文到此講解完畢了，希望對大家有幫助。