二叉樹演算法

『壹』 二叉樹的遍歷演算法

遞歸演算法的實現是依據棧來做的，建議你看一下關於這方面的內容。
preorder()函數功能為：若當前結點不為空，則列印當前值，並遞歸調用列印左右結點。
preorder()函數在每次遞歸調用前，先將下一條指令地址和參數壓棧，即在執行preorder(root->Lchild)前，preorder(root->Rchild)地址及參數壓棧。
以後每次遞歸調用均是如此。
遞歸函數返回時，也即root=NULL時，當前preoder(root->Rchild)指令出棧，繼續向下執行，直到整個遞歸完成。
對於上述的樹，執行過程如下：
1、列印1
2、調用列印2，列印3調用壓棧
3、列印2
4、調用列印4，列印5調用壓棧
5、列印4
6、調用列印4的左結點，列印4的右結點調用壓棧
7、4無左結點，即當前結點=NULL，調用返回
8、棧中彈出列印4右結點調用
9、4無右結點，調用返回
10、棧中彈出列印5的調用
.....
一直這樣執行下去，所以列印結果為：1-2-4-5-3-6

『貳』 平衡二叉樹演算法

多值結點平衡二叉樹的結構及演算法研究
1引言
傳統的AV1.樹是一種應用較為廣泛的數據結構，適合」幾組織在內存中的較小索引.它的
每個結l從上存儲有一個關鍵字、一個平衡因子和兩個指針項，山」幾它是一棵接近」幾理想狀態的
平衡二叉樹，所以AV1.樹具有很高的查詢效率.但正如任何事物都具有兩而性一樣，AV1.樹同
樣存在比較嚴重的缺l從，一是存儲效率比較低:真正有用的關鍵字在結l從上所，片的空間比例較
小，而作為輔助信息的平衡因子和指針卻，片據較大的空間;二是額外運算量比較大:當有結l從
被插入或刪除而導致AV1.樹不平衡時，AV1.樹就需要進行調整而保持它的平衡性，山」幾每個
結l從上只有一個關鍵字，所以任何一次的數據插入或刪除都有可能導致AV1.樹的平衡調整，
這種頻繁的調整運算將大大降低AV1.樹的存取效率.為解決以上問題，結合T3樹每個結l從可
以存儲多個關鍵字項的優l側}l，木文提出了多值結l從平衡二叉樹(簡稱MAV1.樹)，它的主要特
點在」幾每個MAV1.樹的結l從都存儲有多個關鍵字項，而其它信息仍與AV1.樹一樣，即一個平
衡因子和兩個指針項.
2 MAV1.樹結構描述
MAV1.樹仍舊是一種平衡二叉樹，它的整體樹型結構和演算法也是建立在傳統的平衡二叉
樹基礎之上的.MAV1.樹的特徵在」幾它的每個結l從都可以存儲多個關鍵字(較理想的取值大約
在20} 50個之間).用C++語言描述的MAV1.樹結l從結構如卜:
struct NodeStruct
int IJ1emsOnNode;
int bf:
struct NodPStruct*lch;ld:
//一結點中項的數目
//平衡因子
//夕.子
struct NodeStruct * rchild:
}lemType }lemsi Max}lem} ;//結點中的項數組
Node T:
在這種結構中.ElemsOnNode反映的是「當前狀態卜」該結l從中關鍵字項的個數.當在此結
點插入一個關鍵字時.FlemsOnNode值加1.當刪除一個關鍵字時.則FlemsOnNode值減1.每個
結l從上可存儲的關鍵字個數介J幾1 } M axElem之間.bf為平衡因r.其作用等同J幾AV1.樹的平
衡因r. MAV1.樹的任一結l從的平衡因r只能取一1 ,0和1.如果一個結l從的平衡因r的絕對
值大」幾1.則這棵樹就失去了平衡.需要做平衡運算保持平衡.lehild和:child分別為指向左右
J"樹根結0的指針.Flems[ i]為結0中第i個關鍵字項.Flems} MaxFlem」是一個按升序排列的
關鍵字數組.具體的MAV1.樹結l從結構如圖1所示.
}lemsOnNode一h『一* leh;ld一
圖1
reh擊3
}lemsi 0}一
樹結點結構
}lemsi Max}lem}
MAVT
MAV1.樹的結構特l從使它比AV1.樹具有更高的存儲效率.在AV1.樹或MAV1.樹中.實際
有用的信急只有關鍵字.1f1! ElemsOnNode ,bf ,lehild和:child都是為了構建樹型結構If1J不得不添
加的輔助信急. MAV1.樹就是通過減小這些輔助信急的比例來獲得較高的存儲效率.山MAV1.
樹結l從的定義可以看出:FlemsOnNode和bf為int型.各，片4個位元組長度.指針型的lchild和
rchild也各，片4個位元組長度.在以上四項信急中.AV1.樹結l從除了沒有ElemsOnNode外.其餘和
MAV1.樹相同.現假設關鍵字長度為24位元組.M axFl二值定為50.則對AV1.樹來說.它的結l從
長度為36位元組.其中輔助信h,長度為12位元組;If}J MAV1.樹的結l從長度是1. 2K位元組.其中輔助
信急長度為16位元組.山此可以看出.MAV1.樹在存儲時.結l從中輔助信急長度，片整個結l從長度
的比例是很小的.它對存儲空間的利用效率比 AV1.樹要高.這一l從對」幾主要而向內存應用的
MAV1.樹來說是非常重要的.
在實際的應用中.當MAV1.樹作為資料庫索引結構時.為進一步節約內存空間.結l從中Fl-
emType的結構可根據實際需要作不同的定義.
( 1)當排序關鍵字較短時.可以直接將資料庫中的關鍵字值拷貝到索引文件中.這樣
MAV1.樹既有較快的運行速度又不會，片用太大的空間.此時ElemType定義如卜
struct IdxRlemStruct
{
int RecPos://金己錄號
KeyType Key://關鍵字
}R1emType;
( 2}當排序關鍵字較長時.如果直接將資料庫中的關鍵字值拷貝到索引文件中會，片據較大
的空間.此時可以採用只存儲關鍵字地址的形式.這樣不管關鍵字有多長.映射到MAV1.樹後
都只，片據一個指針的固定長度.這種以時間換空間的方法比較適合內存容量有限的情況.此時
ElemType定義如卜
struct Tdxl?lemStruct
int RecPos:
char * Key
R1emType;
//記錄號
//關鍵字指釗
3基於MAUI.樹的運算
MAUI.樹的基木運算.包括MAUI.樹的建立、記錄的插入、刪除、修改以及查詢.這些演算法
與基J幾AVI.樹的演算法相似.都建立在一叉查詢和平衡演算法基礎上.
3. 1 MAVI,樹的平衡運算
如果在一棵原木是平衡的MAUI.樹中插入一個新結l從.造成了不平衡.此時必須調整樹的
結構.使之平衡化「21 .MAUI.樹的平衡演算法與AVI.樹的平衡演算法是相同的.但山J幾MAUI.樹的
每個結l從中都存儲有多個關鍵字.所以在關鍵字個數相同的情況卜. MAUI.樹的應用可以大大
減少平衡運算的次數.例如.假設具有n個關鍵字的待插入序列在插入過程中有5%(根據隨
機序列特l從的不同.此數值會有所差異.這里以比較保守的5%為例)的新產生結l從會導致一
叉樹出現不平衡.對AVI.樹來說.山」幾需要為每個關鍵字分配一個結l從.所以在整個插入過程
中做平衡的次數為n * 5%;對J幾MAUI.樹.設MAUI.樹中M axFl二的值被定義為k(k為大J幾1
的正整數少，則平均每k次的數據插入才會有一個新結l從產生，所以在整個插入過程中需做平
衡的次數僅為(nlk) * 5%.即在M axFl二取值為k的情況卜.對」幾相同的待插入關鍵字序列.
在插入過程中MAUI.樹用J幾平衡運算的開銷是AVI.樹的1/ k.
3. 2數據查找
在MAUI.樹上進行查找.是一個從根結l從開始.沿某一個分支逐層向卜進行比較判等的過
程.假設要在MAUI.樹上查找的值為GetKey.查找過程從根結l從開始.如果根指針為NU1.1..則
查找失敗;否則把要查找的值GetKey與根結l從關鍵字數組中的最小項Elems [ 0]進行比較.如
果GetKev小」幾當前結i最小關鍵字.則遞歸查找左r樹;如果GetKey'大」幾Elems [ 0].則將
GetKey'與根結0關鍵字數組中的最大項Fletns} MaxFl二一1]進行比較.如果GetKey'大」幾當前
結l從最大關鍵字.則遞歸查找右r樹;否則.對當前結l從的關鍵字數組進行查找(山」幾是有序序
列.可以採用折半查找以提高效率).如果有與GetKey'相匹配的值.則查找成功.返回成功信
息,7{報告查找到的關鍵字地址.
3. 3數據插入
數據插入是構建MAV1.樹的基礎.設要在MAV1.樹*T上插入一個新的數據兀素GetKev,
其遞歸演算法描述如卜:
(1)若*T為空樹.則申清一新結} ' Elems} MaxElem}.將GetKey'插入到Flems[ 0]的位置.樹
的深度增1.
(2)若*T未滿.則在*T中找到插入位置後將GetKey'插入.JI在插入後保持結l從中的各
關鍵項有序遞增.若己存在與GetKev相同的項.則不進行插入.
(3)如果*T為滿結l從目一GetKey'值介」幾Flems[ 0]和Flems} MaxFlem]之間.則在*T中找到
GetKev的插入位置posit ion.山」幾*T木身就是滿結l從.所以GetKev的插入必然會將原來*T中
的某個數據擠出去JI卜降到r樹中.根據插入位置position的不同.分以卜幾種情況處理:若*
T中存在與C etl} e`'相同的項.則不進行插入;若插入位置在*T結ii的前半部分(即position <
=MaxFlem/ 2).則將Flems[ 1]到Fletns} position」的數據依次左移一位.再把GetKey插入到Elems
} MaxFlem」中position的位置.Ifn原來*T中最左邊項數據將被擠入到*T的左r樹中.考察此
數據的特l從.它必然大」幾*T左r樹中的任一數據項.所以此時不需要作任何的額外運算.直
接將此數據插入到*T左r樹根結i從的最右r孫位置處就可以了(見圖2中插入，}} 11"後「1,>
的位置變化);若插入位置在*T結ii的後半部分(即position> MaxFlem/ 2).則將Fletns} posi-
tion}到Fletns} MaxFl二一2}的數據依次右移一位.再把GetKev插入到*T結0中position的位
置.與前一種情況類似.結l從中最右邊被擠出的項將被插入到*T的右r樹根結l從的最左r孫
的位置(見圖2中插入「25"後" 30"的位置變化).
插入，"}i」插入」zs0
}o i is i }a
s}土 s
圖2
滿結點插入數據的過程
(4)若GetKey的值小」幾T的最小項值.則將GetKey遞歸插入到T的左r樹中.即在遞歸調
用時GetKey值不變Ifn T= T->lehild.
(5)若GetKey的值大」幾T的最大項值.則將GetKey遞歸插入到T的右r樹中.即在遞歸調
用時GetKey值不變Ifn T= T->rehild.
4結束語
山J幾MAV1.樹的結l從中存儲有多個關鍵字值.所以它具有較高的存儲效率;對MAV l樹進
行查找是_分查找和順序查找的結合.其查詢效率只略低」幾AV1.樹.血山」幾MAV1.樹的平衡
運算比AV1.樹要少得多.所以MAV1.樹有很優秀的綜合運算效率.綜上所述.在數據量大、內
存容量相對較小、數據增刪運算比較頻繁的情況卜.用MAV1.樹作為常駐內存的索引結構是一
種理想的選擇.

『叄』 二叉樹演算法是什麼

二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。

性質

1、在二叉樹中，第i層的結點總數不超過2^(i-1)。

2、深度為h的二叉樹最多有2^h-1個結點（h>=1)，最少有h個結點。

3、對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1。

『肆』 二叉樹的深度演算法怎麼算啊

二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加1即是樹的深度，遞歸返回的條件是若節點為空，返回0
演算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非遞歸實現基本思想：
受後續遍歷二叉樹思想的啟發，想到可以利用後續遍歷的方法來求二叉樹的深度，在每一次輸出的地方替換成算棧S的大小，遍歷結束後最大的棧S長度即是棧的深度。
演算法的執行步驟如下：
（1）當樹非空時，將指針p指向根節點，p為當前節點指針。
（2）將p壓入棧S中，0壓入棧tag中，並令p執行其左孩子。
（3）重復步驟（2），直到p為空。
（4）如果tag棧中的棧頂元素為1，跳至步驟（6）。從右子樹返回
（5）如果tag棧中的棧頂元素為0，跳至步驟（7）。從左子樹返回
（6）比較treedeep與棧的深度，取較大的賦給treedeep，對棧S和棧tag出棧操作，p指向NULL，並跳至步驟（8）。
（7）將p指向棧S棧頂元素的右孩子，彈出棧tag，並把1壓入棧tag。（另外一種方法，直接修改棧tag棧頂的值為1也可以）
（8）循環（2）~（7），直到棧為空並且p為空
（9）返回treedeep，結束遍歷
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}

『伍』 二叉樹演算法

二叉樹是沒有度為1的結點。

完全二叉樹定義：
若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層從右向左連續缺若干結點，這就是完全二叉樹。

完全二叉樹葉子結點的演算法：
如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。
可以根據公式進行推導，假設n0是度為0的結點總數（即葉子結點數），n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可知：n0＝n2＋1，則n= n0＋n1＋n2（其中n為完全二叉樹的結點總數），由上述公式把n2消去得：n= 2n0+n1－1，由於完全二叉樹中度為1的結點數只有兩種可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合並成一個公式：n0＝（n＋1）/2 ，就可根據完全二叉樹的結點總數計算出葉子結點數。

因此葉子結點數是(839+1)/2=420

『陸』 二叉樹 演算法

原因就在於Status CreatBitTree(BitTree e) 這個函數的參數BitTree e，既然e是參數，因此你在函數體內用e=NULL; 及e=(BitTree)malloc(sizeof(BitNode)); 來給e賦值都是沒有用的，賦值不會返回給調用處。修改的話改成引用就可以了。也就是把Status CreatBitTree(BitTree e) 這一行改成Status CreatBitTree(BitTree &e) 就行了。

還有：二叉樹演算法遞歸中序輸入是abc##de#g##f### （你這應該是前序輸入吧？）

『柒』 二叉樹結點的演算法

一個結點的度是指該結點的子樹個數。
度為1就是指只有1個子樹（左子樹或者右子樹）。
度為2的結點個數=葉結點個數-1=69
該二叉樹的總結點數=70+80+69=219

『捌』 C語言二叉樹遞歸演算法怎麼做

#include<stdio.h>
#include<string.h>

structtreenode{
intvalue;
treenode*left;
treenode*right;
};
typedeftreenode*BiTree;

voidvisit(treenode*node)
{
printf("%2d",node->value);
}

//結點總數
intnode(BiTreeT)
{
if(!T){
return0;
}
returnnode(T->left)+node(T->right)+1;
}

//前序
voidpreOrder(BiTreeT)
{
if(T){
visit(T);
preOrder(T->left);
preOrder(T->right);
}
}

//中序
voidinOrder(BiTreeT)
{
if(T){
inOrder(T->left);
visit(T);
inOrder(T->right);
}
}

//後序
voidpostOrder(BiTreeT)
{
if(T){
postOrder(T->left);
postOrder(T->right);
visit(T);
}
}

//葉子節點數
intleafnode(BiTreeT)
{
if(T){
if(!T->left&&!T->right)
return1;
else
leafnode(T->left)+leafnode(T->right);
}else{
return0;
}
}

intheight(BiTreeT)
{
if(T){
intlh=height(T->left);
intrh=height(T->right);
return(lh>rh?lh:rh)+1;
}else{
return0;
}
}

intmain()
{


return0;
}

『玖』 二叉樹的演算法

用棧來實現。

『拾』 二叉樹遍歷的演算法

void PreOrder(BiTree t) { /* 二叉樹的先序遍歷演算法 */
if(t!=NULL) {
putchar (t->data);
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}

void InOrder(BiTree t) { /* 二叉樹的先中序遍歷演算法 */
if(t != NULL) {
InOrder(t->lchild);
putchar(t->data);
InOrder(t->rchild);
}
}

void PostOrder(BiTree t) { /* 二叉樹的後序遍歷演算法 */
if(t != NULL) {
PostOrder(t->lchild);
PostOrder(t->rchild);
putchar(t->data);
}
}