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;
class Node {
public String data;
public Node left = null;
public Node right = null;
public boolean flag;
Node(String data) {
this.data = data;
}
Node() {
}
@Override
public 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;
}
// 记得加1
index++;
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);
}
}
// 树高 递归，分别求出左子树的深度、右子树的深度，两个深度的较大值+1
public 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);
}
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;
}
}以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。
