数据结构—二叉树层次遍历

红太狼 2022-08-22 13:23 142阅读 0赞

/*
    （1）二叉树的层次遍历；
    （2）假设二叉树采用二叉链存储结构，设计一个算法输出从根节点到每个叶子节点的路径的逆
         （即求叶子节点及其所有祖先节点的序列）。
    */
    #include <iostream>
    #include <malloc.h>
    #define MaxSize 100
    typedef char ElemType;
    using namespace std;
    typedef struct node
    {
        ElemType data;
        struct node *lchild;
        struct node *rchild;
    } BTNode;
    
    void CreateBTNode(BTNode *&b,char *str)   //创建二叉树
    {
        BTNode *St[MaxSize],*p;
        int top=-1,k,j=0;
        char ch;
        b=NULL;
        ch=str[j];
        while(ch!='\0')
        {
            switch(ch)
            {
            case '(':
                top++;
                St[top]=p;
                k=1;
                break;
            case ')':
                top--;
                break;
            case ',':
                k=2;
                break;
            default:
                p=(BTNode *)malloc(sizeof(BTNode));
                p->data=ch;
                p->lchild=p->rchild=NULL;
                if(b==NULL)
                    b=p;
                else
                {
                    switch(k)
                    {
                    case 1:
                        St[top]->lchild=p;
                        break;
                    case 2:
                        St[top]->rchild=p;
                        break;
                    }
                }
            }
            j++;
            ch=str[j];
        }
    }
    
    /*
       层次遍历：
           先将根节点进队，在队不为空时循环：从队列中出列一个节点*p,访问它；
           若它有左孩子节点，将左孩子节点进队； 若它有右孩子节点，将右孩子节点进队。
           如此循环，直到队空为止。
    */
    void LevelOrder(BTNode *b)
    {
      BTNode *p;
      BTNode *qu[MaxSize];    //定义环形队列，存放节点指针
      int front,rear;
      front=rear=-1;
      rear++;
      qu[rear]=b;          //根节点指针进队列
      while(front!=rear)
      {
          front=(front+1)%MaxSize;   //访问每个子树的根节点
          p=qu[front];
          cout<<p->data;
          if(p->lchild!=NULL)        //有左孩子时将其进队
          {
              rear=(rear+1)%MaxSize;
              qu[rear]=p->lchild;
          }
          if(p->rchild!=NULL)        //有右孩子时将其进队
          {
              rear=(rear+1)%MaxSize;
              qu[rear]=p->rchild;
          }
      }
    }
    
    /*
       非环形顺序队列qu，将所有已访问过的节点指针进队，并在队列中保存双亲节点的位置。
       当找到一个叶子节点时，在队列中通过双亲节点的位置输出根节点到叶子节点的路径的逆。
    */
    void AllPath(BTNode *b)
    {
        struct snode
        {
            BTNode *node;   //存放当前节点的指针
            int parent;     //存放双亲节点在队列中的位置
        }qu[MaxSize];       //定义非环形队列
        BTNode *q;
        int front,rear,p;
        front=rear=-1;
        rear++;
        qu[rear].node=b;     //根节点指针进入队列
        qu[rear].parent=-1;  //根节点没有双亲节点
        while(front!=rear)
        {
            front++;
            q=qu[front].node;  //队头出队列，该节点仍在qu中
            if(q->lchild==NULL&&q->rchild==NULL)   //*q为叶子节点
            {
                p=front;                        //输出*q到根节点的路径序列
                while(qu[p].parent!=-1)
                {
                    cout<<qu[p].node->data<<"->";
                    p=qu[p].parent;
                }
                cout<<qu[p].node->data<<endl;
            }
            if(q->lchild!=NULL)                  //*q有左孩子时将左孩子进队列
            {
                rear++;
                qu[rear].node=q->lchild;
                qu[rear].parent=front;
            }
            if(q->rchild!=NULL)                  //*q有右孩子时将右孩子进队列
            {
                rear++;
                qu[rear].node=q->rchild;
                qu[rear].parent=front;
            }
        }
    }
    
    int main()
    {
        BTNode *b;
        CreateBTNode(b,"A(B(D(,G)),C(E,F))");
        cout<<"层次遍历：";
        LevelOrder(b);
        cout<<endl;
        cout<<"输出根节点到叶子节点的路径的逆："<<endl;
        AllPath(b);
        cout<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220722/f50c8f07989d437a9afc8b960681c4a5.png