二叉树的存储方式和遍历方式详解

二叉树的存储方式和遍历方式详解

引用

CSDN

1.

https://blog.csdn.net/qq_51352130/article/details/143312785

二叉树是数据结构中一种重要的树形结构，其存储和遍历方式是算法学习中的基础内容。本文将详细介绍二叉树的两种存储方式（链式存储和顺序存储）以及三种主要的遍历方式（深度优先搜索DFS和广度优先搜索BFS）。通过具体的代码示例，帮助读者深入理解二叉树的存储和遍历方法。

二叉树的存储方式

二叉树的存储方式主要有两种：链式存储和顺序存储。

链式存储

链式存储通过指针将分布在各个地址的节点串联起来。每个节点包含数据域和两个指针域，分别指向其左右子节点。

链式存储的二叉树节点定义方式如下：

public class TreeNode {
    int val;
    TreeNode left; //表示左子节点的引用，类型为TreeNode
    TreeNode right;
    
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

顺序存储

顺序存储是将二叉树的节点按照某种顺序存储在数组中。如果父节点的数组下标是 i，那么它的左孩子就是 2i + 1，右孩子是 2i + 2，孩子的父节点为 (i-1)/2。

二叉树的遍历方式

二叉树的遍历方式主要有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索可以分为前序遍历、中序遍历和后序遍历。每种遍历方式都可以通过递归和迭代两种方法实现。

DFS-递归遍历

前序遍历

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
      List<Integer> result = new ArrayList<Integer>();
      preorder(root, result);
      return result;
  }
  public void preorder(TreeNode root, List<Integer> result) {
      if (root == null) {
          return;
      }
      result.add(root.val);
      preorder(root.left, result);
      preorder(root.right, result);
  }
}

中序遍历

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             
        inorder(root.right, list);
    }
}

后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);           
    }
}

DFS-迭代遍历

迭代遍历通常使用栈来辅助实现。

前序遍历

前序遍历的顺序是：中-左-右，入栈顺序是：中-右-左。

class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
      List<Integer> result = new ArrayList<>();
      if (root == null){
          return result;
      }
      Stack<TreeNode> stack = new Stack<>();
      stack.push(root);
      while (!stack.isEmpty()){
          TreeNode node = stack.pop();
          result.add(node.val);
          if (node.right != null){
              stack.push(node.right);
          }
          if (node.left != null){
              stack.push(node.left);
          }
      }
      return result;
  }
}

中序遍历

中序遍历的顺序是：左-中-右，入栈顺序是：左-右。

class Solution {
  public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> result = new ArrayList<>();
      Stack<TreeNode> stack = new Stack<>();
      TreeNode cur = root;
      while(cur != null || !stack.isEmpty()){
          if(cur != null){
              stack.push(cur);
              cur = cur.left;
          }
          else{
              cur = stack.pop();
              result.add(cur.val);
              cur = cur.right;
          }
      }
      return result;
  }
}

后序遍历

后序遍历的顺序是：左-右-中，可以通过先实现前序遍历（中-右-左），然后反转结果集来实现。

class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
      List<Integer> result = new ArrayList<>();
      if (root == null){
          return result;
      }
      Stack<TreeNode> stack = new Stack<>();
      stack.push(root);
      while (!stack.isEmpty()){
          TreeNode node = stack.pop();
          result.add(node.val);
          if (node.left != null){
              stack.push(node.left);
          }
          if (node.right != null){
              stack.push(node.right);
          }
      }
      Collections.reverse(result);
      return result;
  }
}

广度优先搜索（BFS）

广度优先搜索通常用于层次遍历，即按层访问二叉树的节点。

BFS-层次遍历

层次遍历可以使用队列来辅助实现。

迭代方式

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            List<Integer> itemList = new ArrayList<>();
            int levelSize = que.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);
                if(tmpNode.left != null){
                    que.offer(tmpNode.left);
                }
                if(tmpNode.right != null){ 
                    que.offer(tmpNode.right);
                }
            }
            resList.add(itemList);
        }
        return resList;
    }
}

递归方式

class Solution {
    List<List<Integer>> resList = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFun01(root, 0);
        return resList;
    }    
    public void checkFun01(TreeNode node, int deep) {
        if (node == null) {
            return;
        }
        deep++;
        if (resList.size() < deep) {
            resList.add(new ArrayList<Integer>());
        }
        resList.get(deep - 1).add(node.val);
        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }
}

对于自底向上的层次遍历，可以在最后将结果集翻转：Collections.reverse(resList);