java如何创建普通二叉树

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 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.http://left);

printPreOderByRecursion(node.right);

}

public void printPreOderByRecursion() {

printPreOderByRecursion(root);

}

private void printInOderByRecursion(Node node) {

if (http://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 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 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);

tempNohttp://de = tempNode.right;

}

}

// 后序遍历

public void printPostOder() {

Stack 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 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 queue = new LinkedList<>();

Queue 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,sUUNehqCex#,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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。