二叉树单分支节点算法

Ⅰ 二叉树结点的算法

一个结点的度是指该结点的子树个数。
度为1就是指只有1个子树（左子树或者右子树）。
度为2的结点个数=叶结点个数-1=69
该二叉树的总结点数=70+80+69=219

Ⅱ 数据结构课程设计（C版语言）二叉排序树算法

下面的程序包含了树二叉树的所有操作
在二叉树的应用中有二叉排序树。
都是C语言，只不过用了C++的cin(输入)和cout（输出）,因为这两个不需要格式控制符。
//建一个工程：包含头文件：bittree.h Cpp文件：bittree.cpp main函数:main.cpp
编译运行就可以了。

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//头文件 bittree.h
#ifndef _DEF
#define _DEF
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define TURE 1
#define OK 1
#define FALSE 0
#define ERROR 0
#define INFEASIBLE -1//不可实行的
#define OVERFLOW -2
typedef int stas;
typedef char Telemtype;
//typedef int Telemtype2;//为了二叉排序树的创建
typedef char ElemType;
#define STACK_SIZE 100;
#define STACKINCREMENT 10;

//二叉树
typedef struct bitnode{
Telemtype data;
struct bitnode *lchild,*rchild;
}BitNode,*BitTree;
extern stas CreateBitTree(BitTree &T);
extern stas PreOrderTraverse(BitTree T);
extern stas InOrderTraverse(BitTree T);
extern stas PostOrderTraverse(BitTree T);

typedef BitNode selemtypechar;
typedef BitTree selemtypechar2;

// 栈
typedef struct SqStack{
selemtypechar2 *base;
selemtypechar2 *top;
int stacksize;
}sqstack;
extern stas initstackC(sqstack &S);
extern stas gettopC(sqstack S,selemtypechar2 &e);
extern stas pushC(sqstack &S,selemtypechar2 e);
extern stas popC(sqstack &S,selemtypechar2 &e);
extern stas destroyC(sqstack &S);//销毁
extern stas clearC(sqstack &S);//置空
extern stas stackempty(sqstack S);

//栈实现二叉树的输出
extern stas PreOrderTraverse2(BitTree T);
extern stas InOrderTraverse2(BitTree T);
extern stas PostOrderTraverse2(BitTree T);
//二叉树的应用
extern stas Depth(BitTree T);
extern stas Single(BitTree T);
extern stas Double(BitTree T);
extern stas CountLeaf(BitTree T);
extern void Change_Left_Right(BitTree T);
//二叉层次遍历用到队列
typedef BitTree Qelemtype;
typedef struct QNode{
Qelemtype data;
struct QNode *next;
}qnode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
extern stas InitQueue(LinkQueue &Q);
extern stas DestroyQueue(LinkQueue &Q);
extern stas EnterQueue(LinkQueue &Q,Qelemtype e);
extern stas DeQueue(LinkQueue &Q,Qelemtype &e);
//二叉层次遍历
extern stas LevelOrder(BitTree T);
//二叉排序树
extern void insert(BitTree &T,ElemType x);
extern void CreateBiTree2(BitTree &root);

#endif
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//cpp文件 bittree.cpp
#include "bittree.h"
#include <stdlib.h>

stas initstackC (sqstack &s)
{
s.base=(selemtypechar2 *)malloc(100*sizeof(selemtypechar));//用STACKINCREMENT会报错？？？
if (!s.base) exit(OVERFLOW);
s.top=s.base;
s.stacksize=100;
return OK;
}
stas gettopC(sqstack s,selemtypechar2 &e)
{
if(s.base==s.top) return ERROR;
e=*(s.top-1);
return OK;
}
stas pushC(sqstack &s,selemtypechar2 e)
{
if ((s.top-s.base)>=s.stacksize)
{
s.base=(selemtypechar2 *)realloc(s.base,((s.stacksize+10)*(sizeof(selemtypechar))));
if(!s.base) exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*(s.top++)=e;
//s.top++;
return OK;
}
stas popC(sqstack &s,selemtypechar2 &e)
{
if(s.top==s.base) return ERROR;
--s.top;
e=*(s.top);
return OK;
}
stas destroyC(sqstack &s)
{
free(s.base); s.base=NULL;s.top=NULL;
return OK;
}
stas clearC(sqstack &s)
{
s.top=s.base;
return OK;
}
stas stackempty(sqstack s)
{
if(s.top!=s.base) return ERROR;
else
return OK;
}

//二叉树
stas CreateBitTree(BitTree &T)//创建
{
Telemtype ch;
cin>>ch;
if(ch=='#') T=NULL;
else{
T=(BitTree)malloc(sizeof(BitNode));
if (!T) exit (OVERFLOW);
T->data=ch;
CreateBitTree(T->lchild);
CreateBitTree(T->rchild);
}
return OK;
}
stas PreOrderTraverse(BitTree T)//先序访问
{
if(!T) return ERROR;
else if (T)
{
cout<<T->data<<" ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
stas InOrderTraverse(BitTree T)//中序
{
if(!T) return ERROR;
else if (T)
{
InOrderTraverse(T->lchild);
cout<<T->data<<" ";
InOrderTraverse(T->rchild);
}
return OK;
}
stas PostOrderTraverse(BitTree T)//后序
{
if(!T) return ERROR;
else if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<" ";
}
return OK;
}

//栈实现二叉树的访问
stas PreOrderTraverse2(BitTree T)//先序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
//pushC(s,p);
while (p||!stackempty(s))
{
//popC(s,p);
if (p)
{
pushC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
//p1=p;
p=p->lchild;
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);

}
else {
popC(s,p);
popC(s,p);
p=p->rchild;
if (p==NULL)
{
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
p=p->rchild;
}
}
else{
pushC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
p=p->lchild;//左空不压栈
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);
}
}
}
destroyC(s);
return OK;
}
stas InOrderTraverse2(BitTree T)//中序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
}
else {
popC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
p=p->rchild;
}
}
destroyC(s);
return OK;
}

