浙大数据结构-二叉树-Tree Traversals Again

lnnn

2022 年 03 月 26 日

149 次浏览

暂无评论

3858字数

算法 C++ 学习笔记

> 是2014年秋季PAT甲级考试真题，稍微要动下脑筋，想通了其实程序很基础，建议尝试。

## 题目

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.

![](https://images.ptausercontent.com/30)
Figure 1### 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 **2****N** 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:

```in
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
```

### Sample Output:

```out
3 4 2 6 5 1
```

## 题解

> 思路：重构二叉树，然后递归后序遍历

`踩坑：结构体里面用了string类，一直段错误，暂时不知道为什么，暂时用char数组来输入字符串`

```
# include <iostream>
# include <cstring>
# include <stack>

using namespace std;

const int N = 50;
int n;

typedef struct INNode{
    int element;
    char inStr[5];
} inNode;

template<class T>
class node{
public:
    node(T ele){
        element = ele;
        next = NULL;
    }
    ~node(){}
    
public:
    T element;
    node* next;
};

template<class T>
class treeNode{
public:
    treeNode(T ele){
        element = ele;
        pLeft = NULL;
        pRight = NULL;
    }
public:
    T element;
    treeNode* pLeft;
    treeNode* pRight;
};

template<class T>
class tree{
public:
    tree(){
        pRoot = NULL;
        firstFlag = 1;
    }
    ~tree(){
        clear();
    }
    
    void postOrTra(){
        postOrderTraversal(pRoot);
        cout << endl;
    }

void clear(treeNode<T>* pTmpRoot){
        if(!pTmpRoot){
            return;
        }
        
        clear(pTmpRoot->pLeft);
        clear(pTmpRoot->pRight);
        delete pTmpRoot;
        return;
    }
private:
    void postOrderTraversal(treeNode<T>* pTmpRoot){
        if(!pTmpRoot){
            return;
        }
        
        postOrderTraversal(pTmpRoot->pLeft);
        postOrderTraversal(pTmpRoot->pRight);
        if(firstFlag){
            cout << pTmpRoot->element;
            firstFlag = 0;
        }else{
            cout << " " << pTmpRoot->element;
        }
    }
    
public:
    treeNode<T>* pRoot;
    int firstFlag;
};
    
    
int main(){
    int leftFlag = 1;
    
    stack<treeNode<int>*>* pStack = new stack<treeNode<int>*>;
    tree<int>* pTree = new tree<int>;
    
    treeNode<int>* pCurTreeNode = NULL;
    
    inNode* inN = new inNode[N];

cin >> n;
    n *= 2;
    
    for(int i = 0; i < n; i++){
        scanf("%s", inN[i].inStr);

if(!memcmp(inN[i].inStr, "Push", 5)){
            scanf("%d", &inN[i].element);
        } 
    }
    
    treeNode<int>* pNewNode = new treeNode<int>(inN[0].element);
    pTree->pRoot = pNewNode;
    pCurTreeNode = pNewNode;
    pStack->push(pNewNode);
    
    for(int i = 1; i < n ; i++){
        if(!memcmp(inN[i].inStr, "Push", 5)){
            pNewNode = new treeNode<int>(inN[i].element);
            
            if(leftFlag && pCurTreeNode){
                pCurTreeNode->pLeft = pNewNode;
            }else if(pCurTreeNode){
                pCurTreeNode->pRight = pNewNode;
            }
            
            pStack->push(pNewNode);
            pCurTreeNode = pNewNode;
            
            leftFlag = 1;
            
        }else{
            leftFlag = 0;
            if(!pStack->empty()){
                pCurTreeNode = pStack->top();
                pStack->pop();
            }
        }
    }
    
    pTree->postOrTra();
    
    return 0;
}
```

最后修改：2022 年 03 月 26 日