BiTree *Point(BiTree *T,TElemType s)
{ // 返回二叉树T中指向元素值为S的节点的指针
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)
{// 根据LR为0或1，插入c为T中p所指节点的左或右孩子，p所指节点的原有左或右子树，则成为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)
{//根据LR为0或1，删除T中p所指向的左或右子树
if(p)
{
if(LR == 0)
ClearBiTree(&(p->lchild));
else
ClearBiTree(&(p->rchild));
return OK;
}
return ERROR;
}
这一篇主要是二叉树中各种遍历的非递归和递归算法的实现：
void PreOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{// 先序递归遍历T，对每个节点调用函数visit一次且仅一次
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild,Visit);
PreOrderTraverse(T->rchild,Visit);
}
}
void InOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//中序递归遍历T，对每个节点调用函数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的非递归算法（利用栈），对每个数据元素调用函数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的非递归算法（利用栈），对每个数据元素调用函数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,对每个节点调用函数Visit一次
if(T)
{
PostOrderTraverse(T->lchild,Visit);
PostOrderTraverse(T->rchild,Visit);
Visit(T->data);
}
}
void LevelOrderTraverse(BiTree *T,Status (*Visit)(TElemType))
{//层序递归遍历T，利用队列，对每个节点调用函数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);
}
}
}
}
这一篇主要是二叉树一些常用的算法的实现：包括，深度遍历求深度，广度遍历求深度，交换左右子树，求叶子节点数。
size_t BiTreeDepth_queue(BiTree *T)
{//ai返回T的深度（光度o优先算法）
LinkQueue *q;//保存当前节点的o左右孩子的队列
BiTree *p = T;
size_t tree_depth; //二叉树的h深度
size_t cur_queue_length;//当前队列的元素个数
size_t cur_level_length;//二叉树每层的u元素的个数
q = (LinkQueue *)malloc(sizeof(struct QNode));
tree_depth = cur_queue_length = cur_level_length =0;
if(!T)
return 0;
InitQueue(&q);
tree_depth++; //访问根节点
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当前层的元素个数全部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访问节点a存在，n栈不空
if(p!=NULL)
{
Push(&s,p); //把当前节点压入a栈顶
cur_depth++; //i当前二叉树的深度
if(cur_depth>max_depth)
max_depth = cur_depth;
q1 = p; //变量q1用来保存当前不为ngg空的e节点
p= p->lchild;
}
else
{
//当前e节点不存在,回溯
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)
{//所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
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)
{//求叶子节点数
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)
{//交换左右子树的非递归的实现
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("构造空二叉树后，树空否？%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("数空，无根\n");
#ifdef CHAR
printf("请先序输入二叉树（ab 三个空格表示a为根节点，b为左子树的二叉树）\n");
#endif
#ifdef INT
printf("请先序输入二叉树\n");
#endif
CreateBiTree(&T);
printf("建立二叉树后，广度优先求树的深度=%d\n",BiTreeDepth_queue(T));
printf(" 建立二叉树后，树空否?=%d(1:YES 0:NO)树的深度为=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
printf("建立二叉树后，深度优先广度优先求树的深度=%d\n",BiTreeDepth_stack(T));
printf("二叉树的宽度=%d\n",Width(T));
printf("二叉树的叶子节点数=%d\n",BiTreeLeafCount(T));
printf("二叉树的所有的节点数=%d\n",BiTreeCount(T));
printf("交换左右节点数\n");
Swap(T);
InOrderTraverse(T,visitT);
printf("\n交换左右节点非递归\n");
Swap_N(T);
InOrderTraverse(T,visitT);
printf("\n请输入要查询的节点：");
scanf("%*c%c",&x);
printf("返回的b的层号为=%d\n",NodeLevel(T,x));
e1= Root(T);
if(e1!=Nil)
printf("二叉树的根为：%c\n",e1);
else
printf("数空，无根\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("请输入一个节点的值：\n");
scanf("%*c%c",&e1);
p= Point(T,e1);
printf("节点的值为：%c\n",Value(p));
printf("欲改变此节点的值，请输入新值:");
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("构造一个右子树为空的二叉树c:\n");
printf("请先序输入二叉树（如： 1 2 0 0 0表示1为根节点，2为左子树的二叉树\n）");
CreateBiTree(&c);
printf("先序递归遍历二叉树c:\n");
PreOrderTraverse(c,visitT);
printf("\n树c插入树T中，请输入树T中树c的双亲节点c为左（0）或右（1）子树：");
scanf("%*c%c%d",&e1,&i);
p= Point(T,e1);
InsertChild(p,i,c);
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T,visitT);
printf("\n删除子树，请输入待删除的子树的双亲节点，左（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编译器的运行的结果，在输入是有一个虚节点的问题，虚节点用“＃”表示，在输入二叉树的各个节点时，当遇到空节点时，输入"#".按先序的方式输入：
构造空二叉树后，树空否？1(1:YES 0:NO)树的深度=0
数空，无根
请先序输入二叉树（ab 三个空格表示a为根节点，b为左子树的二叉树）
abdg###e##c#f##
建立二叉树后，广度优先求树的深度=4
建立二叉树后，树空否?=0(1:YES 0:NO)树的深度为=4
建立二叉树后，深度优先广度优先求树的深度=4
二叉树的宽度=3
二叉树的叶子节点数=3
二叉树的所有的节点数=7
交换左右节点数
fcaebdg
交换左右节点非递归
gdbeacf
请输入要查询的节点：b
返回的b的层号为=2
二叉树的根为：a
中序递归遍历二叉树
gdbeacf
中序非递归遍历二叉树
gdbeacf
中序非递归遍历二叉树（另一种方法）
gdbeacf
先序非递归遍历二叉树
abdgecf
先序递归遍历二叉树
abdgecf
后序递归遍历二叉树
gdebfca
后序遍历的非递归二叉树
gdebfca
层序遍历二叉树
abcdefg
请输入一个节点的值：
d
节点的值为：d
欲改变此节点的值，请输入新值:m
层序遍历二次树:abcmefg
m的双亲是b
m的左孩子是g
m没有右孩子
m,没有左兄弟m的右兄弟为e
构造一个右子树为空的二叉树c:
请先序输入二叉树（如： 1 2 0 0 0表示1为根节点，2为左子树的二叉树
）hijl###k###
先序递归遍历二叉树c:
hijlk
树c插入树T中，请输入树T中树c的双亲节点c为左（0）或右（1）子树：b 1
先序递归遍历二叉树:
abmghijlkecf
删除子树，请输入待删除的子树的双亲节点，左（0）或右（1）子树：h 0
先序递归遍历二叉树:
abmghecf
构造空二叉树后，树空否？1(1:YES 0:NO)树的深度=0
数空，无根
请先序输入二叉树（ab 三个空格表示a为根节点，b为左子树的二叉树）
abdg###e##c#f##
建立二叉树后，广度优先求树的深度=4
建立二叉树后，树空否?=0(1:YES 0:NO)树的深度为=4
建立二叉树后，深度优先广度优先求树的深度=4
二叉树的宽度=3
二叉树的根为：a
请输入要查询的节点：b
返回的b的层号为=2
|
|
