数据结构-二叉树

二叉树

public class TreeNode {
     int val;
     TreeNode left;
     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;
     }

     public static TreeNode createTree(){
         TreeNode root = new TreeNode(1);
         root.left = new TreeNode(2);
         root.left.left = new TreeNode(4);
         root.left.right = new TreeNode(5);
         root.right = new TreeNode(3);
         root.right.left = new TreeNode(6);
         root.right.right = new TreeNode(7);
         return root;
     }
 }

二叉树是一棵有向树，其每个节点最多有两个子节点，称为左子树和右子树。
全二叉树是所有节点都有两个子节点的二叉树。

非全二叉树

二叉树的深度为节点的层数，深度为0的节点为根节点。

深度优先

深度优先遍历（Depth-First Search, DFS）是一种常用的树或图的遍历算法。它从根节点开始，沿着树的深度方向遍历节点，尽可能深入地访问每个分支，直到无法继续深入为止，然后回溯到上一个节点，继续访问其他未访问的分支

深度优先遍历（Depth-First Search, DFS）包括前序遍历、中序遍历和后序遍历：

• 前序遍历（根节点 -> 左子树 -> 右子树）的结果为：
  • 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
• 中序遍历（左子树 -> 根节点 -> 右子树）的结果为：
  • 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
• 后序遍历（左子树 -> 右子树 -> 根节点）的结果为：
  • 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1

广度优先遍历（Breadth-First Search, BFS）也称为层序遍历：

• 层序遍历（从上到下，从左到右）的结果为：
  • 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

public class DFSTreeTraversal {

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        StringBuilder sb = new StringBuilder();
        System.out.println(dfs(root, sb));
    }

    public static String dfs(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return sb.toString();
        }
        dfs(root.left, sb);
        dfs(root.right, sb);
        sb.append(root.val).append(",");
        return sb.toString();
    }
}

前序遍历

import java.util.Stack;

/**
 * 根结点 ---> 左子树 ---> 右子树
 */
@SuppressWarnings("ALL")
public class TreePreTraversal {

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        StringBuilder sb = new StringBuilder();
        System.out.println(preTraversalRecursion(root, sb));
        System.out.println(preTraversal(root));
    }

    public static String preTraversalRecursion(TreeNode root,StringBuilder sb) {
        if (root == null) {
            return sb.toString();
        }
        sb.append(root.val).append(",");
        preTraversalRecursion(root.left, sb);
        preTraversalRecursion(root.right, sb);
        return sb.toString();
    }

    public static String preTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                sb.append(root.val).append(",");
                stack.push(root);
                root = root.left;
            }else {
                root = stack.pop();
                root = root.right;
            }
        }
        return sb.toString();
    }

}

中序遍历

import java.util.Stack;

/**
 * 左子树 ---> 根结点 ---> 右子树
 */
@SuppressWarnings("ALL")
public class TreeMidTraversal {

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        StringBuilder sb = new StringBuilder();
        System.out.println(midTraversalRecursion(root, sb));
        System.out.println(midTraversal(root));
    }

    public static String midTraversalRecursion(TreeNode root,StringBuilder sb) {
        if (root == null) {
            return sb.toString();
        }
        midTraversalRecursion(root.left, sb);
        midTraversalRecursion(root.right, sb);
        sb.append(root.val).append(" ");
        return sb.toString();
    }

    public static String midTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> result = new Stack<>();

        StringBuilder sb = new StringBuilder();
        if (root != null) {
            stack.push(root);
        }
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            result.push(pop);
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        while (!result.isEmpty()) {
            sb.append(result.pop().val + " "); // 输出节点
        }
        return sb.toString();
    }
}

后序遍历

import java.util.Stack;

/**
 * 左子树 ---> 右子树 ---> 根结点
 */
@SuppressWarnings("ALL")
public class TreePostTraversal {

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        StringBuilder sb = new StringBuilder();
        System.out.println(postTraversalRecursion(root, sb));
        System.out.println(postTraversal(root));
    }

    public static String postTraversalRecursion(TreeNode root,StringBuilder sb) {
        if (root == null) {
            return sb.toString();
        }
        postTraversalRecursion(root.left, sb);
        sb.append(root.val).append(",");
        postTraversalRecursion(root.right, sb);
        return sb.toString();
    }

    public static String postTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            }else {
                root = stack.pop();
                sb.append(root.val).append(",");
                root = root.right;
            }
        }
        return sb.toString();
    }
}

广度优先

广度优先遍历（Breadth-First Search, BFS）是一种用于遍历或搜索树（或其他图结构）的算法。它从根节点开始，逐层访问所有节点，先访问同一层的所有节点，然后再访问下一层的节点。BFS 使用队列（Queue）来实现这一过程。
广度优先遍历的基本步骤

1. 初始化队列：将根节点加入队列。
2. 循环遍历：当队列不为空时，执行以下操作：
   • 从队列中取出一个节点。
   • 访问该节点（例如，打印节点的值或将其值添加到结果列表中）。
   • 将该节点的左子节点（如果存在）加入队列。
   • 将该节点的右子节点（如果存在）加入队列。
   • 结束条件：当队列为空时，遍历结束

import java.util.LinkedList;
import java.util.Queue;

public class BFSTreeTraversal {
                
    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        StringBuilder sb = new StringBuilder();
        System.out.println(bfs(root, sb));
    }

    public static String bfs(TreeNode root, StringBuilder sb) {
        if (root == null) return "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            sb.append(node.val).append(" ");
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return sb.toString();
    }
}

层序遍历

import java.util.LinkedList;
import java.util.Queue;

public class LevelOrderTreeTraversal {

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        StringBuilder sb = new StringBuilder();
        System.out.println(levelOrderTree(root, sb));
    }

    private static String levelOrderTree(TreeNode root, StringBuilder sb) {
        if (root == null) return "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            sb.append(node.val).append(" ");
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return sb.toString();
    }
}