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

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

本文導(dǎo)航

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

二叉樹什么情況下使用

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

這是數(shù)據(jù)結(jié)構(gòu)當(dāng)中對結(jié)點(diǎn)進(jìn)行訪問

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

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

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

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

后序遍歷是：DEBFCA

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

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

二叉樹遍歷對照表

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

規(guī)則：

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

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é)點(diǎn)，w為u的右孩子

s

/

t

/ \

u v

\

w

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

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

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

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

若右子樹不空，則右字?jǐn)?shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值

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

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

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

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

二叉排序樹要么是空二叉樹，要么具有如下特點(diǎn)：

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

二叉排序樹怎么找長度

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

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

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

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