BiTree *Point(BiTree *T,TElemType s)
{ // 返回二叉樹T中指向元素值為S的節(jié)點的指針
LinkQueue *q;
BiTree *a;
q = (LinkQueue *)malloc(sizeof(struct QNode));
a = (BiTree *)malloc(sizeof(struct BiTNode));
if(T)
{
InitQueue(&q);
EnQueue(q,T);
while(!QueueEmpty(q))
{
DeQueue(q,&a);
if(a->data==s)
return a;
if(a->lchild)
EnQueue(q,a->lchild);
if(a->rchild)
EnQueue(q,a->rchild);
}
}
free(q);
free(a);
return NULL;
}
TElemType LeftChild(BiTree *T,TElemType e)
{//返回e的左孩子，若e無左孩子，則返回空
BiTree *a;
if(T)
{
a = Point(T,e);
if(a && a->lchild)
return a->lchild->data;
}
return Nil;
}
TElemType RightChild(BiTree *T,TElemType e)
{//返回e的右孩子，若e無左孩子，則返回空
BiTree *a;
if(T)
{
a = Point(T,e);
if(a && a->rchild)
return a->rchild->data;
}
return Nil;
}
TElemType LeftSibling(BiTree *T,TElemType e)
{//返回e的左兄弟，若e是T的左孩子或無左孩子，則返回空
TElemType a;
BiTree *p;
if(T)
{
a = Parent(T,e);
p= Point(T,a);
if(p->lchild && p->rchild && p->rchild->data ==e)
return p->lchild->data;
}
return Nil;
}
TElemType RightSibling(BiTree *T,TElemType e)
{//返回e的右兄弟，若e是T的左孩子或無左孩子，則返回空
TElemType a;
BiTree *p;
if(T)
{
a= Parent(T,e);
p = Point(T,a);
if(p->lchild && p->rchild && p->lchild->data ==e)
return p->rchild->data;
}
return Nil;
}
Status InsertChild(BiTree *p,int LR,BiTree *c)
{// 根據(jù)LR為0或1，插入c為T中p所指節(jié)點的左或右孩子，p所指節(jié)點的原有左或右子樹，則成為c的右子樹
if(p)
{
if(LR == 0)
{
c->rchild = p->lchild;
p->lchild = c;
}
else
{
c->rchild = p->rchild;
p->rchild =c;
}
return OK;
}
return ERROR;
}
Status DeleteChild(BiTree *p,int LR)
{//根據(jù)LR為0或1，刪除T中p所指向的左或右子樹
if(p)
{
if(LR == 0)
ClearBiTree(&(p->lchild));
else
ClearBiTree(&(p->rchild));
return OK;
}
return ERROR;
}
這一篇主要是二叉樹中各種遍歷的非遞歸和遞歸算法的實現(xiàn)：
void PreOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{// 先序遞歸遍歷T，對每個節(jié)點調(diào)用函數(shù)visit一次且僅一次
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild,Visit);
PreOrderTraverse(T->rchild,Visit);
}
}
void InOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//中序遞歸遍歷T，對每個節(jié)點調(diào)用函數(shù)visit一次
if(T)
{
InOrderTraverse(T->lchild,Visit);
Visit(T->data);
InOrderTraverse(T->rchild,Visit);
}
}
typedef BiTree_1 SElemType;
#include "Stack.h"
#include "Stack.c"
Status InOrderTraverse1(BiTree *T,Status(*Visit)(TElemType))
{//中序遍歷二叉樹T的非遞歸算法（利用棧），對每個數(shù)據(jù)元素調(diào)用函數(shù)visit
SqStack S;
BiTree *p;
InitStack(&S);
while(T||!StackEmpty(S))
{
if(T)
{
Push(&S,T);
T=T->lchild;
}
else
{
Pop(&S,&T);
if(!Visit(T->data))
return ERROR;
T = T->rchild;
}
}
printf("\n");
return OK;
}
Status InOrderTraverse2(BiTree *T,Status(*Visit)(TElemType))
{//中序遍歷二叉樹T的非遞歸算法（利用棧），對每個數(shù)據(jù)元素調(diào)用函數(shù)visit，
SqStack S;
BiTree *p;
InitStack(&S);
Push(&S,T);
while(!StackEmpty(S))
{
while(GetTop(S,&p) && p)
{
Push(&S,p->lchild);
}
Pop(&S,&p);
if(!StackEmpty(S))
{
Pop(&S,&p);
if(!Visit(p->data))
return ERROR;
Push(&S,p->rchild);
}
}
printf("\n");
return OK;
}
void PostOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//后序遞歸遍歷T,對每個節(jié)點調(diào)用函數(shù)Visit一次
if(T)
{
PostOrderTraverse(T->lchild,Visit);
PostOrderTraverse(T->rchild,Visit);
Visit(T->data);
}
}
void LevelOrderTraverse(BiTree *T,Status (*Visit)(TElemType))
{//層序遞歸遍歷T，利用隊列，對每個節(jié)點調(diào)用函數(shù)Visit一次
LinkQueue *q;
QElemType a;
q = (LinkQueue *)malloc(sizeof(struct QNode));
if(T)
{
InitQueue(&q);
EnQueue(q,T);
while(!QueueEmpty(q))
{
DeQueue(q,&a);
Visit(a->data);
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
printf("\n");
}
free(q);
}
Status PreOrderN(BiTree *T,Status (*Visit)(TElemType))
{//先序遍歷二叉樹T非遞歸算法
SqStack s;
BiTree *p;
InitStack(&s);
Push(&s,T);//根指針入棧
while(!StackEmpty(s))
{
while(GetTop(s,&p) && p)
{
if(!Visit(p->data))
return ERROR;
Push(&s,p->lchild);//向左走到盡頭
}
Pop(&s,&p);//空指針出棧
if(!StackEmpty(s))
{
Pop(&s,&p);
Push(&s,p->rchild);
}
}
}
void PreOrder(BiTree *T,Status(*Visit)(TElemType))
{//先序遍歷的遞歸算法
if(T)
{
Visit(T->data);
PreOrder(T->lchild,Visit);
PreOrder(T->rchild,Visit);
}
}
Status PostOrderN(BiTree *T,Status (*Visit)(TElemType))
{//后序遍歷的非遞歸算法
SqStack s;
BiTree *p;
BiTree *r;
p = T;
InitStack(&s);
Push(&s,T);
while(!StackEmpty(s))
{
while(GetTop(s,&p) && p)
Push(&s,p->lchild);
Pop(&s,&p);
if(!StackEmpty(s))
{
GetTop(s,&p);
if(p->rchild && p->rchild!=r)
{
p=p->rchild;
Push(&s,p);
p=p->lchild;
}
else
{
Pop(&s,&p);
if(!Visit(p->data))
return ERROR;
r = p;
p=NULL;
Push(&s,p);
}
}
}
}
這一篇主要是二叉樹一些常用的算法的實現(xiàn)：包括，深度遍歷求深度，廣度遍歷求深度，交換左右子樹，求葉子節(jié)點數(shù)。
size_t BiTreeDepth_queue(BiTree *T)
{//ai返回T的深度（光度o優(yōu)先算法）
LinkQueue *q;//保存當前節(jié)點的o左右孩子的隊列
BiTree *p = T;
size_t tree_depth; //二叉樹的h深度
size_t cur_queue_length;//當前隊列的元素個數(shù)
size_t cur_level_length;//二叉樹每層的u元素的個數(shù)
q = (LinkQueue *)malloc(sizeof(struct QNode));
tree_depth = cur_queue_length = cur_level_length =0;
if(!T)
return 0;
InitQueue(&q);
tree_depth++; //訪問根節(jié)點
if(p->lchild)
{
EnQueue(q,p->lchild);//若存在左孩子，則左孩子入隊列
cur_queue_length++;
}
if(p->rchild)
{
EnQueue(q,p->lchild);//若存在ou右i孩子，右孩子入隊列
cur_queue_length++;
}
cur_level_length = cur_queue_length;
while(!QueueEmpty(q))
{
DeQueue(q,&p);//出隊列
cur_level_length--;
cur_queue_length--;
if(p->lchild)
{
EnQueue(q,p->lchild);//若存在左孩子，左孩子進隊列
cur_queue_length++;
}
if(p->rchild)
{
EnQueue(q,p->rchild);//若存在右孩子，左孩子進隊列
cur_queue_length++;
}
if(cur_level_length<=0)
{
tree_depth++;
cur_level_length = cur_queue_length;//i當前層的元素個數(shù)全部h出隊
}
}
DestroyQueue(q);
return tree_depth;
}
size_t BiTreeDepth_stack(BiTree *T)
{
BiTree *p = T;
SqStack s;
size_t cur_depth,max_depth;
BiTree *q1,*q2;
// p = (BiTree *)malloc(sizeof(struct BNode));
max_depth=cur_depth = 0;
if(!T)
return 0;
InitStack(&s);
while(p!=NULL || !StackEmpty(s))
{ //當前a訪問節(jié)點a存在，n棧不空
if(p!=NULL)
{
Push(&s,p); //把當前節(jié)點壓入a棧頂
cur_depth++; //i當前二叉樹的深度
if(cur_depth>max_depth)
max_depth = cur_depth;
q1 = p; //變量q1用來保存當前不為ngg空的e節(jié)點
p= p->lchild;
}
else
{
//當前e節(jié)點不存在,回溯
Pop(&s,&p);
p=p->rchild;
if(!p)
{
if(StackEmpty(s))
break;
GetTop(s,&q2);
if(q2->lchild!=q1)
cur_depth = StackLength(s);
else
cur_depth--;
}
}//棧的深度并臂一定等于二叉樹的深度
}//while
DestroyStack(s);
return max_depth;
}
size_t Width(BiTree *T)
{//所謂寬度是指在二叉樹的各層上，具有結(jié)點數(shù)最多的那一層上的結(jié)點總數(shù)。
LinkQueue *q;
QElemType a;
BiTree *p = T;
q = (LinkQueue *)malloc(sizeof(struct QNode));
size_t cur_level_length = 0,cur_queue_length = 0,max_length=0;
if(!T)
{
return 0;
}
InitQueue(&q);
if(p->lchild)
{
EnQueue(q,p->lchild);
cur_queue_length++;
}
if(p->rchild)
{
EnQueue(q,p->rchild);
cur_queue_length++;
}
cur_level_length = cur_queue_length;
max_length = cur_queue_length;
while(!QueueEmpty(q))
{
DeQueue(q,&p);
cur_level_length--;
cur_queue_length--;
if(p->lchild !=NULL)
{
EnQueue(q,p->lchild);
cur_queue_length++;
}
if(p->rchild!=NULL)
{
EnQueue(q,p->rchild);
cur_queue_length++;
}
if(cur_level_length <=0)
{
if(cur_queue_length > max_length)
{
max_length = cur_queue_length;
}
cur_level_length = cur_queue_length;
}
}//while
DestroyQueue(q);
return max_length;
}
size_t BiTreeLeafCount(BiTree *T)
{//求葉子節(jié)點數(shù)
if(T==NULL)
{
return 0;
}
else
{
if(T->lchild==NULL && T->rchild==NULL)
return 1;
else
return BiTreeLeafCount(T->lchild) + BiTreeLeafCount(T->rchild);
}
}
size_t BiTreeCount(BiTree *T)
{
if(T==NULL)
return 0;
else
return BiTreeCount(T->lchild)+BiTreeCount(T->rchild)+1;
}
size_t NodeLevel(BiTree *T, TElemType x)
{
if(T==NULL)
return 0;
else
{
if(T->data == x)
{
return 1;
}
else
{//求出x在左子樹中的層號，返回該層號加1
int c1=NodeLevel(T->lchild,x);
if(c1>=1)
return c1+1;
//求出x在右子樹中的層號，返回該層號加1
int c2 = NodeLevel(T->lchild,x);
if(c2>=1)
return c2+1;
else
return 0;
}
}
}
void Swap_N(BiTree *T)
{//交換左右子樹的非遞歸的實現(xiàn)
SqStack s;
BiTree *temp,*p;
InitStack(&s);
p=T;
while(p || !StackEmpty(s))
{
if(p)
{
Push(&s,p);
p=p->lchild;
}
else
{
Pop(&s,&p);
temp = p->lchild;
p->lchild = p->rchild;
p->rchild = temp;
p=p->lchild;
}
}
}
void Swap(BiTree *T)
{
if(T==NULL)
return ;
BiTree *temp;
temp=T->lchild;
T->lchild = T->rchild;
T->rchild=temp;
Swap(T->lchild);
Swap(T->rchild);
}
這一篇主要是前面各種算法的一個測試程序：
Status visitT(TElemType e)
{
#ifdef CHAR
printf("%c",e);
#endif
#ifdef INT
printf("%d",e);
#endif
return OK;
}
void main(void)
{
int i;
BiTree *T,*p,*c,*q;
TElemType e1,e2,x;
InitBiTree(&T);
printf("構(gòu)造空二叉樹后，樹空否？%d(1:YES 0:NO)樹的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1= Root(T);
if(e1!=Nil)
#ifdef INT
printf("二叉樹的根為:%d\n",e1);
#endif
#ifdef CHAR
printf("二叉樹的根為：%c\n",e1);
#endif
else
printf("數(shù)空，無根\n");
#ifdef CHAR
printf("請先序輸入二叉樹（ab 三個空格表示a為根節(jié)點，b為左子樹的二叉樹）\n");
#endif
#ifdef INT
printf("請先序輸入二叉樹\n");
#endif
CreateBiTree(&T);
printf("建立二叉樹后，廣度優(yōu)先求樹的深度=%d\n",BiTreeDepth_queue(T));
printf(" 建立二叉樹后，樹空否?=%d(1:YES 0:NO)樹的深度為=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
printf("建立二叉樹后，深度優(yōu)先廣度優(yōu)先求樹的深度=%d\n",BiTreeDepth_stack(T));
printf("二叉樹的寬度=%d\n",Width(T));
printf("二叉樹的葉子節(jié)點數(shù)=%d\n",BiTreeLeafCount(T));
printf("二叉樹的所有的節(jié)點數(shù)=%d\n",BiTreeCount(T));
printf("交換左右節(jié)點數(shù)\n");
Swap(T);
InOrderTraverse(T,visitT);
printf("\n交換左右節(jié)點非遞歸\n");
Swap_N(T);
InOrderTraverse(T,visitT);
printf("\n請輸入要查詢的節(jié)點：");
scanf("%*c%c",&x);
printf("返回的b的層號為=%d\n",NodeLevel(T,x));
e1= Root(T);
if(e1!=Nil)
printf("二叉樹的根為：%c\n",e1);
else
printf("數(shù)空，無根\n");
printf("中序遞歸遍歷二叉樹\n");
InOrderTraverse(T,visitT);
printf("\n中序非遞歸遍歷二叉樹\n");
InOrderTraverse1(T,visitT);
printf("\n中序非遞歸遍歷二叉樹（另一種方法）\n");
InOrderTraverse2(T,visitT);
printf("\n先序非遞歸遍歷二叉樹\n");
PreOrderN(T,visitT);
printf("\n先序遞歸遍歷二叉樹\n");
PreOrder(T,visitT);
printf("\n后序遞歸遍歷二叉樹\n");
PostOrderTraverse(T,visitT);
printf("\n后序遍歷的非遞歸二叉樹\n");
PostOrderN(T,visitT);
printf("\n層序遍歷二叉樹\n");
LevelOrderTraverse(T,visitT);
printf("請輸入一個節(jié)點的值：\n");
scanf("%*c%c",&e1);
p= Point(T,e1);
printf("節(jié)點的值為：%c\n",Value(p));
printf("欲改變此節(jié)點的值，請輸入新值:");
scanf("%*c%c%*c",&e2);
Assign(p,e2);
printf("層序遍歷二次樹:");
LevelOrderTraverse(T,visitT);
e1 = Parent(T,e2);
if(e1!=Nil)
printf("%c的雙親是%c\n",e2,e1);
else
printf("%c沒有雙親\n",e2);
e1 = LeftChild(T,e2);
if(e1!=Nil)
printf("%c的左孩子是%c\n",e2,e1);
else
printf("%c沒有左孩子\n",e2);
e1= RightChild(T,e2);
if(e1!=Nil)
printf("%c的右孩子是%c\n",e2,e1);
else
printf("%c沒有右孩子\n",e2);
e1 = LeftSibling(T,e2);
if(e1!=Nil)
printf("%c的左兄弟為：%c",e2,e1);
else
printf("%c,沒有左兄弟",e2);
e1= RightSibling(T,e2);
if(e1!=Nil)
printf("%c的右兄弟為%c\n",e2,e1);
else
printf("%c沒有右兄弟、\n",e2);
InitBiTree(&c);
printf("構(gòu)造一個右子樹為空的二叉樹c:\n");
printf("請先序輸入二叉樹（如： 1 2 0 0 0表示1為根節(jié)點，2為左子樹的二叉樹\n）");
CreateBiTree(&c);
printf("先序遞歸遍歷二叉樹c:\n");
PreOrderTraverse(c,visitT);
printf("\n樹c插入樹T中，請輸入樹T中樹c的雙親節(jié)點c為左（0）或右（1）子樹：");
scanf("%*c%c%d",&e1,&i);
p= Point(T,e1);
InsertChild(p,i,c);
printf("先序遞歸遍歷二叉樹:\n");
PreOrderTraverse(T,visitT);
printf("\n刪除子樹，請輸入待刪除的子樹的雙親節(jié)點，左（0）或右（1）子樹：");
scanf("%*c%c%d",&e1,&i);
p= Point(T,e1);
DeleteChild(p,i);
printf("先序遞歸遍歷二叉樹:\n");
PreOrderTraverse(T,visitT);
printf("\n");
DestroyBiTree(&T);
}
|
下面是在Linux下gcc編譯器的運行的結(jié)果，在輸入是有一個虛節(jié)點的問題，虛節(jié)點用“?！北硎?，在輸入二叉樹的各個節(jié)點時，當遇到空節(jié)點時，輸入"#".按先序的方式輸入：
構(gòu)造空二叉樹后，樹空否？1(1:YES 0:NO)樹的深度=0
數(shù)空，無根
請先序輸入二叉樹（ab 三個空格表示a為根節(jié)點，b為左子樹的二叉樹）
abdg###e##c#f##
建立二叉樹后，廣度優(yōu)先求樹的深度=4
建立二叉樹后，樹空否?=0(1:YES 0:NO)樹的深度為=4
建立二叉樹后，深度優(yōu)先廣度優(yōu)先求樹的深度=4
二叉樹的寬度=3
二叉樹的葉子節(jié)點數(shù)=3
二叉樹的所有的節(jié)點數(shù)=7
交換左右節(jié)點數(shù)
fcaebdg
交換左右節(jié)點非遞歸
gdbeacf
請輸入要查詢的節(jié)點：b
返回的b的層號為=2
二叉樹的根為：a
中序遞歸遍歷二叉樹
gdbeacf
中序非遞歸遍歷二叉樹
gdbeacf
中序非遞歸遍歷二叉樹（另一種方法）
gdbeacf
先序非遞歸遍歷二叉樹
abdgecf
先序遞歸遍歷二叉樹
abdgecf
后序遞歸遍歷二叉樹
gdebfca
后序遍歷的非遞歸二叉樹
gdebfca
層序遍歷二叉樹
abcdefg
請輸入一個節(jié)點的值：
d
節(jié)點的值為：d
欲改變此節(jié)點的值，請輸入新值:m
層序遍歷二次樹:abcmefg
m的雙親是b
m的左孩子是g
m沒有右孩子
m,沒有左兄弟m的右兄弟為e
構(gòu)造一個右子樹為空的二叉樹c:
請先序輸入二叉樹（如： 1 2 0 0 0表示1為根節(jié)點，2為左子樹的二叉樹
）hijl###k###
先序遞歸遍歷二叉樹c:
hijlk
樹c插入樹T中，請輸入樹T中樹c的雙親節(jié)點c為左（0）或右（1）子樹：b 1
先序遞歸遍歷二叉樹:
abmghijlkecf
刪除子樹，請輸入待刪除的子樹的雙親節(jié)點，左（0）或右（1）子樹：h 0
先序遞歸遍歷二叉樹:
abmghecf
構(gòu)造空二叉樹后，樹空否？1(1:YES 0:NO)樹的深度=0
數(shù)空，無根
請先序輸入二叉樹（ab 三個空格表示a為根節(jié)點，b為左子樹的二叉樹）
abdg###e##c#f##
建立二叉樹后，廣度優(yōu)先求樹的深度=4
建立二叉樹后，樹空否?=0(1:YES 0:NO)樹的深度為=4
建立二叉樹后，深度優(yōu)先廣度優(yōu)先求樹的深度=4
二叉樹的寬度=3
二叉樹的根為：a
請輸入要查詢的節(jié)點：b
返回的b的層號為=2
|
|
