二叉树的遍历/递归/非递归/翻转

二叉树的定义

// 定义一个二叉树节点
struct BiTreeNode {
    int value;
    struct BiTreeNode *left;
    struct BiTreeNode *right;
};

先序遍历 (递归的形式)

void preOrderTraversal(struct BiTreeNode *node) {
    if (node != NULL) {
        printf("%d", node->value);     //  先序遍历
        preOrderTraversal(node->left); // 递归调用，前序遍历左子树
        // printf("%d", node->value);  // 中序遍历
        preOrderTraversal(node->right); // 递归调用，前序遍历右子树
        // printf("%d", node->value);  // 后序遍历
    }
}

先序遍历 （非递归的形式）

void preOrderTraversalWithNonrecursively(struct BiTreeNode *T) {
    std::stack<BiTreeNode *> s;
    s.push(T); // 先让根进栈
    
    while (!s.empty()) {
        BiTreeNode *temp = s.top(); // 从栈顶取出来
        printf("%d", temp->value);
        s.pop(); // 从栈顶移除
        if (temp->right) {
            s.push(temp->right);
        }
        if (temp->left) {
            s.push(temp->left);
        }
    }
}

中序遍历 （非递归的形式）

#include <stack>

void InOrderTraversalWithNonrecursively(struct BiTreeNode *node) {
    if (node == NULL) {
        return;
    }
    std::stack<BiTreeNode *> s;
    s.push(node);
    
    struct BiTreeNode *current = node->left;
    
    while (current != NULL || !s.empty()) {
        while (current != NULL) { // 一直向左走
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        printf("%d", current->value);
        current = current->right;
    }
}

二叉树翻转

struct BiTreeNode * reverseBiTree(struct BiTreeNode *node) {
    if (node == NULL) {
        return node;
    }
    struct BiTreeNode *n = (struct BiTreeNode *)malloc(sizeof(struct BiTreeNode));
    n->value = node->value;
    // 先翻转左边的节点赋值给右边
    if (node->left != NULL) {
        node->right = reverseBiTree(node->left);
    } else {
        node->right = NULL;
    }
    // 再翻转右边的节点赋值给左边
    if (node->right) {
        node->left = reverseBiTree(node->right);
    } else {
        node->left = NULL;
    }
    return n;
}

完整的代码

#include <stack>

// 定义一个二叉树节点
struct BiTreeNode {
    int value;
    struct BiTreeNode *left;
    struct BiTreeNode *right;
};

// 先序遍历 (递归的形式)
void preOrderTraversal(struct BiTreeNode *node) {
    if (node != NULL) {
        printf("%d", node->value);     //  先序遍历
        preOrderTraversal(node->left); // 递归调用，前序遍历左子树
        // printf("%d", node->value);  // 中序遍历
        preOrderTraversal(node->right); // 递归调用，前序遍历右子树
        // printf("%d", node->value);  // 后序遍历
    }
}

// 先序遍历 （非递归的形式）
void preOrderTraversalWithNonrecursively(struct BiTreeNode *T) {
    std::stack<BiTreeNode *> s;
    s.push(T); // 先让根进栈
    
    while (!s.empty()) {
        BiTreeNode *temp = s.top(); // 从栈顶取出来
        printf("%d", temp->value);
        s.pop(); // 从栈顶移除
        if (temp->right) {
            s.push(temp->right);
        }
        if (temp->left) {
            s.push(temp->left);
        }
    }
}

// 中序遍历 （非递归的形式）
void InOrderTraversalWithNonrecursively(struct BiTreeNode *node) {
    if (node == NULL) {
        return;
    }
    std::stack<BiTreeNode *> s;
    s.push(node);
    
    struct BiTreeNode *current = node->left;
    
    while (current != NULL || !s.empty()) {
        while (current != NULL) { // 一直向左走
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        printf("%d", current->value);
        current = current->right;
    }
}

// 二叉树翻转
struct BiTreeNode * reverseBiTree(struct BiTreeNode *node) {
    if (node == NULL) {
        return node;
    }
    struct BiTreeNode *n = (struct BiTreeNode *)malloc(sizeof(struct BiTreeNode));
    n->value = node->value;
    // 先翻转左边的节点赋值给右边
    if (node->left != NULL) {
        node->right = reverseBiTree(node->left);
    } else {
        node->right = NULL;
    }
    // 再翻转右边的节点赋值给左边
    if (node->right) {
        node->left = reverseBiTree(node->right);
    } else {
        node->left = NULL;
    }
    return n;
}