二叉树
计算机科学中一种数据结构 / 维基百科,自由的 encyclopedia
在电脑科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构[1]。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。
此条目或许包含不重要、多余或偏颇的范例。 (2015年4月8日) |
本条目有隐藏内容,或许有碍读者阅览。请协助改善条目,以符合维基百科标准。 (2015年3月2日) |
二叉树的第层至多拥有个节点;深度为的二叉树至多总共有个节点(定义根节点所在深度 ),而总计拥有节点数符合的,称为“满二叉树”;深度为有个节点的二叉树,当且仅当其中的每一节点,都可以和深度的满二叉树,序号1到的节点一对一对应时,称为完全二叉树。对任何一棵非空的二叉树,如果其叶片(终端节点)数为,分支度为2的节点数为,则。
与普通树不同,普通树的节点个数至少为1,而二叉树的节点个数可以为0;普通树节点的最大分支度没有限制,而二叉树节点的最大分支度为2;普通树的节点无左、右次序之分,而二叉树的节点有左、右次序之分。
二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆,并应用于高效率的搜索和排序。
二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后,每个顶点定义了唯一的父节点,和最多2个子节点。然而,没有足够的资讯来区分左节点和右节点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林。
二叉树是一个有根树,并且每个节点最多有2个子节点。非空的二叉树,若树叶总数为 n0,分支度为2的总数为 n2,则 n0 = n2 + 1。
一棵深度为k,且有个节点的二叉树,称为完美二叉树(Perfect Binary Tree)。这种树的特点是每一层上的节点数都是最大节点数。
对于一棵深度为 的完美二叉树:
- 共有 个结点
- 结点个数一定为奇数
- 第 层有 个结点
- 有 个叶子
在一颗二叉树中,若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么在右边缺少连续若干节点,则此二叉树为完全二叉树(Complete Binary Tree)。具有n个节点的完全二叉树的深度为。深度为k的完全二叉树,至少有个节点,至多有个节点。
在程式设计语言中能用多种方法来构造二叉树。
二叉树可以用数组或链表来存储,若是满二叉树就能紧凑排列而不浪费空间。如果某个节点的索引为i,(假设根节点的索引为0)则在它左子节点的索引会是,以及右子节点会是;而它的父节点(如果有)索引则为。这种方法更有利于紧凑存储和更好的访问的局部性,特别是在前序遍历中。然而,它需要连续的存储空间,这样在存储高度为h的n个节点所组成的一般树时,将浪费很多空间。在最糟糕的情况下,如果深度为h的二叉树其每个节点都只有右孩子,则该存储结构需要占用的空间,实际上却有h个节点,浪费了不少空间,是顺序存储结构的一大缺点。
/* 二叉树的顺序存储表示 */
#define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根节点 */
typedef struct
{
int level,order; /* 即节点的层(按[满二叉树]计算) */
}position;
/* [[二元樹]]的順序存儲的基本操作(23個)*/
#define ClearBiTree InitBiTree /* 在順序存儲結構中,兩函數完全一樣 */
#define DestroyBiTree InitBiTree /* 在順序存儲結構中,兩函數完全一樣 */
void InitBiTree(SqBiTree T) ---(SqBiTree & T)
{ /* 構造[[空二元樹]]T。因為T是陣列名稱,故不需要& */
int i;
for(i=0;i<MAX_TREE_SIZE;i++)
T[i]=Nil; /* 初值為空(Nil在主程中定義) */
}
void CreateBiTree(SqBiTree T)
{ /* 按層序次序輸入二叉樹中結點的值(字元型或整型), 構造順序存儲的二叉樹T */
int i=0;
#if CHAR /* 結點類型為字元 */
int l;
char s[MAX_TREE_SIZE];
InitBiTree(T); /* 構造[空二元樹]T */
printf("請按層序輸入結點的值(字元),空格表示空結點,節點數≦%d:\n",MAX_TREE_SIZE);
gets(s); /* 輸入字串 */
l=strlen(s); /* 求字串的長度 */
for(;i<l;i++) /* 將字串賦值給T */
T[i]=s[i];
#else /* 節點類型為整型 */
InitBiTree(T); /* 構造[空二元樹]T */
printf("請按層序輸入節點的值(整型),0表示空節點,輸999結束。節點數≦%d:\n",MAX_TREE_SIZE);
while(1)
{
scanf("%d",&T[i]);
if(T[i]==999)
{
T[i]=Nil;
break;
}
i++;
}
#endif
for(i=1;i<MAX_TREE_SIZE;i++)
if(T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此非根節點(不空)無雙親 */
{
printf("出現無雙親的非根節點"form"\n",T[i]);
exit(ERROR);
}
}
int BiTreeDepth(SqBiTree T)
{ /* 初始條件:[二元樹]T存在。操作結果:返回T的深度 */
int i,j=-1;
for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最後一個節點 */
if(T[i]!=Nil)
break;
i++; /* 為了便於計算 */
do
j++;
while(i>=pow(2,j)); /*pow是原型為double pow( double x, double y ),計算x的y次方,h = log<sub>2</sub>k + 1來計算[二元樹]的深度*/
return j;
}
Status Root(SqBiTree T,TElemType *e)
{ /* 初始條件:[二元樹]T存在。操作結果:當T不空,用e返回T的根,返回OK;否則返回ERROR,e無定義 */
if(BiTreeEmpty(T)) /* T空 */
return ERROR;
else
{
*e=T[0];
return OK;
}
}
TElemType Value(SqBiTree T,position e)
{ /* 初始條件:[二元樹]T存在,e是T中某個結點(的位置) */
/* 操作結果:返回處於位置e(層,本層序號)的結點的值 */
return T[(int)pow(2,e.level-1)+e.order-2];
}
Status Assign(SqBiTree T,position e,TElemType value)
{ /* 初始條件:二叉樹T存在,e是T中某個結點(的位置) */
/* 操作結果:給處於位置e(層,本層序號)的結點賦新值value */
int i=(int)pow(2,e.level-1)+e.order-2; /* 將層、本層序號轉為矩陣的序號 */
if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 給葉子賦非空值但雙親為空 */
return ERROR;
else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /* 給雙親賦空值但有葉子(不空) */
return ERROR;
T[i]=value;
return OK;
}
TElemType Parent(SqBiTree T,TElemType e)
{ /* 初始條件:二叉樹T存在,e是T中某個結點 */
/* 操作結果:若e是T的非根結點,則返回它的雙親,否則返回"空" */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* 找到e */
return T[(i+1)/2-1];
return Nil; /* 沒找到e */
}
TElemType LeftChild(SqBiTree T,TElemType e)
{ /* 初始條件:二叉樹T存在,e是T中某個結點。操作結果:返回e的左孩子。若e無左孩子,則返回"空" */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* 找到e */
return T[i*2+1];
return Nil; /* 沒找到e */
}
TElemType RightChild(SqBiTree T,TElemType e)
{ /* 初始條件:二叉樹T存在,e是T中某個結點。操作結果:返回e的右孩子。若e無右孩子,則返回"空" */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* 找到e */
return T[i*2+2];
return Nil; /* 沒找到e */
}
TElemType LeftSibling(SqBiTree T,TElemType e)
{ /* 初始條件:二叉樹T存在,e是T中某個結點 */
/* 操作結果:返回e的左兄弟。若e是T的左孩子或無左兄弟,則返回"空" */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2==0) /* 找到e且其序號為偶數(是右孩子) */
return T[i-1];
return Nil; /* 沒找到e */
}
TElemType RightSibling(SqBiTree T,TElemType e)
{ /* 初始條件:二叉樹T存在,e是T中某個結點 */
/* 操作結果:返回e的右兄弟。若e是T的右孩子或無右兄弟,則返回"空" */
int i;
if(T[0]==Nil) /* 空樹 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2) /* 找到e且其序號為奇數(是左孩子) */
return T[i+1];
return Nil; /* 沒找到e */
}
void Move(SqBiTree q,int j,SqBiTree T,int i) /* InsertChild()用到。加 */
{ /* 把從q的j結點開始的子樹移為從T的i結點開始的子樹 */
if(q[2*j+1]!=Nil) /* q的左子樹不空 */
Move(q,(2*j+1),T,(2*i+1)); /* 把q的j結點的左子樹移為T的i結點的左子樹 */
if(q[2*j+2]!=Nil) /* q的右子樹不空 */
Move(q,(2*j+2),T,(2*i+2)); /* 把q的j結點的右子樹移為T的i結點的右子樹 */
T[i]=q[j]; /* 把q的j結點移為T的i結點 */
q[j]=Nil; /* 把q的j結點置空 */
}
void InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree c)
{ /* 初始條件:二叉樹T存在,p是T中某個結點的值,LR為0或1,非空二叉樹c與T不相交且右子樹為空 */
/* 操作結果: 根據LR為0或1,插入c為T中p結點的左或右子樹。p結點的原有左或右子樹則成為c的右子樹 */
int j,k,i=0;
for(j=0;j<(int)pow(2,BiTreeDepth(T))-1;j++) /* 查找p的序號 */
if(T[j]==p) /* j為p的序號 */
break;
k=2*j+1+LR; /* k為p的左或右孩子的序號 */
if(T[k]!=Nil) /* p原來的左或右孩子不空 */
Move(T,k,T,2*k+2); /* 把從T的k結點開始的子樹移為從k結點的右子樹開始的子樹 */
Move(c,i,T,k); /* 把從c的i結點開始的子樹移為從T的k結點開始的子樹 */
}
typedef int QElemType; /* 設佇列元素類型為整型(序號) */
#include "c3-2.h" /* 鏈佇列 */
#include "bo3-2.c" /* 鏈佇列的基本操作 */
Status DeleteChild(SqBiTree T,position p,int LR)
{ /* 初始條件:二叉樹T存在,p指向T中某個結點,LR為1或0 */
/* 操作結果:根據LR為1或0,刪除T中p所指結點的左或右子樹 */
int i;
Status k=OK; /* 佇列不空的標誌 */
LinkQueue q;
InitQueue(&q); /* 初始化佇列,用於存放待刪除的結點 */
i=(int)pow(2,p.level-1)+p.order-2; /* 將層、本層序號轉為矩陣的序號 */
if(T[i]==Nil) /* 此結點空 */
return ERROR;
i=i*2+1+LR; /* 待刪除子樹的根結點在矩陣中的序號 */
while(k)
{
if(T[2*i+1]!=Nil) /* 左結點不空 */
EnQueue(&q,2*i+1); /* 入隊左結點的序號 */
if(T[2*i+2]!=Nil) /* 右結點不空 */
EnQueue(&q,2*i+2); /* 入隊右結點的序號 */
T[i]=Nil; /* 刪除此結點 */
k=DeQueue(&q,&i); /* 佇列不空 */
}
return OK;
}
void(*VisitFunc)(TElemType); /* 函數變數 */
void PreTraverse(SqBiTree T,int e)
{ /* PreOrderTraverse()調用 */
VisitFunc(T[e]);
if(T[2*e+1]!=Nil) /* 左子樹不空 */
PreTraverse(T,2*e+1);
if(T[2*e+2]!=Nil) /* 右子樹不空 */
PreTraverse(T,2*e+2);
}
void PreOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{ /* 初始條件:二叉樹存在,Visit是對結點操作的應用函數 */
/* 操作結果:先序遍歷T,對每個結點調用函數Visit一次且僅一次 */
VisitFunc=Visit;
if(!BiTreeEmpty(T)) /* 樹不空 */
PreTraverse(T,0);
printf("\n");
}
void InTraverse(SqBiTree T,int e)
{ /* InOrderTraverse()調用 */
if(T[2*e+1]!=Nil) /* 左子樹不空 */
InTraverse(T,2*e+1);
VisitFunc(T[e]);
if(T[2*e+2]!=Nil) /* 右子樹不空 */
InTraverse(T,2*e+2);
}
void InOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{ /* 初始條件:二叉樹存在,Visit是對結點操作的應用函數 */
/* 操作結果:中序遍歷T,對每個結點調用函數Visit一次且僅一次 */
VisitFunc=Visit;
if(!BiTreeEmpty(T)) /* 樹不空 */
InTraverse(T,0);
printf("\n");
}
void PostTraverse(SqBiTree T,int e)
{ /* PostOrderTraverse()調用 */
if(T[2*e+1]!=Nil) /* 左子樹不空 */
PostTraverse(T,2*e+1);
if(T[2*e+2]!=Nil) /* 右子樹不空 */
PostTraverse(T,2*e+2);
VisitFunc(T[e]);
}
void PostOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{ /* 初始條件:二叉樹T存在,Visit是對結點操作的應用函數 */
/* 操作結果:後序遍歷T,對每個結點調用函數Visit一次且僅一次 */
VisitFunc=Visit;
if(!BiTreeEmpty(T)) /* 樹不空 */
PostTraverse(T,0);
printf("\n");
}
void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{ /* 層序遍歷二叉樹 */
int i=MAX_TREE_SIZE-1,j;
while(T[i]==Nil)
i--; /* 找到最後一個非空結點的序號 */
for(j=0;j<=i;j++) /* 從根結點起,按層序遍歷二叉樹 */
if(T[j]!=Nil)
Visit(T[j]); /* 只遍歷非空的結點 */
printf("\n");
}
void Print(SqBiTree T)
{ /* 逐層、按本層序號輸出二叉樹 */
int j,k;
position p;
TElemType e;
for(j=1;j<=BiTreeDepth(T);j++)
{
printf("第%d層: ",j);
for(k=1;k<=pow(2,j-1);k++)
{
p.level=j;
p.order=k;
e=Value(T,p);
if(e!=Nil)
printf("%d:"form" ",k,e);
}
printf("\n");
}
}
在使用记录或存储器地址指针的程式设计语言中,二叉树通常用树结点结构来存储。有时也包含指向唯一的父节点的指针。如果一个结点的子结点个数小于2,一些子结点指针可能为空值,或者为特殊的哨兵结点。 使用链表能避免顺序存储浪费空间的问题,算法和结构相对简单,但使用二叉链表,由于缺乏父链的指引,在找回父节点时需要重新扫描树得知父节点的节点地址。
/* 二叉樹的二叉鏈表存儲表示 */
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild; /* 左右孩子指針 */
}BiTNode,*BiTree;