二叉树顺序结构实现/链式结构实现

心已赠人 2022-08-06 01:21 210阅读 0赞

程杰《大话数据结构》这部分的源码乱起八糟的。自己总结下：

顺序结构：

#include "stdafx.h"
    #include "string.h"
    #include "stdio.h"
    #include "stdlib.h"
    #include <iostream>
    using namespace std;
    
    
    #define ok 1
    #define error 0
    #define true 1
    #define false 0
    
    
    #define MAXSIZE 100
    #define MAX_TREE_SIZE 100
    typedef int TElemType;
    //typedef TElemType SqBiTree[MAX_TREE_SIZE];//顺序结构 相当于是数组 结构
    #define MAX_NODE_SIZE 100         //二叉树的最大节点数
    typedef char SqBiTree[MAX_NODE_SIZE+1];        //0号单元节点个数
    
    
    //创建二叉树
    void creat_tree(SqBiTree &t)
    {
    int i=0;
    char ch;
    while((ch=getchar())!='$')
    {
    i++;
    t[i]=ch;
    }
    t[0]=i;
    }
    
    
    //获取给定结点（位置）的左孩子的结点位置
    int LeftChild_locate(SqBiTree &t,int node) 
    {
    if ((2 * node) > t[0])
    return -1;
    else 
    return 2 * node;
    }
    //获取给定结点（位置）的右孩子的结点位置
    int RightChild_locate(SqBiTree &t,int node) 
    {
    if ((2 * node+1) > t[0])
    return -1;
    else 
    return 2 * node+1;
    }
    
    
    //层序遍历
    void level_order(SqBiTree &t)
    {
    for(int i=1;i<=t[0];i++)
    if(t[i]!='$')
    cout<<t[i]<<" ";
    }
    //先序遍历
    void pre_order(SqBiTree &t,int i)
    {
    if(t[0]<=0)
    {
    cout<<"空树!"<<endl;
    }
    else
    {
    if(t[i]!='$')
    cout<<t[i]<<" ";
    if(LeftChild_locate(t,i)!=-1)    //如果左子结点存在，递归
    pre_order(t,LeftChild_locate(t,i));
    if(RightChild_locate(t,i)!=-1)    //如果右子结点存在，递归
    pre_order(t,RightChild_locate(t,i));
    }
    }
    //中序遍历
    void mid_order(SqBiTree &t,int i)
    {
    if(t[0]<=0)
    {
    cout<<"空树!"<<endl;
    }
    else
    {
    if(LeftChild_locate(t,i)!=-1)    //如果左子结点存在，递归
    mid_order(t,LeftChild_locate(t,i));
    if(t[i]!='$')
    cout<<t[i]<<" ";
    if(RightChild_locate(t,i)!=-1)    //如果右子结点存在，递归
    mid_order(t,RightChild_locate(t,i));
    }
    }//后序遍历
    void back_order(SqBiTree &t,int i)
    {
    if(t[0]<=0)
    {
    cout<<"空树!"<<endl;
    }
    else
    {
    if(LeftChild_locate(t,i)!=-1)    //如果左子结点存在，递归
    back_order(t,LeftChild_locate(t,i));
    if(RightChild_locate(t,i)!=-1)    //如果右子结点存在，递归
    back_order(t,RightChild_locate(t,i));
    if(t[i]!='$')
    cout<<t[i]<<" ";
    }
    }
    int main()
    {
    cout<<"创建二叉树:"<<endl;
    SqBiTree sbt;
    //创建顺序二叉树
    creat_tree(sbt);
    //层序遍历
    cout<<"层序遍历:"<<endl;
    level_order(sbt);
    cout<<endl;
    //先序遍历
    cout<<"前序遍历:"<<endl;
    pre_order(sbt,1);
    cout<<endl;
    //中序遍历
    cout<<"中序遍历:"<<endl;
    mid_order(sbt,1);
    cout<<endl;
    //后续遍历
    cout<<"后序遍历:"<<endl;
    back_order(sbt,1);
    cout<<endl;
    
    
    cout<<LeftChild_locate(sbt,3);
    system("pause");
    return 0;
    }

链式结构：

#include "stdafx.h"
    #include "stdio.h"
    #include "io.h"
    #include "string.h"
    #include"stdlib.h"//除了内存分配的 malloc free new delete这些还有 system pause的命令也归这个关啊
    
    
    typedef struct BiNode
    {
    char data;
    struct BiNode *lchild,*rchild;
    }BiNode,*LinkBiTree;
    
    
    //递归构建链式二叉树
    void CreatTree(LinkBiTree &T)
    {
    char ch;
    //printf("创建链式二叉树");
        ch=getchar();
    if(ch=='#')
    {T=NULL;
        return;}
    else
    {
    T=new BiNode;
    T->data=ch;
    CreatTree(T->lchild);
    CreatTree(T->rchild);//一直建立左子树，直到左子树建立完了，#表示建立完了，建立右子树，这是前序遍历的方式建立的
    }
       
    }
    
    
    void preorder(LinkBiTree &T)
    {
    if(T==NULL)
    return;
    else
    {printf("%c ",T->data);
       preorder(T->lchild);
    preorder(T->rchild);}
    }
    
    
    void midorder(LinkBiTree &T)
    {
    if(T==NULL)
    return;
    else
      { midorder(T->lchild);
          
    printf("%c ",T->data);
    midorder(T->rchild);}
    }
    
    
    void backorder(LinkBiTree &T)
    {
    if(T==NULL)
    return;
    else
      { backorder(T->lchild);
    
       backorder(T->rchild);
       
    printf("%c ",T->data);}
    }
    int main()
    {
    LinkBiTree T;
    CreatTree(T);
    //前序遍历
    preorder(T);
    printf("\n");
    //中序遍历
    midorder(T);
    printf("\n");
    //后续遍历
    backorder(T);
        printf("\n");
    
    
    system("pause");
    return 0;
    }

要注意的地方是：

链式结构是递归创建，且结束符是\#.

如果初始创建是1233456\#\#\#\#\#\#\#\#\#\#\#\#这种的话，其实是一个左斜树。最后中序遍历和后续遍历结果是一样的，都是前序遍历的倒序。

![SouthEast][]

因为我分不清应该有几个\#结尾，所以干脆打了很多结尾符。但是这样就能得到正确直观的遍历。

[SouthEast]: /images/20220806/f0025355500d472789b7bb55e63fbecc.png