树和二叉树的建立及应用.txt

数据结构的线性表及其应用

二叉树采用二叉链表作存储结构，试编程实现二叉树的如下操作：
1．用先序序列构造一棵二叉链表表示的二叉树T；
2．对这棵二叉树进行遍历：先序、层次遍历序列，分别输出结点的遍历序列；
求二叉树的深度/叶子结点数目。

#include<stdio.h> 
#include<stdlib.h>
#define  NULL  0 
typedef struct bitnode 
{
char data; 
struct bitnode *lchild,*rchild; 
}bitnode,*bitree; 
bitree create_tree() //先序创建 
{ 
char a;bitree root; 
scanf("%c",&a); 
if(a=='#')return NULL; 
else 
{ 
root=(bitnode *)malloc(sizeof(bitnode)); 
root->data=a; 
root->lchild=create_tree(); 
root->rchild=create_tree(); 
} 
return root; 
} 
/*输出二叉树(前序遍历) */ 
void preOrder(struct bitnode *root) 
{ 
/* 树为空时结束递归，否则执行如下操作 */ 
if(root != NULL){ 
printf("%c", root->data); /* 输出根结点的值 */ 
if(root->lchild != NULL || root->rchild!= NULL){ 
printf("("); 
preOrder(root->lchild); 
if(root->rchild != NULL){ 
printf(","); 
} 
preOrder(root->rchild); 
printf(")"); 
} 
} 
return; 
} 
/*按层遍历 */ 
void levelOrder(struct bitnode *root) 
{ 
struct bitnode *p; 
struct bitnode *q[100]; 
int front = 0, rear = 0; 
/* 将树根指针进队 */ 
if(root != NULL){ 
rear = (rear + 1) % 100; 
q[rear] = root; 
} 
while(front != rear){ /* 队列非空 */ 
front = (front + 1) % 100; /* 使队首指针指向队首元素 */ 
p = q[front]; 
printf("%c ", p->data); 
/* 若结点存在左孩子，则左孩子结点指针进队 */ 
if(p->lchild != NULL){ 
rear = (rear + 1) % 100; 
q[rear] = p->lchild; 
} 
/* 若结点存在右孩子，则右孩子结点指针进队 */ 
if(p->rchild != NULL){ 
rear = (rear + 1) % 100; 
q[rear] = p->rchild; 
} 
} 
return; 
} 
/*.求二叉树深度 */ 
 BTreeDepth(bitree root) 
{ 
if(root== NULL){ 
return 0; /* 对于空树，返回0结束递归 */ 
}
else{ 
int dep1 = BTreeDepth(root->lchild); /* 计算左子树的深度 */ 
int dep2 = BTreeDepth(root->rchild); /* 计算右子树的深度 */ 
return dep1>dep2?(dep1+1):(dep2+1);
} 
} 
int leafcount(bitree root)//计算叶子节点个数 
{ 
if(!root)return 0; 
else 
{ 
if(!(root->lchild)&&!(root->rchild))return 1; 
else return leafcount(root->lchild)+leafcount(root->rchild); 
} 
} 
int main() 
{ 
bitree root=NULL; 
printf("按先序序列构造一棵二叉树:");
root=create_tree();//输入序列为先序遍历序列，＃代表空 
printf("前序遍历序列:"); /* 前序遍历 */ 
preOrder(root); 
printf("\n"); 
printf("按层遍历序列:"); /* 按层遍历 */ 
levelOrder(root); 
printf("\n");
printf("叶子结点个数为:%d\n",leafcount(root)); 
printf("\n");  
printf("二叉树的深度为:"); 
printf("%d\n", BTreeDepth(root)); 
return 0; 
}