二叉树的结构
*/ public class TreeNode { // 左孩子 private TreeNode leftNode; // 右孩子 private TreeNode rightNode; // 存储值 private Object value; // 构造方法 TreeNode(Object value){ this.value = value; } // 省略 set get } ``` 现在需要实现以下的一颗满二叉树; ![](https://ww1.yunjiexi.club/2020/03/28/mu47V.png) 思路如下: 首先根节点储存1;然后分别储存 左孩子2,右孩子3; 其次左孩子节点作为父节点,然后分别储存 左孩子4,右孩子5; 最后右孩子节点作为父节点然后分别储存 左孩子6,右孩子7; 代码实现如下: ``` public static void main(String[] args) { // 初始化树 TreeNode tree = initTree(); } public static TreeNode initTree(){ // 创建7个节点 TreeNode treeNode1 = new TreeNode(1); TreeNode treeNode2 = new TreeNode(2); TreeNode treeNode3 = new TreeNode(3); TreeNode treeNode4 = new TreeNode(4); TreeNode treeNode5 = new TreeNode(5); TreeNode treeNode6 = new TreeNode(6); TreeNode treeNode7 = new TreeNode(7); // 根据上面思路对节点进行组装 // 组装根节点 treeNode1.setLeftNode(treeNode2); treeNode1.setRightNode(treeNode3); // 组装左孩子 treeNode2.setLeftNode(treeNode4); treeNode2.setRightNode(treeNode5); // 组装右孩子 treeNode3.setLeftNode(treeNode6); treeNode3.setRightNode(treeNode7); return treeNode1; } ``` ## 3.2 二叉树的遍历与实现 二叉树的遍历分为前序遍历,中序遍历,后续遍历;假设 当前节点 为C (Current Node), 左节点为L ,右节点为R; > 前序遍历:C----->L------->R > > 中序遍历:L----->C------->R > > 后续遍历:R----->C------>L **先序遍历的实现** 思路 : - 首先访问当前节点; - 其次访问左节点; - 最后访问后节点; 回到 前图 前序遍历CLR就是 1,2,4,5,3,6,7; ``` public static void main(String[] args) { // 初始化树 TreeNode tree = initTree(); // 调用先序遍历 preOrderTree(tree); } /* * * @Author lsc *先序遍历
* @Param [rootNode] * @Return void */ public static void preOrderTree(TreeNode rootNode){ if (rootNode!=null){ // 值 System.out.println(rootNode.getValue()); // 左孩子 preOrderTree(rootNode.getLeftNode()); // 右孩子 preOrderTree(rootNode.getRightNode()); } } ``` 输出 ``` 1 2 4 5 3 6 7 ``` 先序遍历实现为线性实现,时间复杂度为O(n) **中序遍历的实现** 思路 : - 首先访问左节点 - 其次访问当前节点 - 最后访问右节点 回到 前图中序遍历的结果是 4,2,5,1, 6,3,7 ``` public static void main(String[] args) { // 初始化树 TreeNode tree = initTree(); // 调用中序遍历 middleOrderTree(tree); } /* * * @Author lsc *中序遍历
* @Param [rootNode] * @Return void */ public static void middleOrderTree(TreeNode rootNode){ if (rootNode!=null){ // 左孩子 middleOrderTree(rootNode.getLeftNode()); // 值 System.out.println(rootNode.getValue()); // 右孩子 middleOrderTree(rootNode.getRightNode()); } } ``` 输出 ``` 4 2 5 1 6 3 7 ``` 中序遍历实现为线性实现,时间复杂度为O(n) **后续遍历的实现** 思路: - 首先访问左节点 - 其次访问右节点 - 最后访问当前节点 回到 前图中序遍历的结果是 4,5,2,6, 7,3,1 ``` public static void main(String[] args) { // 初始化树 TreeNode tree = initTree(); // 调用后续遍历 postOrderTree(tree); } /* * * @Author lsc *后续遍历
* @Param [rootNode] * @Return void */ public static void postOrderTree(TreeNode rootNode){ if (rootNode!=null){ // 左孩子 postOrderTree(rootNode.getLeftNode()); // 右孩子 postOrderTree(rootNode.getRightNode()); // 值 System.out.println(rootNode.getValue()); } } ``` 输出 ``` 4 5 2 6 7 3 1 ``` 后序遍历实现为线性实现,时间复杂度为O(n)