二叉树算法总结

㈠ 二叉树的算法

如果一棵具有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

㈡ 怎样实现二叉树的前序遍历的非递归算法

在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：
[cpp]
view
plain

print?
int
(const
BiTree
&T,
int
(*VisitNode)(TElemType
data))
{
if
(T
==
NULL)
{
return
-1;
}
BiTNode
*pBiNode
=
T;
SqStack
S;
InitStack(&S);
Push(&S,
(SElemType)T);
while
(!IsStackEmpty(S))
{
while
(pBiNode)
{
VisitNode(pBiNode->data);
if
(pBiNode
!=
T)
{
Push(&S,
(SElemType)pBiNode);
}
pBiNode
=
pBiNode->lchild;
}
if(pBiNode
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
}
if
(
pBiNode->rchild
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
//如果此时栈已空，就有问题
}
pBiNode
=
pBiNode->rchild;
}
return
0;
}

㈢ 二叉树算法是什么

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

二叉树的第i层至多有2^（i 1）个结点；深度为k的二叉树至多有2^k 1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。

二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

(3)二叉树算法总结扩展阅读：

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：

1、空二叉树——(a)

2、只有一个根结点的二叉树——(b);

3、右子树为空的二叉树——(c);

4、左子树为空的二叉树——(d);

5、完全二叉树——(e)

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

㈣ 二叉树算法有哪些应用场景

二叉树常被用于实现二叉查找树和二叉堆。

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。

根据不同的用途可分为：

1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

(4)二叉树算法总结扩展阅读

深度为h的二叉树最多有个结点(h>=1)，最少有h个结点。对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。

有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系为若I为结点编号则 如果I>1，则其父结点的编号为I/2。如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I。若2*I>N，则无左孩子。如果2*I+1<=N，则其右孩子的结点编号为2*I+1。

㈤ 求二叉树的基本算法和各种遍历算法

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) //按先序次序输入二叉树中结点的值，构造二叉树链表
{
char ch;
ch=getchar();
if(ch==' ')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status PreOrder(BiTree T) //先序遍历的递归算法
{
if(T)
{
cout<<T->data;
PreOrder(T->lchild);
PreOrder(T->rchild);
}
return OK;
}
Status InOrder(BiTree T) //中序遍历的递归算法
{
if(T)
{
InOrder(T->lchild);
cout<<T->data;
InOrder(T->rchild);
}
return OK;
}
Status PostOrder(BiTree T) //后续遍历的递归函数
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
cout<<T->data;
}
return OK;
}
Status BiTreeLevelOrder(BiTree T) //层序遍历的非递归函数
{
int front=0,rear=0;
BiTree p,Q[20];
if(T)
{
rear++;
Q[rear]=T;
}
while(front!=rear)
{
front++;
p=Q[front];
cout<<p->data;
if(p->lchild)
{
rear++;
Q[rear]=p->lchild;
}
if(p->rchild)
{
rear++;
Q[rear]=p->rchild;
}
}
return OK;
}
Status BiTreeNodeSum(BiTree T) //计算二叉树的结点数
{

if(T==NULL)
return 0;
else
return 1+BiTreeNodeSum(T->lchild)+BiTreeNodeSum(T->rchild);
}
Status BiTreeLeafSum(BiTree T) //计算二叉树的叶子结点数
{
if(T==NULL)
return 0;
else
if(T->lchild==NULL&&T->rchild==NULL)
return 1;
else
return BiTreeLeafSum(T->lchild)+BiTreeLeafSum(T->rchild);
}
Status BiTreeDeep(BiTree T) //计算二叉树的深度
{
if(T==NULL)
return 0;
else
return (BiTreeDeep(T->lchild)>BiTreeDeep(T->rchild))?(BiTreeDeep(T->lchild)+1):(BiTreeDeep(T->rchild)+1);
}

void main() //主函数
{
BiTree T;
cout<<"input Bitree char:"<<endl;
CreateBiTree(T);
cout<<"先序遍历为："<<endl;
PreOrder(T);
cout<<endl;
cout<<"中序遍历为："<<endl;
InOrder(T);
cout<<endl;
cout<<"后序遍历为："<<endl;
PostOrder(T);
cout<<endl;
cout<<"层序遍历为："<<endl;
BiTreeLevelOrder(T);
cout<<endl;
BiTreeNodeSum(T);
cout<<"二叉树的结点数："<<BiTreeNodeSum(T)<<endl;
BiTreeLeafSum(T);
cout<<"二叉树的叶子结点数为："<<BiTreeLeafSum(T)<<endl;
BiTreeDeep(T);
cout<<"二叉树的深度为："<<BiTreeDeep(T)<<endl;
}

㈥ 二叉树算法

二叉树是没有度为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

㈦ 二叉树的遍历算法

void
preorder(BiTree
root)
/*先序遍历输出二叉树结点，root为指向二叉树根节点的指针*/
{
if（root!=NULL）
{
printf(root->data);
preorder(root->Lchild);
preorder(root->Rchild);
}
}
你看好这个程序,你首先定义了一个preorder函数,然后在函数体中又调用了本函数,这是函数的自调用.执行printf(root->data);语句的时候输出当前遍历的数据,preorder(root->Lchild);在执行到4的时候,root->Lchild=NULL,但是执行preorder(root->Rchild);语句,由此转向下一个结点,即5

㈧ 二叉树先序遍历递归算法和非递归算法本质区别

1. 先序遍历
在先序遍历中，对节点的访问工作是在它的左右儿子被访问之前进行的。换言之，先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义，所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下：
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT->Data); //对节点做些访问比如打印
PreOrderTraversal(BT->Left); //访问左儿子
PreOrderTraversal(BT->Right); //访问右儿子
}
}
由递归代码可以看出，该递归为尾递归（尾递归即递归形式在函数末尾或者说在函数即将返回前）。尾递归的递归调用需要用栈存储调用的信息，当数据规模较大时容易越出栈空间。虽然现在大部分的编译器能够自动去除尾递归，但是即使如此，我们不妨自己去除。非递归先序遍历算法基本思路：使用堆栈

a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；
b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右儿子，继续a步骤；
c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。
实现代码如下：
void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点访问（打印）后压入堆栈
{
printf("%d\n", T->Data);
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //节点弹出堆栈
T = T->Right; //转向右子树
}
}
}
由以上例子可以看出，递归与非递归的本质区别就是递归是不断循环调用同一过程，非递归是循环执行同一个动作，并且非递归有入栈与出栈的过程，因此更节省存储空间。个人浅见，欢迎指正。

㈨ 二叉树算法是什么

二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(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就是指只有1个子树（左子树或者右子树）。
度为2的结点个数=叶结点个数-1=69
该二叉树的总结点数=70+80+69=219