C语言实现二叉树的操作
作者:王鹤 QQ:583241212
树,是什么?是到处可见的树吗?呵呵,类似啦。。。数据结构中的树。。。类似啦!!!
树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用,如在编译源程序如下时,可用树表示源源程序如下的语法结构。又如在数据库系统中,树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
一、树的概述
树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。
(一)树的定义
树是由一个或多个结点组成的有限集合,其中:
⒈必有一个特定的称为根(ROOT)的结点;
⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn,而且,这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。
树的递归定义如下:(1)至少有一个结点(称为根)(2)其它是互不相交的子树
1.树的度——也即是宽度,简单地说,就是结点的分支数。以组成该树各结点中最大的度作为该树的度,如上图的树,其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次,如上图,其深度为4;
3.森林——指若干棵互不相交的树的集合,如上图,去掉根结点A,其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林;
4.有序树——指树中同层结点从左到右有次序排列,它们之间的次序不能互换,这样的树称为有序树,否则称为无序树。
5.树的表示
树的表示方法有许多,常用的方法是用括号:先将根结点放入一对圆括号中,然后把它的子树由左至右的顺序放入括号中,而对子树也采用同样的方法处理;同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。如上图可写成如下形式:
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5. 2 二叉树
1.二叉树的基本形态:
二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:
(1)空二叉树——(a);
(2)只有一个根结点的二叉树——(b);
(3)右子树为空的二叉树——(c);
(4)左子树为空的二叉树——(d);
(5)完全二叉树——(e)
注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。
2.两个重要的概念:
(1)完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树;
(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。
3.二叉树的性质
(1)
在二叉树中,第i层的结点总数不超过2^(i-1);
(2)
深度为h的二叉树最多有2^h-1个结点(h>=1),最少有h个结点;
(3)
对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,
则N0=N2+1;
(4)
具有n个结点的完全二叉树的深度为int(log2n)+1
(5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
若I为结点编号则如果I<>1,则其父结点的编号为I/2;
如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;
如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。
4.二叉树的存储结构:
(1)顺序存储方式
type node=record
data:datatype
l,r:integer;
end;
var tr:array[1..n]
of node;
(2)链表存储方式,如:
type btree=^node;
node=record
data:datatye;
lchild,rchild:btree;
end;
5.普通树转换成二叉树:凡是兄弟就用线连起来,然后去掉父亲到儿子的连线,只留下父母到其第一个子女的连线。
二叉树很象一株倒悬着的树,从树根到大分枝、小分枝、直到叶子把数据联系起来,这种数据结构就叫做树结构,简称树。树中每个分叉点称为结点,起始结点称为树根,任意两个结点间的连接关系称为树枝,结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的"双亲",结点的后趋结点称为该结点的"子女"或"孩子",同一结点的"子女"之间互称"兄弟"。
二叉树:二叉树是一种十分重要的树型结构。它的特点是,树中的每个结点最多只有两棵子树,即树中任何结点的度数不得大于2。二叉树的子树有左右之分,而且,子树的左右次序是重要的,即使在只有一棵子树的情况下,也应分清是左子树还是右子树。定义:二叉树是结点的有限集合,这个集合或是空的,或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。
(三)完全二叉树
对满二叉树,从第一层的结点(即根)开始,由下而上,由左及右,按顺序结点编号,便得到满二叉树的一个顺序表示。据此编号,完全二叉树定义如下:一棵具有n个结点,深度为K的二叉树,当且仅当所有结点对应于深度为K的满二叉树中编号由1至n的那些结点时,该二叉树便是完全二叉树。图4是一棵完全二叉树。
遍历概念
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。
遍历方案
1.遍历方案
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
(1)访问结点本身(N),
(2)遍历该结点的左子树(L),
(3)遍历该结点的右子树(R)。
以上三种操作有六种执行次序:
NLR、LNR、LRN、NRL、RNL、RLN。
注意:
前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。
2.三种遍历的命名
根据访问结点操作发生位置命名:
①
NLR:前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
② LNR:中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③
LRN:后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
注意:
由于被访问的结点必是某子树的根,所以N(Node)、L(Left
subtlee)和R(Right
subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1.中序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)访问根结点;
(3)遍历右子树。
2.先序遍历的递归算法定义:
若二叉树非空,则依次执行如下操作:
(1) 访问根结点;
(2) 遍历左子树;
(3) 遍历右子树。
3.后序遍历得递归算法定义:
若二叉树非空,则依次执行如下操作:
(1)遍历左子树;
(2)遍历右子树;
(3)访问根结点。
4.中序遍历的算法实现
用二叉链表做为存储结构,中序遍历算法可描述为:
void InOrder(BinTree T)
{
//算法里①~⑥是为了说明执行过程加入的标号
① if(T) { // 如果二叉树非空
②
InOrder(T->lchild);
③
printf("%c",T->data); // 访问结点
④
InOrder(T->rchild);
⑤ }
⑥ } // InOrder
实战演习:
如果,你比较聪明或基础很好,上面的可以不用看了。。。那些字都是费话。。。直接看程序吧
VC++6。0中的代码:
#include "stdafx.h"
#include "malloc.h"
#define NULL 0
typedef struct
BTree
{
char data;
struct BTree *lChild;
struct BTree *rChild;
}BinTree;
BinTree*
CreateTree(BinTree *p)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
return NULL;
p=(BinTree *)malloc(sizeof(BinTree));
p->data=ch;
p->lChild=CreateTree(p->lChild);
p->rChild=CreateTree(p->rChild);
return
p;
}
int Sumleaf(BinTree *T)
{
int sum=0,m,n;
if(T)
{
if((!T->lChild)&&(!T->rChild
))
sum++;
m=Sumleaf(T->lChild);
sum+=m;
n=Sumleaf(T->rChild );
sum+=n;
}
return sum;
}
void ZhongXu(BinTree *T)
{
if(T)
{
ZhongXu(T->lChild);
printf("%c",T->data);
ZhongXu(T->rChild );
}
}
void PreOrder(BinTree *T)
{
if(T){
printf("%c",T->data);
PreOrder(T->lChild);
PreOrder(T->rChild );
}
}
void HouXu(BinTree *T)
{
if(T)
{
HouXu(T->lChild);
HouXu(T->rChild );
printf("%c",T->data );
}
}
int Depth(BinTree *T)
{
int dep=0,dep1,depr;
if(!T) dep=0;
else{
dep1=Depth(T->lChild);
depr=Depth(T->rChild );
dep=1+(dep1>depr?dep1:depr);
}
return dep;
}
int main(int argc, char* argv[])
{
BinTree *Tree;
Tree=CreateTree(Tree);
printf("\n前续遍历:\n");
PreOrder(Tree);
printf("\n中续遍历:\n");
ZhongXu(Tree);
printf("\n后续遍历:\n");
HouXu(Tree);
printf("\n子叶数为:%d\n",Sumleaf(Tree));
printf("\n树的深度为:%d\n",Depth(Tree));
printf("\n程序设计:王鹤 QQ:583241212
\n华锐学院2006级数学与计算机系\n");
return 0;
}
下列代码在DEV-C++中调试通过。。。
#include
#include
#include
#define NULL 0
typedef struct
BTree
{
char data;
struct BTree *lChild;
struct BTree *rChild;
}BinTree;
BinTree*
CreateTree(BinTree *p)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
return NULL;
p=(BinTree *)malloc(sizeof(BinTree));
p->data=ch;
p->lChild=CreateTree(p->lChild);
p->rChild=CreateTree(p->rChild);
return
p;
}
int Sumleaf(BinTree *T)
{
int sum=0,m,n;
if(T)
{
if((!T->lChild)&&(!T->rChild
))
sum++;
m=Sumleaf(T->lChild);
sum+=m;
n=Sumleaf(T->rChild );
sum+=n;
}
return sum;
}
void ZhongXu(BinTree *T)
{
if(T)
{
ZhongXu(T->lChild);
printf("%c",T->data);
ZhongXu(T->rChild );
}
}
void PreOrder(BinTree *T)
{
if(T){
printf("%c",T->data);
PreOrder(T->lChild);
PreOrder(T->rChild );
}
}
void HouXu(BinTree *T)
{
if(T)
{
HouXu(T->lChild);
HouXu(T->rChild );
printf("%c",T->data );
}
}
int Depth(BinTree *T)
{
int dep=0,dep1,depr;
if(!T) dep=0;
else{
dep1=Depth(T->lChild);
depr=Depth(T->rChild );
dep=1+(dep1>depr?dep1:depr);
}
return dep;
}
int main(int argc, char* argv[])
{
BinTree *Tree;
Tree=CreateTree(Tree);
printf("\n前续遍历:\n");
PreOrder(Tree);
printf("\n中续遍历:\n");
ZhongXu(Tree);
printf("\n后续遍历:\n");
HouXu(Tree);
printf("\n子叶数为:%d\n",Sumleaf(Tree));
printf("\n树的深度为:%d\n",Depth(Tree));
printf("\n程序设计:王鹤 QQ:583241212
\n华锐学院2006级数学与计算机系\n");
system("pause");
return
0;
}
输入ABD##E##CF##G##就可以创建一棵树了。。。演练一下吧!!!
这一个是最终的效果图哦。。。
|