03-树3 Tree Traversals Again（树的遍历）
03-树3 Tree Traversals Again
分数 25
作者 陈越
单位 浙江大学
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
Sample Output:
3 4 2 6 5 1
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
入栈是前序遍历，弹出是中序遍历，输出要求后续遍历。
1)后序遍历递归写法
/**
1)后序遍历递归写法
*/
#include <iostream>
#include <stack>
using namespace std;
const int maxn=35;
typedef int Tree;
#define Null -1
struct TNode
{
Tree left,right;
TNode()
{
left=right=Null;
}
}tree[maxn];
Tree CreateTree(TNode *T);
void BehTraver(Tree root);
int flag=0;
int main()
{
Tree root=CreateTree(tree);
BehTraver(root);
return 0;
}
Tree CreateTree(TNode *T)
{
int root=Null;
int n;
cin >> n;
getchar(); //吸收掉换行符
string str;
int index,pre=Null; //index存储结点的下标，pre存储结点的孩子节点的下标
stack<int> st;
int flag=0,coun=0; //当第一次Push与Pop的数目相等时，此时Pop掉的结点下标就是根节点
for(int i=1;i<=2*n;++i)
{
getline(cin,str);
if(str.substr(0,3)=="Pus")
{
++coun;
index=0;
for(int j=5;j<(int)str.size();++j) //得到结点的下标
index=index*10+str[j]-'0';
if(pre!=Null&&flag==0) //如果非首结点且上一个输入是Push
T[pre].left=index;
else if(pre!=Null&&flag==1) //如果上一个节点是Pop
T[pre].right=index;
pre=index; //要将此节点的下标赋给pre存储
st.push(index);
flag=0;
}
else if(str.substr(0,3)=="Pop")
{
--coun;
pre=st.top();
st.pop();
flag=1;
}
if(coun==0&&root==Null)
root=pre;
}
return root;
}
void BehTraver(Tree root)
{
if(root!=Null)
{
BehTraver(tree[root].left);
BehTraver(tree[root].right);
if(flag==0)
flag=1;
else
cout << ' ';
cout << root;
}
}
*/
2)后序遍历非递归写法
///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(Tree root)
{
stack<int> st;
int fir=root,sec;
while(!st.empty()||fir!=Null)
{
while(fir!=Null)
{
st.push(fir);
st.push(fir);
fir=tree[fir].left;
}
if(!st.empty())
fir=st.top();
st.pop();
if(!st.empty())
sec=st.top();
else //此处要注意，如果是树根，则树根取出来后栈就空了，所以此处要特判一下
{
if(flag==0)
flag=1;
else
cout << ' ';
cout << fir;
break;
}if(fir==sec)
fir=tree[fir].right;
else //第二次结点出栈后，打印输出
{
if(flag==0)
flag=1;
else
cout << ' ';
cout << fir;
fir=Null; //打印节点后，要把fir赋为Null，否则会造成多余的结点从while循环入栈
}
}
}
/**
2)后序遍历非递归写法
*/
#include <iostream>
#include <stack>
using namespace std;
const int maxn=35;
typedef int Tree;
#define Null -1
struct TNode
{
Tree left,right;
TNode()
{
left=right=Null;
}
}tree[maxn];
Tree CreateTree(TNode *T);
void BehTraver(Tree root);
int flag=0;
int main()
{
Tree root=CreateTree(tree);
BehTraver(root);
return 0;
}
Tree CreateTree(TNode *T)
{
int root=Null;
int n;
cin >> n;
getchar();
string str;
int index,pre=Null;
stack<int> st;
int flag=0,coun=0;
for(int i=1;i<=2*n;++i)
{
getline(cin,str);
if(str.substr(0,3)=="Pus")
{
++coun;
index=0;
for(int j=5;j<(int)str.size();++j)
index=index*10+str[j]-'0';
if(pre!=Null&&flag==0)
T[pre].left=index;
else if(pre!=Null&&flag==1)
T[pre].right=index;
pre=index;
st.push(index);
flag=0;
}
else if(str.substr(0,3)=="Pop")
{
--coun;
pre=st.top();
st.pop();
flag=1;
}
if(coun==0&&root==Null)
root=pre;
}
return root;
}
///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(Tree root)
{
stack<int> st;
int fir=root,sec;
while(!st.empty()||fir!=Null)
{
while(fir!=Null)
{
st.push(fir);
st.push(fir);
fir=tree[fir].left;
}
if(!st.empty())
fir=st.top();
st.pop();
if(!st.empty())
sec=st.top();
else //此处要注意，如果是树根，则树根取出来后栈就空了，所以此处要特判一下
{
if(flag==0)
flag=1;
else
cout << ' ';
cout << fir;
break;
}
if(fir==sec)
fir=tree[fir].right;
else //第二次结点出栈后，打印输出
{
if(flag==0)
flag=1;
else
cout << ' ';
cout << fir;
fir=Null; //打印节点后，要把fir赋为Null，否则会造成多余的结点从while循环入栈
}
}
}
3)知道前序遍历结果和中序遍历结果，得到后序遍历结果；
算法笔记代码：
/**
3)知道前序遍历结果和中序遍历结果，得到后序遍历结果；
算法笔记代码：
*/
/**
#include <iostream>
#include <string>
#include <stack>
using namespace std;
const int maxn=35;
int pre[maxn],mid[maxn],prenum=0,midnum=0;
int n;
bool flag=0;
typedef struct TNode* Tree;
struct TNode
{
int data;
Tree lchild,rchild;
TNode()
{
lchild=rchild=NULL;
}
};
void Read_data(); //读入数据
//用前序遍历结果和中序遍历结果，得到后序遍历结果；
Tree create_tree_with_pre_and_mid(int preL,int preR,int midL,int midR);
void Traver_Beh(Tree BT); //后序遍历树；
int main()
{
Read_data();
Tree BT=create_tree_with_pre_and_mid(1,prenum,1,midnum);
Traver_Beh(BT);
return 0;
}
void Read_data()
{
cin >> n;
stack<int> st;
for(int i=-n;i<n;++i)
{
string str;
cin >> str;
if(str=="Push")
{
int index;
cin >> index;
st.push(index);
pre[++prenum]=index;
}
else
{
int top=st.top();
st.pop();
mid[++midnum]=top;
}
}
}
Tree create_tree_with_pre_and_mid(int preL,int preR,int midL,int midR)
{
if(preL>preR)
return NULL;
Tree NewNode = new TNode;
int k;
for(k=midL;k<=midR;++k)
if(mid[k]==pre[preL])
break;
int numL=k-midL; //得到左子树的结点个数
NewNode->data=mid[k];
NewNode->lchild=create_tree_with_pre_and_mid(preL+1,preL+numL,midL,midL+numL-1);
NewNode->rchild=create_tree_with_pre_and_mid(preL+numL+1,preR,midL+numL+1,midR);
return NewNode; // 别忘了返回根节点
}
void Traver_Beh(Tree BT)
{
if(BT)
{
Traver_Beh(BT->lchild);
Traver_Beh(BT->rchild);
if(flag==0)
flag=1;
else
cout << ' ';
printf("%d",BT->data);
}
}
*/
4)知道前序遍历结果和中序遍历结果，得到后序遍历结果；
用数组表示后序遍历结果：（浙大代码讲解）
/**
4)知道前序遍历结果和中序遍历结果，得到后序遍历结果；
用数组表示后序遍历结果：（浙大代码讲解）
*/
#include <iostream>
#include <string>
#include <stack>
using namespace std;
const int maxn=35;
int pre[maxn],mid[maxn],beh[maxn],prenum=0,midnum=0;
int n;
bool flag=0;
void Read_data(); //读入数据
//用前序遍历结果和中序遍历结果，得到后序遍历结果；
void create_tree_with_pre_and_mid(int preL,int midL,int behL,int num);
int main()
{
Read_data();
create_tree_with_pre_and_mid(1,1,1,n);
for(int i=1;i<=n;++i)
{
if(i!=1)
cout << ' ';
cout << beh[i];
}
return 0;
}
void Read_data()
{
cin >> n;
stack<int> st;
for(int i=-n;i<n;++i)
{
string str;
cin >> str;
if(str=="Push")
{
int index;
cin >> index;
st.push(index);
pre[++prenum]=index;
}
else
{
int top=st.top();
st.pop();
mid[++midnum]=top;
}
}
}
void create_tree_with_pre_and_mid(int preL,int midL,int behL,int num)
{
if(num==0) //递归边界
return;
if(num==1)
{
beh[behL]=pre[preL];
return ;
}
int root=pre[preL],index;
beh[behL+num-1]=root; //要将根节点存在beh数组里；每次都是以根结点为分界点，进行左右子树递归
for(index=0;index<=n;++index)
if(mid[midL+index]==root)
break;
int numL=index, numR=num-index-1;
create_tree_with_pre_and_mid(preL+1,midL,behL,numL);
create_tree_with_pre_and_mid(preL+numL+1,midL+numL+1,behL+numL,numR);
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献7条内容
所有评论(0)