java创建二叉树
这段时间一直在复习数据结构的知识。
从最基础的开始，实现一个普通的二叉树。但发现也不那么简单。因为之前学数据结构时是用C语言写的。
指针用来对结构体的值操作比较好理解。但java没有指针。
而Node节点在方法中传递的是地址。
如果直接对形参进行new操作是错误的。无法改变实参的值的。这一点坑了我很久，然后一顿查资料。
时隔很久，终于填上这个坑了
下面是以递归创建的二叉树.还有一些常见的遍历和树的高度与树的最大宽度.
一个方法不能修改一个基本数据类型的参数 一个方法可以修改一个对象参数的状态 一个方法不能实现让对象参数引用一个新对象（这句话在这里尤为适用）代码中的二叉树如下图
下面是非常简单的实现
这里为了，后面的输出格式，使用了JDK的动态代理。并写了一个接口
package test.tree; public interface AbstractBinaryTree { void printPostOder(); void printPostOderByRecursion(); void printPreOder(); void printPreOderByRecursion(); void printInOderByRecursion(); void printInOder(); void printHeight(); void printMaxWidth(); void printLevelOrder();}
主要的代码
package test.tree; import java.util.LinkedList;import java.util.Queue;import java.util.Stack; /** * 为了方便展示,并没有将Node属性私有 */ class Node { public String data;public Node left = null;public Node right = null;public boolean flag; Node(String data) {this.data = data;} Node() {} @Overridepublic String toString() { return this.data;} } public class BinaryTree implements AbstractBinaryTree{ private Node root = new Node(); public Node getRoot() {return root;} public void printNode(Node node) { if (node.data == null) {System.out.print("");} else {System.out.print(node.data);}} public BinaryTree(String tree) {String[] treeNodes = tree.split(",");createTreeByRecursion(treeNodes);} private int createTreeByRecursion(Node node, String[] treeNodes, int n) { if ("#".equals(treeNodes[n]))return n + 1; node.data = treeNodes[n]; node.left = new Node();int left = createTreeByRecursion(node.left, treeNodes, n + 1); node.right = new Node();int right = createTreeByRecursion(node.right, treeNodes, left); return right;} public void createTreeByRecursion(String[] treeNodes) {createTreeByRecursion(root, treeNodes, 0);} /** * 先序非递归创建 */public void createTree(String[] treeNodes) { Stack<Node> stack = new Stack<>(); int index = 0; Node node = root; while (index < treeNodes.length) { while (true) { if ("#".equals(treeNodes[index])) { node = stack.pop(); if (node.flag == false) {node.left = null;node.flag = true;stack.push(node);} else {node.right = null;} // 记得加1index++;break;} if (node.flag == true) {node.right = new Node();node = node.right;} node.data = treeNodes[index];stack.push(node);node.left = new Node();node = node.left;index++;} if (node.flag == false) {stack.push(node);node.flag = true;node = node.right;} else {node = stack.peek();node.flag = true;} } } // 递归调用的方法,需要将root传递进去private void printPreOderByRecursion(Node node) { if (node == null)return; printNode(node);printPreOderByRecursion(node.left);printPreOderByRecursion(node.right); } public void printPreOderByRecursion() { printPreOderByRecursion(root);} private void printInOderByRecursion(Node node) { if (node == null)return; printInOderByRecursion(node.left);printNode(node);printInOderByRecursion(node.right); } public void printInOderByRecursion() {printInOderByRecursion(root);} private void printPostOderByRecursion(Node node) { if (node == null)return; printPostOderByRecursion(node.left);printPostOderByRecursion(node.right);printNode(node); } public void printPostOderByRecursion() { printPostOderByRecursion(root);} // 非递归遍历二叉树 // 先序遍历public void printPreOder() { Stack<Node> stack = new Stack<>(); Node tempNode = root; while (true) { while (tempNode != null) {printNode(tempNode);stack.push(tempNode);tempNode = tempNode.left;} if (stack.isEmpty()) {break;} tempNode = stack.pop();tempNode = tempNode.right; } } // 中序遍历public void printInOder() { Stack<Node> stack = new Stack<>(); Node tempNode = root; while (true) { while (tempNode != null) {stack.push(tempNode);tempNode = tempNode.left;} if (stack.isEmpty()) {break;}tempNode = stack.pop();printNode(tempNode);tempNode = tempNode.right; } } // 后序遍历public void printPostOder() { Stack<Node> stack = new Stack<>(); Node tempNode = root; while (true) { while (tempNode != null) {if (tempNode.flag == true) {tempNode = tempNode.right;} else {stack.push(tempNode);tempNode = tempNode.left;} } tempNode = stack.pop(); if (tempNode.flag == false) {stack.push(tempNode);tempNode.flag = true;tempNode = tempNode.right;} else {printNode(tempNode);if (stack.isEmpty()) {break;}tempNode = stack.peek();tempNode.flag = true;} } } // 层序遍历 利用队列public void printLevelOrder() { Queue<Node> queue = new LinkedList<>(); Node tempNode = root; queue.offer(tempNode); while (!queue.isEmpty()) { Node topNode = queue.poll(); if (topNode == null)continue; printNode(topNode);queue.offer(topNode.left);queue.offer(topNode.right); } } // 树高 递归，分别求出左子树的深度、右子树的深度，两个深度的较大值+1public int getHeightByRecursion(Node node) { if (node == null) {return 0;}int left = getHeightByRecursion(node.left);int right = getHeightByRecursion(node.right);return 1 + Math.max(left, right); } /** * 为什么不直接写成调用 root,而是另写一个方法去调用呢 因为,这样可以不再为root,单独设置一个临时变量去存贮 * 而且也固定外部调用的方法,而不用关心内部的实现 */ public void printHeight() { int height = getHeightByRecursion(root); System.out.print(height);} // 利用层序遍历,得到树的最大宽度public void printMaxWidth() { Queue<Node> queue = new LinkedList<>();Queue<Node> queueTemp = new LinkedList<>(); int maxWidth = 1; Node tempNode = root; queue.offer(tempNode); while (!queue.isEmpty()) { while (!queue.isEmpty()) { Node topNode = queue.poll(); if (topNode == null)continue; if (topNode.left.data != null) { queueTemp.offer(topNode.left);} if (topNode.right.data != null) { queueTemp.offer(topNode.right);} } maxWidth = Math.max(maxWidth, queueTemp.size());queue = queueTemp;queueTemp = new LinkedList<>();} System.out.print(maxWidth);} }
下面是写的测试类
package test.tree; import java.lang.reflect.Proxy; public class BinaryTreeTest { public static void main(String[] args) {String treeStr = "A,B,D,#,#,#,C,#,E,#,#";// String treeStr = "A,#,#";AbstractBinaryTree binaryTree = BinaryTreeTest.proxyBinaryTree(treeStr); binaryTree.printPostOder();binaryTree.printPostOderByRecursion();binaryTree.printPreOder();binaryTree.printPreOderByRecursion();binaryTree.printInOderByRecursion();binaryTree.printInOder();binaryTree.printLevelOrder();binaryTree.printHeight();binaryTree.printMaxWidth();} public static AbstractBinaryTree proxyBinaryTree(String treeStr) {AbstractBinaryTree binaryTree = new BinaryTree(treeStr); Object newProxyInstance = Proxy.newProxyInstance(binaryTree.getClass().getClassLoader(),binaryTree.getClass().getInterfaces(), (proxy, method, args) -> {System.out.println(method.getName());Object invoke = method.invoke(binaryTree, args);System.out.println();return invoke;});return (AbstractBinaryTree) newProxyInstance;} }
以上为个人经验，希望能给大家一个参考，也希望大家多多支持。
生活若剥去了理想梦想幻想，那生命便只是一堆空架子
