day13|二叉树理论

一、二叉树的定义

//定义一个二叉树：使用链式存储
public class TreeNode {int val; // 节点的值TreeNode left; // 左子节点TreeNode right; // 右子节点public TreeNode() {}// 构造函数，初始化节点值public TreeNode(int val){this.val=val;}// 构造函数，初始化节点值、左子节点和右子节点public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}

二、前序遍历

package com.thirteenday.tree;import java.util.ArrayList;
import java.util.List;//前序遍历
/*** 递归三部曲：*  1、确定递归函数的参数和返回值*  2、确定递归终止条件*  3、确定单层递归的逻辑*/
public class PreorderTraversal {/*** 1、确定递归函数的参数和返回值* @param root  树的根节点* @param result  将遍历的结果放在集合中*/private static void preorder(TreeNode root , List<Integer> result){//2、确定递归终止条件if (root == null){return;}//3、确定单层递归的逻辑：前序遍历：根左右result.add(root.val); //根preorder(root.left,result);//左preorder(root.right,result); //右}public static List<Integer> preorderTraversal(TreeNode root){ArrayList<Integer> result = new ArrayList<>();preorder(root,result);return result;}public static void main(String[] args) {TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));List<Integer> list = preorderTraversal(root);list.stream().forEach( e -> System.out.println(e+" "));}}

三、中序遍历

package com.thirteenday.tree;import java.util.ArrayList;
import java.util.List;//中序遍历
public class InorderTraversal {/*** 1、确定递归函数的参数和返回值* @param root  树的根节点* @param result  将遍历的结果放在集合中*/private static void preorder(TreeNode root , List<Integer> result){//2、确定递归终止条件if (root == null){return;}//3、确定单层递归的逻辑：中序遍历：左根右preorder(root.left,result);//左result.add(root.val); //根preorder(root.right,result); //右}public static List<Integer> inorderTraversal(TreeNode root){ArrayList<Integer> result = new ArrayList<>();preorder(root,result);return result;}public static void main(String[] args) {TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));List<Integer> list = inorderTraversal(root);list.stream().forEach( e -> System.out.println(e+" "));}
}

四、后序遍历

//后序遍历
public class PostorderTraversal {/*** 1、确定递归函数的参数和返回值* @param root  树的根节点* @param result  将遍历的结果放在集合中*/private static void preorder(TreeNode root , List<Integer> result){//2、确定递归终止条件if (root == null){return;}//3、确定单层递归的逻辑：后序遍历：左右根preorder(root.left,result);//左preorder(root.right,result); //右result.add(root.val); //根}public static List<Integer> postorderTraversal(TreeNode root){ArrayList<Integer> result = new ArrayList<>();preorder(root,result);return result;}public static void main(String[] args) {TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));List<Integer> list = postorderTraversal(root);list.stream().forEach( e -> System.out.println(e+" "));}
}