二叉树遍历等

荆轲

#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;       
}

荆轲

二叉树的很多算法都使用的递归

fishc.love