java如何创建普通二叉树

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() {
	}
	@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);
	}

	/**
	 * 为什么不直接写成调用 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;
	}
}

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。