二叉树的简单操作

• 1. 二叉树操作
  • 1.1. 二叉树遍历：
  • 1.2. 二叉树的高
  • 1.3. 二叉树遍历的非递归实现

1. 二叉树操作

1.1. 二叉树遍历：

问题描述：使用前序遍历、中序遍历、后序遍历和层次遍历输出二叉树的节点。

求解策略：根据定义，前三种遍历采用递归实现（也可以用非递归实现，见本文最后），而层次遍历采用队列（不是栈）来存储将要访问的元素。

/* visit 函数 */
template<typename T>
void visit(binaryTreeNode<T>* x){
    cout << x->element << ' ';
}

/* 前序遍历 */
template<typename T>
void preOrder(binaryTreeNode<T>* t){
    if (t != NULL){
        visit(t);
        preOrder(t->leftChild);         // 前序遍历左子树
        preOrder(t->rightChild);        // 前序遍历右子树
    }
}

/* 中序遍历 */
template<typename T>
void inOrder(binaryTreeNode<T>* t){
    if (t != NULL){
        inOrder(t->leftChild);         // 中序遍历左子树
        visit(t);
        inOrder(t->rightChild);        // 中序遍历右子树
    }
}

/* 后序遍历 */
template<typename T>
void postOrder(binaryTreeNode<T>* t){
    if (t != NULL){
        postOrder(t->leftChild);         // 后序遍历左子树
        postOrder(t->rightChild);        // 后序遍历右子树
        visit(t);
    }
}

/* 层次遍历 */
template <typename T>
void levelOrder(binaryTreeNode<T>* t){
    queue<binaryTreeNode<T>*> q;
    binaryTreeNode<E> *t = root;
    while (t != NULL){
        visit(t);

        // 将 s 的孩子插入队列
        if (t->leftChild != NULL)
            q.push(t->leftChild);
        if (t->rightChild != NULL)
            q.push(t->rightChild);

        // get next node to visit
        if (q.empty())
            return;
        t = q.front();
        q.pop();
    }
}

时间复杂度：这四种方法的时间和空间复杂度均为 O(n)。

1.2. 二叉树的高

问题描述：给一颗二叉树，求它的高度。

求解策略：利用递归。先取得左子树高度，然后获取右子树高度，最后把左右子树高度的最大者加上 1，即得到树的高度。

/* 确定二叉树的高度 */
template<typename T>
int height(binaryTreeNode<T>* t){
    if (t == NULL)
        return 0;                       // 空树
    int hl = height(t->leftChild);      // 左树高
    int hr = height(t->rightChild);     // 右树高
    int max = (hl>hr) ? hl : hr;
    return ++max;
}

1.3. 二叉树遍历的非递归实现

问题描述：用非递归方法实现二叉树的前序遍历、中序遍历和后序遍历。

思路：

前序遍历（非递归）：对任意结点 currNode

1. 访问结点 currNode，并将其入栈；
2. 判断结点 currNode 的左孩子是否为空，若不空，则将当前结点的左孩子置为当前结点；若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前结点 currNode；
3. 直到当前结点为空并且栈为空，遍历结束。

中序遍历（非递归）：对任意结点 currNode

1. 若其左孩子不为空，则将 currNode 入栈，并将 currNode 的左孩子结点置为 currNode，然后再对当前结点进行相同处理；
2. 若其左孩子为空，则取栈顶元素进行出栈操作，访问该栈顶结点，然后将当前的结点 currNode 置为栈顶结点的右孩子；
3. 直到 currNode 为空并且栈为空，遍历结束。

后序遍历（非递归，三种实现）：

• 实现一：
  要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点 currNode，先将其入栈。如果 currNode 不存在左孩子和右孩子，则可以直接访问它；或者 currNode 存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将 currNode 的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

• 实现二：
  该方法与方法一同理，实现方法不同。

• 实现三：
  用两个栈，先将根结点入第一个栈，然后每次从第一个栈中取出栈顶结点，将其如第二个栈，然后再将其左孩子和右孩子（如果有的话）依次入第一个栈，直到第一个栈为空。再将第二个栈的元素依次出栈即可。

代码实现：

#include <iostream>
#include <stack>
using namespace std;

struct BinaryTree{
    int val;
    BinaryTree* left;
    BinaryTree* right;
    BinaryTree() : val(0), left(nullptr), right(nullptr) {}
    BinaryTree(int n) : val(n), left(nullptr), right(nullptr) {}
};

