定义二叉树的节点

struct BTNode {
    int data;
    BTNode *left;
    BTNode *right;
};

先序建立二叉树

思路：以数组中的元素先序构建二叉树，过程就是不断插入，直至数组中没有元素

// 先序建立二叉树
void insert_node(BTNode **root, int *data, int i) {
    if (i <= data[0]) {
        *root = new BTNode();
        (*root)->data = data[i];
        (*root)->left = NULL;
        (*root)->right = NULL;
        insert_node(&(*root)->left, data, 2 * i);
        insert_node(&(*root)->right, data, 2 * i + 1);
    }
}

遍历二叉树的操作，先序、中序、后续及层序遍历

递归实现二叉树的遍历

void pre_order(BTNode *root) {
    if (root != NULL) {
        cout << root->data << " ";
        pre_order(root->left);
        pre_order(root->right);
    }
}

void in_order(BTNode *root) {
    if (root != NULL) {
        in_order(root->left);
        cout << root->data << " ";
        in_order(root->right);
    }
}

void post_order(BTNode *root) {
    if (root != NULL) {
        post_order(root->left);
        post_order(root->right);
        cout << root->data << " ";
    }
}

非递归实现二叉树的遍历

先序遍历

void non_pre_order(BTNode *root) {
    stack<BTNode*> s;
    BTNode *cur = root;

    while (cur != NULL || !s.empty()) {
        while (cur != NULL) {
            cout << cur->data << " ";
            s.push(cur);
            cur = cur->left;
        }

        if (!s.empty()) {
            cur = s.top();
            s.pop();
            cur = cur->right;
        }
    }
}

中序遍历

void non_in_order(BTNode *root) {
    stack<BTNode*> s;
    BTNode *cur = root;

    while (cur != NULL || !s.empty()) {
        while (cur != NULL) {
            s.push(cur);
            cur = cur->left;
        }

        if (!s.empty()) {
            cur = s.top();
            s.pop();
            cout << cur->data << " ";
            cur = cur->right;
        }
    }
}

后序遍历

void non_post_order(BTNode *root) {
    stack<BTNode*> s1, s2;
    BTNode *cur = root;

    s1.push(cur);
    while (!s1.empty()) {
        cur = s1.top();
        s1.pop();
        s2.push(cur);

        if (cur->left != NULL)
            s1.push(cur->left);
        if (cur->right != NULL)
            s1.push(cur->right);
    }

    while (!s2.empty()) {
        cout << s2.top()->data << " ";
        s2.pop();
    }
}

层序遍历

void floor_order(BTNode *root) {
    queue<BTNode*> q;
    BTNode *cur;

    if (root != NULL)
        q.push(root);

    while (!q.empty()) {
        cur = q.front();
        cout << cur->data << " ";
        q.pop();

        if (cur->left != NULL)
            q.push(cur->left);
        if (cur->right != NULL)
            q.push(cur->right);
    }
}

测试代码

int main(void) {
    int data[] = {5, 1, 2, 3, 4, 5};
    BTNode *root = NULL;

    insert_node(&root, data, 1);

    // 先序遍历二叉树
    cout << "递归先序遍历二叉树" << endl;
    pre_order(root);
    cout << "\n非递归先序遍历二叉树\n";
    non_pre_order(root);
    cout << "\n递归中序遍历二叉树\n";
    // 中序遍历二叉树
    in_order(root);
    cout << "\n非递归中序遍历二叉树\n";
    non_in_order(root);
    cout << "\n递归后序遍历二叉树\n";
    // 后序遍历二叉树
    post_order(root);
    cout << "\n非递归后序遍历二叉树\n";
    non_post_order(root);
    cout << endl;
    // 层序遍历二叉树
    cout << "层序遍历二叉树\n";
    floor_order(root);
    cout << endl;

    return 0;
}