L2-006. 树的遍历

    xiaoxiao2021-03-25  84

    L2-006. 树的遍历

    时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    输入格式:

    输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

    输出格式:

    在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

    输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例: 4 1 6 3 5 7 2 #include <iostream> #include <queue> using namespace std; struct Node { int data; Node* lchlid; Node* rchild; }; Node* build_tree(int back[],int in[],int length) { if(length==0){ return NULL; } Node* temp = new Node;; int pos = 0; while(in[pos]!= back[length-1]){ pos++; } temp->data = in[pos]; temp->lchlid = build_tree(back,in,pos); temp->rchild = build_tree(back+pos,in+pos+1,length-pos-1); return temp; } bool first = true; void dfs(Node* root) //层次遍历 { queue<Node*> Q; Q.push(root); while(!Q.empty()){ Node* temp = Q.front(); if(first){ cout<<temp->data; first = false; } else { cout<<" "<<temp->data; } Q.pop(); if(temp->lchlid){ Q.push(temp->lchlid); } if(temp->rchild){ Q.push(temp->rchild); } } } int main() { int n; cin>>n; int back[n],in[n]; for(int i=0;i<n;i++){ cin>>back[i]; } for(int i=0;i<n;i++){ cin>>in[i]; } Node* root = build_tree(back,in,n); dfs(root); return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-50290.html

    最新回复(0)