链式存储的二叉树
二叉树数据结构创建二叉树二叉树的遍历先序遍历中序遍历后序遍历二叉树节点的查找先序查找中序查找后序查找删除二叉树的子树二叉树示例完整代码BinaryTree 类测试类 TestBinaryTree二叉树数据结构
// 二叉树类public class BinaryTree {// 根节点TreeNode root;// 设置根节点public void setRoot(TreeNode root) {this.root = root;}// 获取根节点public TreeNode getRoot() {return root;}}// 二叉树的节点类class TreeNode{// 权值int value;public TreeNode(int value){this.value = value;}// 左儿子TreeNode leftNode;// 右儿子TreeNode rightNode;// 设置左儿子public void setLeftNode(TreeNode leftNode) {this.leftNode = leftNode;}// 设置右儿子public void setRightNode(TreeNode rightNode) {this.rightNode = rightNode;}}
创建二叉树
我们将创建如下图的二叉树：
public static void main(String[] args) {// 创建一棵树，一开始为空树BinaryTree binTree = new BinaryTree();// 创建一个根节点TreeNode root = new TreeNode(1);// 给树设置节点binTree.setRoot(root);// 创建根的左儿子节点TreeNode rootL = new TreeNode(2);// 将新创建的节点设为根的左儿子root.setLeftNode(rootL);// 创建根的右儿子节点TreeNode rootR = new TreeNode(3);// 将新创建的节点设为根的右儿子root.setRightNode(rootR);// 为第二层的左节点创建两个子节点rootL.setLeftNode(new TreeNode(4));rootL.setRightNode(new TreeNode(5));// 为第二层的右节点创建两个子节点rootR.setLeftNode(new TreeNode(6));rootR.setRightNode(new TreeNode(7));}
二叉树的遍历
由上面的图可知，
先序遍历为：1 2 4 5 3 6 7
中序遍历为：4 2 5 1 6 3 7
后序遍历为：4 5 2 6 7 3 1
先序遍历
// 先序遍历，BinaryTree 对象的方法public void frontShow() {if (root != null){root.frontShow();}}-------------------------------------------------------------------------------------------// 先序遍历，TreeNode 对象的方法public void frontShow() {// 根System.out.print(value + " ");// 左节点if (leftNode != null)leftNode.frontShow();// 右节点if (rightNode != null)rightNode.frontShow();}
中序遍历
// 中序遍历，BinaryTree 对象的方法public void midShow() {if (root != null){root.midShow();}}-------------------------------------------------------------------------------------------// 中序遍历，TreeNode 对象的方法public void midShow(){// 左if (leftNode != null)leftNode.midShow();// 根System.out.print(value + " ");//右if (rightNode != null)rightNode.midShow();}
后序遍历
// 后序遍历，BinaryTree 对象的方法public void afterShow() {if (root != null){root.afterShow();}}-------------------------------------------------------------------------------------------// 后序遍历，TreeNode 对象的方法public void afterShow(){// 左if (leftNode != null)leftNode.afterShow();// 右if (rightNode != null)rightNode.afterShow();// 根System.out.print(value + " ");}
二叉树节点的查找
先序查找
// 先序查找，BinaryTree 对象的方法public TreeNode frontSearch(int i) {return root.frontSearch(i);}-------------------------------------------------------------------------------------------// 先序查找，TreeNode 对象的方法public TreeNode frontSearch(int i) {TreeNode target = null;if (this.value == i){return this;}if (leftNode != null){target = leftNode.frontSearch(i);}if (target != null){return target;}if (rightNode != null) {target = rightNode.frontSearch(i);}return target;}
中序查找
// 中序查找，BinaryTree 对象的方法public TreeNode midSearch(int i) {return root.midSearch(i);}-------------------------------------------------------------------------------------------// 中序查找，TreeNode 对象的方法public TreeNode midSearch(int i){TreeNode target = null;if (leftNode != null){target = leftNode.midSearch(i);}if (target != null){return target;}if (this.value == i){return this;}if (rightNode != null){target = rightNode.midSearch(i);}return target;}
后序查找
// 后序查找，BBinaryTree 对象的方法public TreeNode afterSearch(int i) {return root.afterSearch(i);}-------------------------------------------------------------------------------------------// 后序查找，TreeNode 对象的方法public TreeNode afterSearch(int i) {TreeNode target = null;if (leftNode != null){target = leftNode.afterSearch(i);}if (target != null){return target;}if (rightNode != null){target = rightNode.afterSearch(i);}if (target != null){return target;}if (this.value == i){return this;}return target;}
删除二叉树的子树
// 删除二叉树的子树，BinaryTree 对象的方法public void delete(int i) {if (root.value == i){root = null;return;}else{root.delete(i);}}-------------------------------------------------------------------------------------------// 删除二叉树的子树，TreeNode 对象的方法public void delete(int i) {TreeNode parent = this;// 判断左儿子if (parent.leftNode != null && parent.leftNode.value == i){parent.leftNode = null;return;}// 判断右儿子if (parent.rightNode != null && parent.rightNode.value == i){parent.rightNode = null;return;}// 递归检查并删除左儿子parent = leftNode;if (parent != null){parent.delete(i);}// 递归检查并删除右儿子parent = rightNode;if (parent != null){parent.delete(i);}}
二叉树示例完整代码
BinaryTree 类
package com.yusael.Tree2;public class BinaryTree {// 根节点TreeNode root;// 设置根节点public void setRoot(TreeNode root) {this.root = root;}// 获取根节点public TreeNode getRoot() {return root;}// 先序遍历public void frontShow() {if (root != null){root.frontShow();}}// 中序遍历public void midShow() {if (root != null){root.midShow();}}// 后序遍历public void afterShow() {if (root != null){root.afterShow();}}// 先序查找public TreeNode frontSearch(int i) {return root.frontSearch(i);}// 中序查找public TreeNode midSearch(int i) {return root.midSearch(i);}// 后序查找public TreeNode afterSearch(int i) {return root.afterSearch(i);}// 删除二叉树的子树public void delete(int i) {if (root.value == i){root = null;return;}else{root.delete(i);}}}// 二叉树的节点类class TreeNode{// 权值int value;public TreeNode(int value){this.value = value;}// 左儿子TreeNode leftNode;// 右儿子TreeNode rightNode;// 设置左儿子public void setLeftNode(TreeNode leftNode) {this.leftNode = leftNode;}// 设置右儿子public void setRightNode(TreeNode rightNode) {this.rightNode = rightNode;}// 先序遍历public void frontShow() {// 根System.out.print(value + " ");// 左节点if (leftNode != null)leftNode.frontShow();// 右节点if (rightNode != null)rightNode.frontShow();}// 中序遍历public void midShow(){// 左if (leftNode != null)leftNode.midShow();// 根System.out.print(value + " ");//右if (rightNode != null)rightNode.midShow();}// 后序遍历public void afterShow(){// 左if (leftNode != null)leftNode.afterShow();// 右if (rightNode != null)rightNode.afterShow();// 根System.out.print(value + " ");}// 先序查找public TreeNode frontSearch(int i) {TreeNode target = null;if (this.value == i){return this;}if (leftNode != null){target = leftNode.frontSearch(i);}if (target != null){return target;}if (rightNode != null) {target = rightNode.frontSearch(i);}return target;}// 中序查找public TreeNode midSearch(int i){TreeNode target = null;if (leftNode != null){target = leftNode.midSearch(i);}if (target != null){return target;}if (this.value == i){return this;}if (rightNode != null){target = rightNode.midSearch(i);}return target;}// 后序查找public TreeNode afterSearch(int i) {TreeNode target = null;if (leftNode != null){target = leftNode.afterSearch(i);}if (target != null){return target;}if (rightNode != null){target = rightNode.afterSearch(i);}if (target != null){return target;}if (this.value == i){return this;}return target;}// 删除二叉树的子树public void delete(int i) {TreeNode parent = this;// 判断左儿子if (parent.leftNode != null && parent.leftNode.value == i){parent.leftNode = null;return;}// 判断右儿子if (parent.rightNode != null && parent.rightNode.value == i){parent.rightNode = null;return;}// 递归检查并删除左儿子parent = leftNode;if (parent != null){parent.delete(i);}// 递归检查并删除右儿子parent = rightNode;if (parent != null){parent.delete(i);}}}
测试类 TestBinaryTree
public class TestBinaryTree {public static void main(String[] args) {// 创建一颗树BinaryTree binTree = new BinaryTree();// 创建一个根节点TreeNode root = new TreeNode(1);// 把根结点赋给树binTree.setRoot(root);// 创建根的左儿子节点TreeNode rootL = new TreeNode(2);// 将新创建的节点设为根结点的左儿子root.setLeftNode(rootL);// 创建根的右儿子节点TreeNode rootR = new TreeNode(3);// 将新创建的节点设为根结点的右儿子root.setRightNode(rootR);// 为第二层的左节点创建两个子节点rootL.setLeftNode(new TreeNode(4));rootL.setRightNode(new TreeNode(5));// 为第二层的右节点创建两个子节点rootR.setLeftNode(new TreeNode(6));rootR.setRightNode(new TreeNode(7));System.out.println("**************以上为创建二叉树*************");// 先序遍历System.out.print("先序遍历:");binTree.frontShow();System.out.println();// 中序遍历System.out.print("中序遍历:");binTree.midShow();System.out.println();// 后序遍历System.out.print("后序遍历:");binTree.afterShow();System.out.println();System.out.println("*************以上为二叉树的遍历**************");// 先序查找TreeNode treeNode1 = binTree.frontSearch(3);System.out.println(treeNode1 == rootR);// 中序查找TreeNode treeNode2 = binTree.midSearch(5);System.out.println(treeNode2);// 后序查找TreeNode treeNode3 = binTree.afterSearch(8);System.out.println(treeNode3);System.out.println("**************以上为二叉树的查找*************");// 删除一个子树binTree.delete(5);System.out.println("删除一个子树后的先序遍历：");binTree.frontShow();System.out.println();System.out.println("**************以上为删除二叉树的子树*************");}}
**************以上为创建二叉树*************先序遍历:1 2 4 5 3 6 7 中序遍历:4 2 5 1 6 3 7 后序遍历:4 5 2 6 7 3 1 *************以上为二叉树的遍历**************truecom.yusael.Tree.TreeNode@1b6d3586null**************以上为二叉树的查找*************删除一个子树后的先序遍历：1 2 4 3 6 7 **************以上为删除二叉树的子树*************
