二叉樹單分支節點演算法

Ⅰ 二叉樹結點的演算法

一個結點的度是指該結點的子樹個數。
度為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)遍歷了所有結點後,退出"遞歸函數",最後的返回值就是總的"葉子"結點數.