什么是二叉排序樹畫圖 二叉樹遍歷對照表

什么是二叉樹？數(shù)據(jù)結(jié)構(gòu) 二叉排序樹的題 誰能給我畫圖 給我講講啊謝謝謝謝，某二叉樹的前根次序列遍歷結(jié)果為stuwv，中序遍歷為uwtvs，則該二叉樹的后序是什么？如何畫圖？什么是二叉排序樹？什么是二叉排序樹？什么叫二叉排序樹？

本文導航

• 二叉樹什么情況下使用
• 如何構(gòu)造最佳二叉排序樹
• 二叉樹遍歷對照表
• 什么是最優(yōu)二叉查找樹
• 平衡二叉排序樹有什么特征
• 二叉排序樹怎么找長度

二叉樹什么情況下使用

在計算機科學中，二叉樹是每個結(jié)點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left;subtree）和“右子樹”（right;subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的;i;-1次方個結(jié)點；深度為k的二叉樹至多有2^(k);-1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)(即葉子結(jié)點數(shù))為n0，度為2的結(jié)點數(shù)為n2，則n0;=;n2;+;1。

這是數(shù)據(jù)結(jié)構(gòu)當中對結(jié)點進行訪問

遍歷分分先序、中序、后序

先序：先訪問根結(jié)點、左結(jié)點、右結(jié)點

中序：先訪問左結(jié)點、根結(jié)點、右結(jié)點

后序：先訪問左結(jié)點、右結(jié)點、根結(jié)點

后序遍歷是：DEBFCA

如何構(gòu)造最佳二叉排序樹

構(gòu)造平衡的二叉排序樹:;{34,23,15,98,115,28}以下是詳細過程:(1);插入34,;這是第一個結(jié)點,是根結(jié)點.(2);插入23,;比34小,作為34的左分支.;;;;;;;;;34;;;;;;;;/;;;;;;23(3);插入15,;比34和23都小,15作為23的左分支,結(jié)點34的平衡因子BF變成2(左子樹過高),;;;;要右旋(就是順時針旋轉(zhuǎn)),旋轉(zhuǎn)后,結(jié)點23成為根結(jié)點.;;;;;;;;;;34;;;;;;;;;;/;;;;;;;;;;;;;23;;;;;;;;;;;;23;;;;;;/;;;;;;;;;;;;;/;;\;;;;;15;;;;;;;;;;;;15;;34;;;;;;;;;;;;;;;;;;;右旋之后;;;;平衡因子BF(Balance;Factor)就是:;;;;將二叉樹上結(jié)點的;左子樹深度;減去;右子樹深度的值.(4);插入98,;結(jié)點23的BF是-1,結(jié)點34的BF是-1,二叉樹仍然保持平衡.;;;;;;;23;;;;;;/;;\;;;;;15;;34;;;;;;;;;;;\;;;;;;;;;;;98(5);插入115,;結(jié)點34的BF是-2,;結(jié)點23的BF是-2,就是右子樹過高,;;;;結(jié)點34,98,115需要左旋(就是逆時針旋轉(zhuǎn)),;;;;旋轉(zhuǎn)后,結(jié)點98的BF是0,;結(jié)點23的BF是-1,二叉樹保持平衡.;;;;;;;23;;;;;;;;;;;;;;;;23;;;;;;/;;\;;;;;;;;;;;;;;/;;\;;;;;15;;34;;;;;;;;;;;;15;;98;;;;;;;;;;;\;;;;;;;;;;;;;;/;;\;;;;;;;;;;;98;;;;;;;;;;;;34;;115;;;;;;;;;;;;;\;;;;;;;;;;;;;115;;;;;;;左旋之后(6);插入28,;結(jié)點23的BF是-2,;結(jié)點98的BF是1,;兩個符號不一致,;;;;結(jié)點98,34,28先右旋,此時,結(jié)點23的BF是-2,;結(jié)點34的BF是-1,;;;;兩個符號一致,結(jié)點15,23,34進行左旋,此時,二叉樹保持平衡.;;;;;;;;;;;;;23;;;;;;;;;;;;23;;;;;;;;;;;;;;;;;;34;;;;;;;;/;;\;;;;;;;;;;/;;\;;;;;;;;;;;;;;;;/;;\;;;;;;;15;;98;;;;;;;;15;;34;;;;;;;;;;;;;;23;;;98;;;;;;;;;;/;;\;;;;;;;;;;/;;\;;;;;;;;;;;;/;;\;;;\;;;;;;;;;34;;115;;;;;;;28;;98;;;;;;;;;;15;;28;;115;;;;;;;;/;;;;;;;;;;;;;;;;;;;;\;;;;;;;28;;;;;;;;;;;;;;;;;;;;115;;;;;;;;;;;;;;;;;;;;;右旋之后;;;;;;;;;;;;左旋之后;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;這就是最后得到的平衡二叉排序樹