stas PostOrderTraverse2(BitTree T)//后序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
if (p==NULL)
{
popC(s,p);
//p=p->rchild;
if (p->rchild==NULL)
{
if(!p->data)return ERROR;
cout<<p->data<<" ";
//p=p->rchild;
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);//???右结点重复压栈？？？
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
else
{
p=p->rchild;
}
}
else
continue ;
}
else
{
//popC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
}
destroyC(s);
return OK;
}
//二叉树的应用

//二叉树的深度
stas Depth(BitTree T)
{
int depthval,depthLeft,depthRight;
if (!T) depthval=0;
else{
depthLeft=Depth(T->lchild);
depthRight=Depth(T->rchild);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
//二叉树的单分支结点数
stas Single(BitTree T)
{
if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Single(T->rchild)+1;//只有左单分支
if (T->lchild && !T->rchild) return Single(T->lchild)+1;//只有右单分支
if(T->lchild && T->rchild) return Single(T->lchild)+Single(T->rchild);//双分支结点
}
}
//二叉树的多分支结点数
stas Double(BitTree T)
{

if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Double(T->rchild);//只有左单分支
if (T->lchild && !T->rchild) return Double(T->lchild);//只有右单分支
if(T->lchild && T->rchild) return Double(T->lchild)+Double(T->rchild)+1;//双分支结点
}
}
//叶子结点
stas CountLeaf(BitTree T)
{
int num,num1,num2;
if(T==NULL) num=0;
else if(T->lchild==NULL&&T->rchild==NULL)
num=1;
else
{
num1=CountLeaf(T->lchild);
num2=CountLeaf(T->rchild);
num=num1+num2;
}
return num;
}
//交换左右子树
void Change_Left_Right(BitTree T)
{
BitTree Temp;
if (T)
{
Change_Left_Right(T->lchild);
Change_Left_Right(T->rchild);
Temp=T->lchild;
T->lchild=T->rchild;
T->rchild=Temp;
}
}
//二叉层次遍历用到队列
stas InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(100*sizeof(qnode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
stas DestroyQueue(LinkQueue &Q)
{
while (Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}

stas EnterQueue(LinkQueue &Q,Qelemtype e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(qnode));
if(!p) return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
stas DeQueue(LinkQueue &Q,Qelemtype &e)
{ QueuePtr p;
if(Q.front==Q.rear) return ERROR;
p=Q.front->next;e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;
}
//二叉层次遍历
stas LevelOrder(BitTree T)
{
LinkQueue Q;
BitTree B;
InitQueue(Q);
if (T!=NULL)
{
EnterQueue(Q,T);
while (!(Q.front==Q.rear))
{
DeQueue(Q,B);
cout<<B->data<<" ";
if(B->lchild!=NULL) EnterQueue(Q,B->lchild);
if(B->rchild!=NULL) EnterQueue(Q,B->rchild);
}
}
return OK;
}
//二叉排序树
void insert(BitTree &T,ElemType x)
{
if (T==NULL)
{
T=(BitTree)malloc(sizeof(BitNode));
T->data=x;
T->lchild=T->rchild=NULL;
}
else
{
if(x<T->data)insert(T->lchild,x);
if(x>=T->data)insert(T->rchild,x);
}
}
void CreateBiTree2(BitTree &root)
{
ElemType x;
root=NULL;
cout<<"二叉排序树的创建<以'#'结束!!!>"<<endl;
cout<<"<请输入字母，没写整型!!!>"<<endl;
cin>>x;
while (x!='#')
{
insert(root,x);
cin>>x;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//主函数 main.cpp
#include "bittree.h"
void main()
{
system("cls");
system("color f0");
BitTree T;
Create:
cout<<'\t'<<'\t'<<"先序创建二叉树<以'#'表示左右孩子为空!!!>："<<endl;
CreateBitTree(T);
BitTree T1(T);
select:
cout<<'\t'<<'\t'<<"----------------MAIN-MENU----------------"<<endl;
cout<<'\t'<<'\t'<<"&1、先序输出 2、中序输出 3、后序输出 &"<<endl;
cout<<'\t'<<'\t'<<"&4、栈实现输出 5、重新创建二叉树 0、退出&"<<endl;
cout<<'\t'<<'\t'<<"------------6、二叉树的应用-------------"<<endl;
char sel;
getchar();
cin>>sel;
switch (sel)//总
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '4':
stackcout:
cout<<endl<<'\t'<<" -------------------SUB-MENU1---------------------"<<endl;
cout<<'\t'<<" &1、先序输出 2、中序输出 3、后序输出 4、返回 &"<<endl;
cout<<'\t'<<" ------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//栈关于树的输出
{
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse2(T1);//p->lchild==null,时 T 的值被修改！！！！！！！！
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse2(T);
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T1);//栈实现未写完
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '4':goto select;
default:cout<<"选择错误!!!"<<endl;
goto stackcout;
}
case '5':
goto Create;
case '6':
{
SUB_MENU2:
cout<<'\t'<<'\t'<<"-------------------------SUB-MENU2---------------------"<<endl;
cout<<'\t'<<'\t'<<"&1、二叉树的深度 2、二叉树的单分支结点数 &"<<endl;
cout<<'\t'<<'\t'<<"&3、二叉树的多分支结点数 4、二叉树的叶子结点数 &"<<endl;
cout<<'\t'<<'\t'<<"&5、二叉层次遍历 6、二叉排序树 7、交换左右子树 &"<<endl;
cout<<'\t'<<'\t'<<"&------------------8、输出 0、返回--------------------&"<<endl;
cin>>sel;
switch (sel)//二叉树的应用
{
case '0':
goto select;
case '1':
{
int deepth=0;
deepth=Depth(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"树的深度为："<<deepth<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '2':
{
int cou_sig;
cou_sig=Single(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的单分支结点为数："<<cou_sig<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '3':
{
int cou_dou;
cou_dou=Double(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的双分支结点数为："<<cou_dou<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '4':
{
int cou_leaf;
cou_leaf=CountLeaf(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的叶子结点数为："<<cou_leaf<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '5':
{
cout<<"二叉层次遍历的结果为："<<endl;
cout<<endl<<"---------------------------------"<<endl;
LevelOrder(T);
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '6':
{
BitTree T3;
CreateBiTree2(T3);
SUB3:
cout<<'\t'<<"-------------------------SUB-MENU2-------------------"<<endl;
cout<<'\t'<<" &1、先序输出 2、中序输出 3、后序输出 0、返回 &"<<endl;
cout<<'\t'<<"-----------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//二叉树的层次遍历
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
default:
cout<<"选择错误!!!"<<endl;
goto SUB3;
}
}
goto SUB_MENU2;
case '7':
{
Change_Left_Right(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"交换完成，请选择8输出查看!!!"<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '8':
goto select;
default:
cout<<"选择错误!!!"<<endl;
goto SUB_MENU2;
}
}
break;
default :
cout<<endl<<"选择错误!!!"<<endl;
goto select;
}
}

Ⅲ 什么是单分支结点

单分支节点就是有左孩子或右孩子的节点 其余的是叶子节点 。

分支点是描述数据结构中的从根部出发（对有向图而言）有入度和出度的节点，（对无向图而言）不属于叶子节点的节点。出度不为0的结点称为分枝点。在完全m叉树中，如树叶数为t，分支点数为i，则（m-1）i=t-1算法描述：该算法递归去统计结点个数。值得一提的是该系列算法都是统计根结点以下的符和条件的结点的个数进行了加和。免去的设置全局变量和void的类型的函数。

Ⅳ 二叉树的结点

二叉树的结点：包含一个数据元素及若干指向子树的分支。

类型

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

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

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

Ⅳ 关于二叉树结点算法的问题

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

Ⅵ 什么是二叉树的分支结点度为0吗

分支结点的意思是说它指向其他的节点，所以是度不为0的结点。
为度为0的结点称之为“叶子结点”。

Ⅶ 为什么单分支结点不加入计算：一棵二叉树中，双分支结点数为15，单分支结点数为30，叶子节点数为n0=n2+1

先看一下证明方法：
结点总数n = n0 + n1 + n2。设B为分支总数，因为除根节点外，其余结点都有一个分支进入，所以n = B + 1。又因为分支是由度为1或2的结点射出，所以B = n1 + 2n2。综上：n = n0 + n1 + n2 = B + 1 = n1 + 2n2 + 1，得出：n0 = n2 + 1。

度为1的节点，就是出1个分支线，度为2的节点出2个分支线

aa
/
bbc

Ⅷ 二叉树叶子结点数算法

用"递归"的方法,以下是大致的步骤:
(1)进入"递归函数";
(2)如果当前结点没有分支,则是空结点,返回值为0;
(3)如果当前结点有左右分支,则是"叶子",返回值为1;
(4)查看当前结点的左分支,到步骤(1),然后,
查看当前结点的右分支,到步骤(1),合计两次返回值,
然后,返回该数值.
(5)遍历了所有结点后,退出"递归函数",最后的返回值就是总的"叶子"结点数.