数据结构—二叉树的创建遍历输出

客官°小女子只卖身不卖艺 2022-08-09 15:48 51阅读 0赞

二叉链表节点结构的定义如下

typedef struct Node
    {
        DateType data;//该节点的数据域
        struct Node *Lchild;//左孩子
        struct Node *Rchild;//右孩子
    }BiTNode,*BiTree;

二叉树的创建我们采用的是拓展先序序列创建二叉链表  
基本思路就是  
1.从键盘接收一个字符判断他是不是\#号 如果是\#号正面这个位置为空 如果不是\#号 则创建节点 写进数据 第一个创建的节点因为采用先序所以就是根。  
2 然后采用递归的方法按照先序的顺序继续创建左右孩子 指导键盘输入空格则创建结束  
代码如下

BiTree Creat()
    {
        char ch;
        BiTNode *S;
        ch = getchar();
        if(ch=='#')//判断是不是#号
        {
            return NULL;
        }
        S = (BiTNode *)malloc(sizeof(BiTNode));//创建新节点
        S->data = ch;//给新节点的数据域赋值
        S->Lchild = Creat();//递归创建左孩子
        S->Rchild = Creat();//递归创建右孩子
        return S;//返回根
    }

遍历我们分了三种顺序  
先序 中序 后序（这里均采用递归法遍历）  
先序遍历的思路是  
1 遍历的第一个肯定的根 所以打印出来数据  
2.遍历左孩子 也是采用递归方法  
3。左孩子遍历完之后才开始遍历右孩子

void PrintXX(BiTree S)
    {
        if(S)//如果树不为空才开始进入遍历
        {
            printf("%c ",S->data );//打印根
            PrintXX(S->Lchild);//递归遍历左孩子
            PrintXX(S->Rchild);//递归遍历右孩子
        }
    }
    void PrintZX(BiTree S)
    {
        if(S)
        {
            PrintZX(S->Lchild);//从左孩子开始遍历打印
            printf("%c ",S->data );
            PrintZX(S->Rchild);//右孩子遍历打印
        }
    }
    
    void PrintHX(BiTree S)
    {
        if (S)
        {
            PrintHX(S->Lchild);//左孩子遍历打印
            PrintHX(S->Rchild);//右孩子遍历打印最后才是根
            printf("%c ",S->data );
        }
    }

二叉树按照树形输出

void Print(BiTree S, int h)
    {
        if(S)
        {
          Print(S->Rchild,h+1);
          for(int i = 0;i<h;i++)
            {
             printf("   ");
            }
          printf("%c\n",S->data);
          Print(S->Lchild,h+1);
        }
    }