二叉樹遍歷對照表

對于先序遍歷stuwv, 和中序遍歷uwtvs可以這么分析：

規(guī)則：

1）先序遍歷確定父節(jié)點

2）中序遍歷確定左右子樹

分析過程：

1、由前序遍歷可知s為樹的根

s

tuwv

2、結(jié)合中序遍歷可知：tuwv為s左子樹的先序遍歷， uwtv為s左子樹的中序遍歷

3、同理判斷t為左子樹的根,uw為t的左子樹， v為t的右子樹

s

t

uw v

4、遞歸判斷t的左子樹可知： 其先序遍歷和中序遍歷均為uw，判斷u為子樹的根節(jié)點，w為u的右孩子

s

/

t

/ \

u v

\

w

由此可知其后序遍歷為：wuvts

什么是最優(yōu)二叉查找樹

二叉排序樹（Binary Sort Tree），首先它是一棵樹，“二叉”這個描述已經(jīng)很明顯了，就是樹上的一根樹枝開兩個叉，于是遞歸下來就是二叉樹了（下圖所示），而這棵樹上的節(jié)點是已經(jīng)排好序的，具體的排序規(guī)則如下：

若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值

若右子樹不空，則右字數(shù)上所有節(jié)點的值均大于它的根節(jié)點的值

它的左、右子樹也分別為二叉排序數(shù)（遞歸定義）

從圖中可以看出，二叉排序樹組織數(shù)據(jù)時，用于查找是比較方便的，因為每次經(jīng)過一次節(jié)點時，最多可以減少一半的可能，不過極端情況會出現(xiàn)所有節(jié)點都位于同一側(cè)，直觀上看就是一條直線，那么這種查詢的效率就比較低了，因此需要對二叉樹左右子樹的高度進行平衡化處理，于是就有了平衡二叉樹（Balenced Binary Tree）

所謂“平衡”，說的是這棵樹的各個分支的高度是均勻的，它的左子樹和右子樹的高度之差絕對值小于1，這樣就不會出現(xiàn)一條支路特別長的情況。于是，在這樣的平衡樹中進行查找時，總共比較節(jié)點的次數(shù)不超過樹的高度，這就確保了查詢的效率（時間復雜度為O(logn)）

平衡二叉排序樹有什么特征

二叉排序樹要么是空二叉樹，要么具有如下特點：

• 二叉排序樹中，如果其根結(jié)點有左子樹，那么左子樹上所有結(jié)點的值都小于根結(jié)點的值；
• 二叉排序樹中，如果其根結(jié)點有右子樹，那么右子樹上所有結(jié)點的值都大小根結(jié)點的值；
• 二叉排序樹的左右子樹也要求都是二叉排序樹；

二叉排序樹怎么找長度

1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；

（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；

（3）左、右子樹也分別為二叉排序樹；

（4）沒有鍵值相等的結(jié)點。