1樓：鄭芬多老師
二叉排序樹（binary sort tree），又稱二叉查詢樹（binary search tree），亦稱二叉搜尋樹。是資料結構中的一類。在一般情況下，查詢效率比連結串列結構要高。
定義一：一棵空樹，或者是具有下列性質的二叉樹：
1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
3）左、右子樹也分別為二叉排序樹；
4）沒有鍵值相等的結點。
定義二：一棵空樹，或者是具有下列性質的二叉樹：
1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
2）若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
3）左、右子樹也分別為二叉排序樹。
定義三：一棵空樹，或者是具有下列性質的二叉樹：
1）若左子樹不空，則左子樹上所有結點的值均小於或等於它的根結點的值；
2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
3）左、右子樹也分別為二叉排序樹；
注】：以上的三種定義在不同的資料結構教材中均有不同的定義方式 但是都是正確的 在開發時需要根據不 同的需求進行進行選擇。
插入刪除：與次優二叉樹相對，二叉排序樹是一種動態樹表。其特點是：
樹的結構通常不是一次生成的，而是在查詢過程中，當樹中不存在關鍵字等於給定值的結點時再進行插入。新插入的結點一定是乙個新新增的葉子結點，並且是查詢不成功時查詢路徑上訪問的最後乙個結點的左孩子或右孩子結點。
2樓：微言悚聽
首先二叉排序樹也是一棵二叉樹，所謂二叉樹，就是“任何節點最多只允許兩個子節點”，這兩個子節點稱為左右子節點。
二叉排序樹通常採用二叉連結串列作為儲存結構。中序遍歷二叉排序樹可得到乙個依據關鍵字的有序序列，乙個無序序列可以通過構造一棵二叉排序樹變成乙個有序序列，構造樹的過程即是對無序序列進行排序的過程。每次插入的新的結點都是二叉排序樹上新的葉子結點，在進行插入操作時，不必移動其它結點，只需改動某個結點的指標，由空變為非空即可。
二叉排序樹性質：
1、就是若它的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
2、若它的右子樹不空，則右子樹上所有節點的值均大於其根節點的值。
3、換句話說就是：任何節點的鍵值一定大於其左子樹中的每乙個節點的鍵值，並小於其右子樹中的每乙個節點的鍵值。
3樓：生活達人小桃子
一、定義。二叉排序樹，又叫二叉查詢樹，它或者是一棵空樹；或者是具有以下性質的二叉樹：
1. 若它的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
2. 若它的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
3. 它的左右子樹也分別為二叉排序樹。
二叉搜尋樹（bst）又稱二叉查詢樹或二叉排序樹。一棵二叉搜尋樹是以二叉樹來組織的，可以使用乙個連結串列資料結構來表示，其中每乙個結點就是乙個物件。一般地，除了key和衛星資料之外，每個結點還包含屬性lchild、rchild和parent，分別指向結點的左孩子、右孩子和雙親（父結點）。
如果某個孩子結點或父結點不存在，則相應屬性的值為空（nil）。根結點是樹中唯一父指標為nil的結點，而葉子結點的孩子結點指標也為nil。
4樓：封琴瑟煙雨冢
在 電腦科學中， 二叉搜尋樹(bst)，有時也被稱為二叉排序樹，是一種特殊型別的容器： 在記憶體中儲存“專案”（例如數字，名稱等）的資料結構。它們允許快速查詢、新增和刪除專案，並且可以用於實現動態專案集，或者允許通過其關鍵字查詢專案的查詢表(例如，通過名稱查詢人員的**號碼)。
二叉排序樹有序儲存它們的關鍵字，以便查詢和其他操作可以使用 二分的原則：當在樹中尋找關鍵字(或插入新關鍵字的位置)時，他們從根到葉遍歷樹，與儲存在樹結點中的關鍵字進行比較，並根據比較結果決定繼續在左或右子樹中搜尋。平均而言，這意味著每次比較都允許操作跳過樹的大約一半結點，因此每次查詢、插入或刪除都需要儲存在樹中的專案數的對數級別的時間複雜度。
這比在(未排序的)陣列中按關鍵字查詢專案需要的線性時間複雜的好多了 ，但比雜湊表上的相應操作要慢。
電腦科學出現了二叉排序樹的幾種變體；本文主要討論基本型別，並在適當的時候引用更高階的型別。
二叉排序樹是帶根結點的二叉樹，其內部結點各自儲存乙個關鍵字(以及可選的相關值),並且各自具有兩個可區分的子樹，通常表示為左和右。該樹還擁有二分搜尋的屬性，該屬性宣告每個結點中的關鍵字必須大於或等於左子樹中儲存的任何關鍵字，並且小於或等於右子樹中儲存的任何關鍵字。[1] 樹的葉子(最終結點)不包含關鍵字，也沒有結構來區分它們。
通常，每個結點代表的資訊是一條記錄，而不是乙個資料元素。 然而，出於排序的目的，結點是根據它們的關鍵字而不是它們相關記錄的任何部分進行比較的。二叉排序樹相對於其他資料結構的主要優勢是在分類演算法和 搜尋演算法比如有序遍歷中非常有效；它們也很容易編碼。
二叉排序樹的形狀完全取決於插入和刪除的順序，並且可能退化。
在長時間隨機插入和刪除的混合序列之後，樹的預期高度接近關鍵字數量的平方根 √n，它的增長速度比 log n快得多。
已經有許多研究來防止樹的退化，這種退化導致最壞情況下的時間複雜度 o(n) (有關詳細資訊，請參見部分)。
二叉樹和二叉排序樹有啥區別
5樓：生活仁昌
二叉樹和二叉排序樹區別為：子樹結點不同、鍵值相等不同、子樹樹型不同。
一、子樹結點不同。
1、二叉樹：二叉樹的左/右子樹上所有結點的值可以大於、等於和小於它的根結點的值。
2、二叉排序樹：二叉排序樹若左/右子樹不空，則左/右子樹上所有結點的值均小於它的根結點的值。
二、鍵值相等不同。
1、二叉樹：二叉樹可以有鍵值相等的結點。
2、二叉排序樹：二叉排序樹沒有鍵值相等的結點。
三、子樹樹型不同。
1、二叉樹：二叉樹的左、右子樹也分別為二叉樹。
2、二叉排序樹：二叉排序樹的左、右子樹也分別為二叉排序樹。
6樓：網友
一棵空樹，或者是具有下列性質的二叉樹：
1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
3）左、右子樹也分別為二叉排序樹；
4）沒有鍵值相等的結點。
7樓：實若谷靖璧
兄弟，你看考綱的時候要認真一點，二叉排序樹和平衡二叉樹在樹與二叉樹的那一章是要求的。
二叉排序樹怎麼構造
8樓：旅遊達人在此
假設二叉排序樹t為空，則建立乙個keyword為k的結點。將其作為根結點。
否則將k和根結點的keyword進行比較，假設相等則返回，假設k小於根結點的keyword則插入根結點的左子樹中，否則插入根結點的右子樹中。
int insertbst(bstnode *p, keytype k)
else if(k==p->key)
return 0;
else if(kkey)
return insertbst(p->lchild, k);
elsereturn insertbst(p->rchild, k);
二叉排序樹的生成演算法：
bstnode *createbst(keytype a,int n)
bstnode *bt=null;
int i=0;
while(i<>
請問平衡二叉樹和二叉排序樹的關係
平衡二叉樹和二叉排序樹沒有關係,他們的定義都不相同。由於平衡二叉樹的設計是為了改進二叉排序樹的效能,所以他的插入和刪除按排序樹的來 討論 請問 平衡二叉樹和二叉排序樹的關係 看你的插入演算法是怎樣的了,平衡二叉樹未必是二叉排序樹,比如二路堆就可以實現為平衡二叉樹,且非二叉排序樹。平衡二叉樹和二叉排序...
將二叉樹轉化為樹森林將樹森林轉化為二叉樹的基本目的是什麼
二叉樹轉bai換為森林 前提 加入一棵 du二叉zhi樹的根節點有右孩子dao，則這棵二叉樹專能夠轉換為屬森林，否則轉換為一棵樹。轉換規則 1 從根節點開始，若右孩子存在，則把與右孩子結點的連線刪除。再檢視分離後的二叉樹，若其根節點的右孩子存在，則連續刪除。直到所有這些根結點與右孩子的連線都刪除為止...
二叉樹的層次遍歷演算法，二叉樹層次遍歷怎麼進行？
建立一個佇列q 將根放入佇列 while 佇列非空 求用c語言實現二叉樹層次遍歷的遞迴演算法，謝謝！二叉樹層次遍歷怎麼進行？設計一個演算法層序遍歷二叉樹 同一層從左到右訪問 思想 用一個佇列儲存被訪問的當前節點的左右孩子以實現層序遍歷。void hierarchybitree bitree root...