二叉树遍历等
#include<stdio.h>#include<stdlib.h>
typedef char Elemtype;
int find_level=1; //查找结点所在层数
typedef struct Tree
{
Elemtype data; // 存放结点数据
struct Tree *lchild; // 遍历左子树指针
struct Tree *rchild; // 遍历右子树指针
}Tree,*BitTree;
static BitTree T_temp;
BitTree CreateLink()
{
Elemtype data;
Elemtype temp;
BitTree T;
scanf("%c",&data); // 输入数据
temp=getchar(); // 吸收空格
if(data == '*')
{ // 输入* 代表此结点下子树不存数据，也就是不继续递归创建
return NULL;
}
else
{
T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间
if(T==NULL)
{
printf("内存申请失败,请重启!\n");
}
T->data = data; // 把当前输入的数据存入当前节点指针的数据域中
printf("请输入%c的左子树,*号代表无左子树: ",data);
T->lchild = CreateLink(); // 开始递归创建左子树
printf("请输入%c的右子树,*号代表无右子树: ",data);
T->rchild = CreateLink(); // 开始到上一级结点的右边递归创建左右子树
return T; // 返回根结点
}
}
void findNodelevel (BitTree T,char key) //判断某结点在哪一层
{
if(T)
{
if(T->data==key)
{
printf("在第%d层\n",find_level);
}
else
{
find_level++;
findNodelevel(T->lchild,key);
findNodelevel(T->rchild,key);
--find_level;//若
}
}
}
// 先序遍历
void ShowXianXu(BitTree T,int num) // 先序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层结点
{
return;
}
printf("%c 在第%d层\n",T->data,num++);
ShowXianXu(T->lchild,num); // 递归遍历左子树
ShowXianXu(T->rchild,num); // 递归遍历右子树
}
// 中序遍历
void ShowZhongXu(BitTree T,BitTree S)// 中序遍历二叉树，第二个参数是为了调用findNodelevel时T不变
{
if(T==NULL) // 递归中遇到NULL，返回上一层结点
{
return;
}
ShowZhongXu(T->lchild,S); // 递归遍历左子树
printf("%c ",T->data);
findNodelevel (S,T->data); // 输出该结点所在层数
ShowZhongXu(T->rchild,S); // 递归遍历右子树
}
// 后序遍历
void ShowHouXu(BitTree T,BitTree S) // 后序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层结点
{
return;
}
ShowHouXu(T->lchild,S); // 递归遍历左子树
ShowHouXu(T->rchild,S); // 递归遍历右子树
printf("%c ",T->data);
findNodelevel (S,T->data); // 输出该结点所在层数
}
int level_count(BitTree T) //计算二叉树层数
{
int level_Left,level_Right,level;
if(T==NULL)
{
return 0; //递归出口
}
level_Left=level_count(T->lchild);
level_Right=level_count(T->rchild);
level=level_Left > level_Right ? (level_Left + 1) : (level_Right + 1);
return level;
}
int Node_count(BitTree T) //计算二叉树结点数
{
int count_Left,count_Right,node_count;
if(T==NULL)
{
return 0;
}
count_Left=Node_count(T->lchild);
count_Right=Node_count(T->rchild);
node_count=count_Left+count_Right+1;
return node_count;
}
void print_k_levle(BitTree T,int k) //打印第K层的所有结点
{
if(T==NULL)
{
return;
}
if(k==1)
{
printf("%-3c",T->data);
}
else
{
print_k_levle(T->lchild,k-1);
print_k_levle(T->rchild,k-1);
}
}
int K_level_nodenum(BitTree T,int k,int level) //计算二叉树第K层的结点数
{
int nodenum;
if(k>level) //level为最大层数
{
printf("输入错误，超出二叉树最大层数!\n");
}
if(T==NULL || k<1)
{
return 0; //空树
}
if(k==1)
{
return 1; //递归出口
}
nodenum=K_level_nodenum(T->lchild,k-1,level)+K_level_nodenum(T->rchild,k-1,level);
return nodenum;
}
int printf_leafnode(BitTree T) //打印所有叶结点,并统计叶结点个数
{
int num_leaf;
if(T==NULL)
{
return 0;
}
if(T->lchild==NULL && T->rchild==NULL)
{
printf("%-2c",T->data);
return 1;
}
num_leaf=printf_leafnode(T->lchild)+printf_leafnode(T->rchild);
return num_leaf;
}
int main()
{
int num=1,level,k_level,k;
BitTree S;
printf("请输入根节点的数据,按回车结束:");
S = CreateLink(); // 接受创建二叉树完成的根结点
printf("\n\n二叉树的叶结点有：");
printf(",共有%d个叶结点.\n",printf_leafnode(S));
level=level_count(S);
printf("\n\n二叉树共有%d层!\n\n",level);
printf("请输入需要查询结点数的层数k=");
scanf("%d",&k);
k_level=K_level_nodenum(S,k,level);
printf("\n");
printf("二叉树第%d层的结点数为%d个,分别是:",k,k_level);
print_k_levle(S,k); //输出第K层的所有结点
printf("\n\n");
printf("先序遍历结果: \n");
ShowXianXu(S,num); // 先序遍历二叉树
printf("\n中序遍历结果: \n");
ShowZhongXu(S,S); // 中序遍历二叉树
printf("\n后序遍历结果: \n");
ShowHouXu(S,S); // 后序遍历二叉树
return 0;
}
二叉树的很多算法都使用的递归
{:10_257:}
页:
[1]