二叉树的基本操作
- 格式：doc
- 大小：42.00 KB
- 文档页数：6
二叉树的基本操作
1、定义二叉树
typedef struct ChainTree
{
DATA data;
struct ChainTree *left;
struct ChainTree *right;
}ChainBinTree;
2、初始化二叉树的根节点
ChainBinTree *InitRoot()
{
ChainBinTree *node;
if(node=(ChainBinTree *)malloc(sizeof(ChainBinTree))) //分配内存
{
printf("\n输入根结点数据:");
scanf("%s",&node->data);
node->left=NULL;
node->right=NULL;
return BinTreeInit(node);
}
return NULL;
3、为二叉树添加数据（n只能取1或2）
int BinTreeAddNode(ChainBinTree *bt,ChainBinTree *node,int n)
//bt为父结点，node为子结点,n=1表示添加左子树，n=2表示添加右子树
{
if(bt==NULL)
{
printf("父结点不存在，请先设置父结点!\n");
return 0;
}
switch(n)
{
case 1:
if(bt->left)
{
printf("左子树结点不为空!\n");
return 0;
}else
bt->left=node;
break;
case 2:
if( bt->right)
{
printf("右子树结点不为空!\n");
return 0;
}else
bt->right=node;
break;
default:
printf("参数错误!\n");
return 0;
}
return 1;
}
4、返回左子结点
ChainBinTree *BinTreeLeft(ChainBinTree *bt)
{
if(bt)
return bt->left;
else
return NULL;
}
5、返回右节点
ChainBinTree *BinTreeRight(ChainBinTree *bt)
{
if(bt)
return bt->right;
else
return NULL;
}
6、检查二叉树是否为空
int BinTreeIsEmpty(ChainBinTree *bt)
{
if(bt)
return 0;
else
return 1;
}
7、求二叉树的深度（递归）
int BinTreeDepth(ChainBinTree *bt)
{
int dep1,dep2;
if(bt==NULL)
return 0;
else
{
dep1 = BinTreeDepth(bt->left);
dep2 = BinTreeDepth(bt->right);
if(dep1>dep2)
return dep1 + 1;
else
return dep2 + 1;
}
}
8、查找数据为data的节点
ChainBinTree *BinTreeFind(ChainBinTree *bt,DATA data) //在二叉树中查找值为data的结点
{
ChainBinTree *p;
if(bt==NULL)
return NULL;
else
{
if(bt->data==data)
return bt;
else{
if(p=BinTreeFind(bt->left,data))
return p;
else if(p=BinTreeFind(bt->right, data))
return p;
else
return NULL;
}
}
}
9、清空二叉树
void BinTreeClear(ChainBinTree *bt)
{
if(bt)
{
BinTreeClear(bt->left);
BinTreeClear(bt->right);
free(bt);
bt=NULL;
}
return;
}
10、先序遍历
void BinTree_DLR(ChainBinTree *bt,void (*oper)(ChainBinTree *p))
{
if(bt)
{
oper(bt);
BinTree_DLR(bt->left,oper);
BinTree_DLR(bt->right,oper);
}
return;
}
11、中序遍历
void BinTree_LDR(ChainBinTree *bt,void(*oper)(ChainBinTree *p))
{
if(bt)
{
BinTree_LDR(bt->left,oper);
oper(bt);
BinTree_LDR(bt->right,oper);
}
return;
}
12、后序遍历
void BinTree_LRD(ChainBinTree *bt,void (*oper)(ChainBinTree *p))
{
if(bt)
{
BinTree_LRD(bt->left,oper);
BinTree_LRD(bt->right,oper);
oper(bt);
}
return;
}
13、层次遍历
void BinTree_Level(ChainBinTree *bt,void (*oper)(ChainBinTree *p))
{
ChainBinTree *p;
ChainBinTree *q[QUEUE_MAXSIZE]; //定义一个顺序栈
int head=0,tail=0;//队首、队尾序号
if(bt)//若队首指针不为空
{
tail=(tail+1)%QUEUE_MAXSIZE;//计算循环队列队尾序号
q[tail] = bt;//将二叉树根指针进队
}
while(head!=tail) //队列不为空，进行循环
{
head=(head+1)%QUEUE_MAXSIZE; //计算循环队列的队首序号
p=q[head]; //获取队首元素
oper(p);//处理队首元素
if(p->left!=NULL) //若结点存在左子树，则左子树指针进队
{
tail=(tail+1)%QUEUE_MAXSIZE;//计算循环队列的队尾序号
q[tail]=p->left;//将左子树指针进队
}
if(p->right!=NULL)//若结点存在右孩子，则右孩子结点指针进队
{
tail=(tail+1)%QUEUE_MAXSIZE;//计算循环队列的队尾序号
q[tail]=p->right;//将右子树指针进队
}
}
return;
}
14、建立二叉树
void CreateBiTree(BiTree *T)
{ /* 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，*/
/* 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。有改动 */
TElemType ch;
scanf(form,&ch);
if(ch==Nil) /* 空 */
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode)); /* 生成根结点 */
if(!*T)
exit(OVERFLOW);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild); /* 构造左子树 */
CreateBiTree(&(*T)->rchild); /* 构造右子树 */
}
