美文网首页
二叉树的遍历

二叉树的遍历

作者: 1nvad3r | 来源:发表于2020-08-14 10:16 被阅读0次

递归:

//先序遍历
void preOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    printf("%d\n", root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

//中序遍历
void inOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->lchild);
    printf("%d\n", root->data);
    inOrder(root->rchild);
}

//后序遍历
void postOrder(Node *root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("%d\n", root->data);
}

//层次遍历
void levelOrder(Node *root) {
    queue<Node *> q;
    q.push(root);
    while (!q.empty()) {
        Node *now = q.front();
        q.pop();
        printf("%d\n", now->data);
        if (now->lchild != NULL) {
            q.push(now->lchild);
        }
        if (now->rchild != NULL) {
            q.push(now->rchild);
        }
    }
}

非递归:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode top = stack.poll();
            res.add(top.val);
            if (top.right != null) {
                stack.push(top.right);
            }
            if (top.left != null) {
                stack.push(top.left);
            }
        }
        return res;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == pre) {
                res.add(root.val);
                pre = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}
无论是先序遍历序列还是后序遍历序列还是层次遍历序列,都必须知道中序遍历序列才能唯一确定一棵树。
例1

给定一棵二叉树的先序遍历序列和中序遍历序列,重建这棵二叉树。
分析:


#include <cstdio>

using namespace std;

const int maxn = 100;

//二叉树存储结构
struct Node {
    int data;
    Node *lchild;
    Node *rchild;
};

int pre[maxn], in[maxn];

Node *create(int preL, int preR, int inL, int inR) {
    if (preL > preR) {
        return NULL;
    }
    Node *root = new Node;
    root->data = pre[preL];
    int k;
    //在中序序列中找到根结点位置
    for (k = inL; k <= inR; k++) {
        if (in[k] == pre[preL]) {
            break;
        }
    }
    int numLeft = k - inL;//左子树结点个数
    root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);
    root->rchild = create(preL + numLeft + 1, preR, k + 1, inR);
    return root;
}

1020 Tree Traversals

1086 Tree Traversals Again

1102 Invert a Binary Tree

相关文章

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 二叉树遍历

    二叉树 二叉树的存储结构 前序遍历 中序遍历 后序遍历 遍历代码 反转二叉树 深入学习二叉树 二叉树-你必须要懂!...

  • 二叉树操作

    树节点 逐行顺序解析二叉树 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 删除指定数值的节点 前序遍历顺序存储的...

  • 关于二叉树的算法题

    前序遍历中序遍历后序遍历判断是否是平衡二叉树判断是否是对称二叉树判断二叉树高度按照层遍历二叉树判断二叉树宽度

  • 二叉树三种遍历Swift代码实现

    二叉树的三种遍历 二叉树 前序遍历 中序遍历 后序遍历 另外 不得不说,得到二叉树的前序遍历和中序遍历的结果或者后...

  • 数据结构与算法之二叉树遍历(七)

    目录 前序遍历中序遍历后序遍历层序遍历遍历方式的选择条件根据遍历结果重构二叉树翻转二叉树计算二叉树的高度判断一棵树...

  • 二叉树的遍历

    二叉树的遍历 二叉树遍历 分为前序遍历、中序遍历和后序遍历。 前序遍历 (DLR) 先访问根节点,然后前序遍历左子...

  • 数据结构:树的实现和遍历(c++)

    (一)二叉树的遍历——递归实现 二叉树常见的遍历方式分为前序遍历、中序遍历和后序遍历。 1 前序遍历 前序遍历也叫...

  • 二叉树的蛇形层次遍历(LeetCode.103)

    题目 解析 首先参考二叉树的层次遍历层次遍历二叉树(LeetCode--102二叉树的层次遍历)[https://...

  • 算法精选题总结之二叉树类

    1.二叉树的中序遍历中序遍历的迭代方法中序遍历的递归方法2.二叉树前序遍历3.二叉树后续遍历4.二叉树的最近公共祖...

网友评论

      本文标题:二叉树的遍历

      本文链接:https://www.haomeiwen.com/subject/dokbdktx.html