#include<iostream>
using namespace std;
typedef struct TreeNode* Tree;
struct TreeNode {
int Element;
Tree Left;
Tree Right;
};
struct Stack {
Tree Node;
Stack* Next;
};
void Push(Tree, Stack*);
void CreatNew(int, Tree,Stack*);
Tree CreatNULL(Tree,Stack*);
Tree Pop(Stack*);
void PostOrderTraversal(Tree);
int main() {
int node_number,node_index;
char operation[4];
Stack* S=new Stack;
S->Next = NULL;
Tree root;
root = new TreeNode;
cin >> node_number;
cin >> operation;
cin >> node_index;
Tree new_node = new TreeNode;
root->Left = new_node;
root->Element = node_index;
Push(root, S);
Tree temp = new_node;
for (int i = 1; i < 2 * node_number; i++) {
cin >> operation;
if (!strcmp(operation, "Push")) {
cin >> node_index;
CreatNew(node_index, temp, S);
}
else
temp=CreatNULL(temp,S);
}
temp = NULL;
PostOrderTraversal(root);
return 0;
}
void CreatNew(int x, Tree T, Stack* S) {
Tree new_node = new TreeNode;
T->Left = new_node;
T->Element = x;
Push(T, S);
T = T->Left;
}
void Push(Tree T, Stack* S) {
Stack* temp = new Stack;
temp->Next = S->Next;
S->Next = temp;
temp->Node = T;
}
Tree CreatNULL(Tree T,Stack* S) {
T = NULL;
Tree poped;
poped = Pop(S);
Tree anewnode=new TreeNode;
anewnode = poped->Right;
return anewnode;
}
Tree Pop(Stack* S) {
Stack* temp;
Tree tempTree;
temp = S->Next;
S->Next = temp->Next;
tempTree = temp->Node;
delete(temp);
return tempTree;
}
void PostOrderTraversal(Tree T) {
if (T) {
PostOrderTraversal(T->Left);
PostOrderTraversal(T->Right);
cout << T->Element<<" ";
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/269220.html
標籤：C++ 語言
上一篇：QGraphicsPixmapItem::setRotation()函式呼叫后滑鼠縮放view，圖片消失問題？
下一篇：請問一下 為什么會不斷輸入