/* 前序遍历非递归实现 */
void preOrder(BinaryTree* root){
    if (root == nullptr) return;
    stack<BinaryTree*> s;
    BinaryTree* currNode = root;
    while (currNode != nullptr || !s.empty()){
        while (currNode != nullptr){
            cout << currNode->val << ' ';
            s.push(currNode);
            currNode = currNode->left;
        }
        if (!s.empty()){
            currNode = s.top();
            s.pop();
            currNode = currNode->right;
        }
    }
}

/* 中序遍历非递归实现 */
void inOrder(BinaryTree* root){
    if (root == nullptr) return;
    stack<BinaryTree*> s;
    BinaryTree* currNode = root;
    while (currNode != nullptr || !s.empty()){
        while (currNode != nullptr){
            s.push(currNode);
            currNode = currNode->left;
        }
        if (!s.empty()){
            currNode = s.top();
            cout << currNode->val << " ";
            s.pop();
            currNode = currNode->right;
        }
    }
}

/* 后序遍历非递归实现 */
void postOrder(BinaryTree* root){
    if (root == nullptr) return;
    stack<BinaryTree*> s;
    BinaryTree* currNode = nullptr;
    BinaryTree* preNode = nullptr;
    s.push(root);
    while (!s.empty()){
        currNode = s.top();
        if ((currNode->left == nullptr && currNode->right == nullptr) || 
        (preNode != nullptr && (preNode == currNode->left || preNode == currNode->right))){
            cout << currNode->val << " ";   // 当前结点没有孩子或者孩子结点已经被访问过
            s.pop();
            preNode = currNode;
        } else {
            // 将结点的右孩子和左孩子依次入栈
            if (currNode->right != nullptr)
                s.push(currNode->right);
            if (currNode->left != nullptr)
                s.push(currNode->left);
        }
    }
}

/* 后序遍历非递归实现 2 */
void postOrder2(BinaryTree* root){
    if (root == nullptr) return;
    stack<BinaryTree*> s;
    BinaryTree* currNode = root;
    BinaryTree* preNode = nullptr;
    while (currNode != nullptr || !s.empty()){
        while (currNode != nullptr){
            s.push(currNode);
            currNode = currNode->left;
        }
        if (!s.empty()){
            currNode = s.top();
            // 当前结点的右孩子如果为空或者已经被访问过了，则访问当前结点
            if (currNode->right == nullptr || currNode->right == preNode){
                cout << currNode->val << " ";
                preNode = currNode;
                s.pop();
                currNode = nullptr;
            } else {
                currNode = currNode->right;     // 否则访问右孩子
            }
        }
    }
}

/* 后序遍历非递归实现 3 */
void postOrder3(BinaryTree* root){      // 双栈法
    if (root == nullptr) return;
    stack<BinaryTree*> s1, s2;
    BinaryTree* currNode = root;
    s1.push(currNode);
    while (!s1.empty()){
        currNode = s1.top();
        s1.pop();
        s2.push(currNode);
        if (currNode->left)
            s1.push(currNode->left);
        if (currNode->right)
            s1.push(currNode->right);
    }
    while (!s2.empty()){
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

// 树的结构如下：
//           1
//         /   \
//        2     3
//       / \     \
//      4   5     6
//         /     /
//        7     8
//         \
//          9
int main(int argc, char** argv){
    BinaryTree* node1 = new BinaryTree(1);
    BinaryTree* node2 = new BinaryTree(2);
    BinaryTree* node3 = new BinaryTree(3);
    BinaryTree* node4 = new BinaryTree(4);
    BinaryTree* node5 = new BinaryTree(5);
    BinaryTree* node6 = new BinaryTree(6);
    BinaryTree* node7 = new BinaryTree(7);
    BinaryTree* node8 = new BinaryTree(8);
    BinaryTree* node9 = new BinaryTree(9);

    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node5->left = node7;
    node7->right = node9;
    node3->right = node6;
    node6->left = node8;

    cout << "preorder: " << endl;
    preOrder(node1);
    cout << endl << "inorder: " << endl;
    inOrder(node1);
    cout << endl << "postOrder: " << endl;
    postOrder(node1);
    cout << endl << "postOrder2: " << endl;
    postOrder2(node1);
    cout << endl << "postOrder3: " << endl;
    postOrder3(node1);

    return 0;
}

代码输出：

preorder:
1 2 4 5 7 9 3 6 8
inorder:
4 2 7 9 5 1 3 8 6
postOrder:
4 9 7 5 2 8 6 3 1
postOrder2:
4 9 7 5 2 8 6 3 1
postOrder3:
4 9 7 5 2 8 6 3 1