二叉树相关算法：迭代式与递归式中序遍历

此处以一个用数组表示的完全二叉树为例，根节点为1

流程：

1、从根节点出发，一路向左，把每一个左孩子（如果有）推入辅助栈

2、当走到最后（左孩子不存在）时，从栈中弹出一个节点进行访问

3、试着转向右孩子进行访问

vector<int>node;
vector<int>tree;
stack<int> s;
void goAlongLeftBranch(int x) {
    while (x<=N)
    {
        s.push(x);
        x = 2 * x;
    }
}
int counter = 1;
void travIn() {
    int x = 1;
    while (true)
    {
        goAlongLeftBranch(x);
        if (s.empty())
        {
            break;
        }
        x = s.top();
        s.pop();
        int temp = node[counter]; 
        tree[x] = temp;  //访问节点
        counter++;
        x = 2 * x + 1; //转向右孩子（本例为完全二叉树）
    }
}
//递归式中序遍历：
void travInRecur(int root){
    int x=root;
    if(2*x<=N){
        travInRecur(2*x);
    }
    visit(x);
    if(2*x+1<=N){
        travInRecur(2*x+1);
    }
}