二叉树算法

‘壹’ 二叉树的遍历算法

递归算法的实现是依据栈来做的，建议你看一下关于这方面的内容。
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);
}
}