二叉树操作的11个简单算法1.docx
《二叉树操作的11个简单算法1.docx》由会员分享，可在线阅读，更多相关《二叉树操作的11个简单算法1.docx（7页珍藏版）》请在冰点文库上搜索。
二叉树操作的11个简单算法1
#include
#include
#defineSTACK_MAX_SIZE30
#defineQUEUE_MAX_SIZE30
#ifndefelemType
typedefcharelemType;
#endif
/************************************************************************/
/* 以下是关于二叉树操作的11个简单算法 */
/************************************************************************/
structBTreeNode{
elemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};
/*1.初始化二叉树*/
voidinitBTree（structBTreeNode**bt）
{
*bt=NULL;
return;
}
/*2.建立二叉树（根据a所指向的二叉树广义表字符串建立）*/
voidcreateBTree（structBTreeNode**bt,char*a）
{
structBTreeNode*p;
structBTreeNode*s[STACK_MAX_SIZE];/*定义s数组为存储根结点指针的栈使用*/
inttop=-1; /*定义top作为s栈的栈顶指针，初值为-1,表示空栈*/
intk; /*用k作为处理结点的左子树和右子树，k=1处理左子树，k=2处理右子树*/
inti=0; /*用i扫描数组a中存储的二叉树广义表字符串，初值为0*/
*bt=NULL; /*把树根指针置为空，即从空树开始建立二叉树*/
/*每循环一次处理一个字符，直到扫描到字符串结束符\0为止*/
while（a[i]!
='\0'）{
switch（a[i]）{
case'':
break; /*对空格不作任何处理*/
case'（':
if（top==STACK_MAX_SIZE-1）{
printf（"栈空间太小！
\n"）;
exit
（1）;
}
top++;
s[top]=p;
k=1;
break;
case'）':
if（top==-1）{
printf（"二叉树广义表字符串错误!
\n"）;
exit
（1）;
}
top--;
break;
case',':
k=2;
break;
default:
p=malloc（sizeof（structBTreeNode））;
p->data=a[i];
p->left=p->right=NULL;
if（*bt==NULL）{
*bt=p;
}else{
if（k==1）{
s[top]->left=p;
}else{
s[top]->right=p;
}
}
}
i++; /*为扫描下一个字符修改i值*/
}
return;
}
/*3.检查二叉树是否为空，为空则返回1,否则返回0*/
intemptyBTree（structBTreeNode*bt）
{
if（bt==NULL）{
return1;
}else{
return0;
}
}
/*4.求二叉树深度*/
intBTreeDepth（structBTreeNode*bt）
{
if（bt==NULL）{
return0; /*对于空树，返回0结束递归*/
}else{
intdep1=BTreeDepth（bt->left）; /*计算左子树的深度*/
intdep2=BTreeDepth（bt->right）; /*计算右子树的深度*/
if（dep1>dep2）{
returndep1+1;
}else{
returndep2+1;
}
}
}
/*5.从二叉树中查找值为x的结点，若存在则返回元素存储位置，否则返回空值*/
elemType*findBTree（structBTreeNode*bt,elemTypex）
{
if（bt==NULL）{
returnNULL;
}else{
if（bt->data==x）{
return&（bt->data）;
}else{ /*分别向左右子树递归查找*/
elemType*p;
if（p=findBTree（bt->left,x））{
returnp;
}
if（p=findBTree（bt->right,x））{
returnp;
}
returnNULL;
}
}
}
/*6.输出二叉树（前序遍历）*/
voidprintBTree（structBTreeNode*bt）
{
/*树为空时结束递归，否则执行如下操作*/
if（bt!
=NULL）{
printf（"%c",bt->data）; /*输出根结点的值*/
if（bt->left!
=NULL||bt->right!
=NULL）{
printf（"（"）;
printBTree（bt->left）;
if（bt->right!
=NULL）{
printf（","）;
}
printBTree（bt->right）;
printf（"）"）;
}
}
return;
}
/*7.清除二叉树，使之变为一棵空树*/
voidclearBTree（structBTreeNode**bt）
{
if（*bt!
=NULL）{
clearBTree（&（（*bt）->left））;
clearBTree（&（（*bt）->right））;
free（*bt）;
*bt=NULL;
}
return;
}
/*8.前序遍历*/
voidpreOrder（structBTreeNode*bt）
{
if（bt!
=NULL）{
printf（"%c",bt->data）; /*访问根结点*/
preOrder（bt->left）; /*前序遍历左子树*/
preOrder（bt->right）; /*前序遍历右子树*/
}
return;
}
/*9.前序遍历*/
voidinOrder（structBTreeNode*bt）
{
if（bt!
=NULL）{
inOrder（bt->left）; /*中序遍历左子树*/
printf（"%c",bt->data）; /*访问根结点*/
inOrder（bt->right）; /*中序遍历右子树*/
}
return;
}
/*10.后序遍历*/
voidpostOrder（structBTreeNode*bt）
{
if（bt!
=NULL）{
postOrder（bt->left）; /*后序遍历左子树*/
postOrder（bt->right）; /*后序遍历右子树*/
printf（"%c",bt->data）; /*访问根结点*/
}
return;
}
/*11.按层遍历*/
voidlevelOrder（structBTreeNode*bt）
{
structBTreeNode*p;
structBTreeNode*q[QUEUE_MAX_SIZE];
intfront=0,rear=0;
/*将树根指针进队*/
if（bt!
=NULL）{
rear=（rear+1）%QUEUE_MAX_SIZE;
q[rear]=bt;
}
while（front!
=rear）{ /*队列非空*/
front=（front+1）%QUEUE_MAX_SIZE;/*使队首指针指向队首元素*/
p=q[front];
printf（"%c",p->data）;
/*若结点存在左孩子，则左孩子结点指针进队*/
if（p->left!
=NULL）{
rear=（rear+1）%QUEUE_MAX_SIZE;
q[rear]=p->left;
}
/*若结点存在右孩子，则右孩子结点指针进队*/
if（p->right!
=NULL）{
rear=（rear+1）%QUEUE_MAX_SIZE;
q[rear]=p->right;
}
}
return;
}
/************************************************************************/
/*
intmain（intargc,char*argv[]）
{
structBTreeNode*bt; /*指向二叉树根结点的指针*/
char*b; /*用于存入二叉树广义表的字符串*/
elemTypex,*px;
initBTree（&bt）;
printf（"输入二叉树广义表的字符串：
\n"）;
/*scanf（"%s",b）;*/
b="a（b（c）,d（e（f,g）,h（,i）））";
createBTree（&bt,b）;
if（bt!
=NULL）
printf（"%c",bt->data）;
printf（"以广义表的形式输出：
\n"）;
printBTree（bt）; /*以广义表的形式输出二叉树*/
printf（"\n"）;
printf（"前序：
"）; /*前序遍历*/
preOrder（bt）;
printf（"\n"）;
printf（"中序：
"）; /*中序遍历*/
inOrder（bt）;
printf（"\n"）;
printf（"后序：
"）; /*后序遍历*/
postOrder（bt）;
printf（"\n"）;
printf（"按层：
"）; /*按层遍历*/
levelOrder（bt）;
printf（"\n"）;
/*从二叉树中查找一个元素结点*/
printf（"输入一个待查找的字符：
\n"）;
scanf（"%c",&x）; /*格式串中的空格跳过空白字符*/
px=findBTree（bt,x）;
if（px）{
printf（"查找成功：
%c\n",*px）;
}else{
printf（"查找失败！
\n"）;
}
printf（"二叉树的深度为：
"）;
printf（"%d\n",BTreeDepth（bt））;
clearBTree（&bt）;
return0;
}
*/
升级会员 