7-4 jmu-ds-输出二叉树每层节点

![题目要求](https://images.gitee.com/uploads/images/2021/0502/162847_c9ccc354_8756800.png "屏幕截图.png")
```
#include<iostream>
#include<string>
#include<queue>
using namespace std;

#define Maxsize 5000
typedef struct BiTNode {                             //二叉树的二叉链表存储表示
    char data;
    struct BiTNode* lchild, * rchild;
}BTNode, * BTree;

/*typedef struct
{
    BiTNode* data[Maxsize];                        //层次遍历用到的结构体
    int front, rear;
}SqQueue;*/

BTree CreatTree(string str, int &i);//先序建树
void GetLevel(BTree T);//层次遍历并输出结点层次
//void PreTree(BTree T);

int main()
{
    string str;
    cin >> str;
    int i = 0;
    BTree T = CreatTree(str, i);
    //PreTree(T);
    GetLevel(T);
    return 0;
}

BTree CreatTree(string str, int &i)//先序创建树
{
    int len;
    len = str.size();
    BTree bt;
    if (i > len - 1)
    {
        return NULL;
    }
    if (str[i] == '#')
    {
        return NULL;
    }
    bt = new BTNode;
    bt->data = str[i];
    bt->lchild = CreatTree(str, ++i);
    bt->rchild = CreatTree(str, ++i);
    return bt;
}
void GetLevel(BTree T)//层次遍历并输出结点层次
{
    int level = 1;
    queue<BTree>q;
    BTree node, curNode, lastNode;
    node = lastNode = T;
    if (T)
        q.push(T);
    else
    {
        cout << "NULL" << endl;
        return;
    }
    cout << "1:";
    while (!q.empty())
    {
        node = q.front();
        if (node->rchild)
            curNode = node->rchild;
        else if (node->lchild)
            curNode = node->lchild;
        cout << node->data << ",";
        if (node->lchild)
            q.push(node->lchild);
        if (node->rchild)
            q.push(node->rchild);
        q.pop();
        if (node == lastNode && !q.empty())
        {
            cout << endl;
            cout << ++level << ":";
            lastNode = curNode;
        }
    }

}

void PreTree(BTree T)
{
    if (T == NULL)
    {
        return;
    }
    printf("%c ", T->data);
    PreTree(T->lchild);
    PreTree(T->rchild);
}

```

秣羽konjac/网络2011 博客代码

内容风险标识

评论 (0)

秣羽konjac/网络2011 博客代码 .gitee-modal { width: 500px !important; }

内容风险标识