두 갈래 나무의 차원이 동시에 층수를 훑어보다

1562 단어
두 갈래 나무의 차원은 bfs로 해결할 수 있지만 각 층의 노드를 출력하고 한 층을 위한 다음에 줄을 바꾸도록 요구하면.
일반적으로 생각할 수 있는 것은 대열의 구조체에 변수 dep를 추가하여 그의 깊이를 기록하는 것이다.
그러나 여기에는 끝 표시 NULL을 추가하여 NULL을 각 줄의 마지막 노드로 사용하면 기능을 실현할 수 있다.
#include
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
#define INF 0x3f3f3f3f
#define clr(x,y) memset(x,y,sizeof x)
const ll Mod = 998244353;
typedef  unsigned long long ull;
struct TreeLinkNode {
    int val;
    TreeLinkNode *left, *right, *next;
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

void solve(TreeLinkNode * root)
{
    if(root == NULL)return;
    queueq;
    q.push(root);q.push(NULL);
    int level = 1;
    while(!q.empty())
    {
        TreeLinkNode * t = q.front();q.pop();
        if(t == NULL)
        {
            if(q.empty())break;
            level ++;
            q.push(NULL);
            puts("");
            continue;
        }
        cout << (t -> val) << " ";
        if(t -> left)q.push(t -> left);
        if(t -> right)q.push(t -> right);
    }
}

int main()
{
    TreeLinkNode *root=new TreeLinkNode(1);
    TreeLinkNode *left=new TreeLinkNode(2);
    TreeLinkNode *right=new TreeLinkNode(3);
    TreeLinkNode *leftRight=new TreeLinkNode(4);
    TreeLinkNode *rightRight=new TreeLinkNode(5);
    root->left=left;
    root->right=right;
    left->right=leftRight;
    right->left=rightRight;
    solve(root);
    system("pause");
    return 0;
}

좋은 웹페이지 즐겨찾기