Java实现简单二叉树遍历

时间:2022-07-12 10:09:42

楔子

最近听了个词叫红黑树,看了下,发现真难。突然觉得自己好失败。难的不会,写个简单的吧。就随手写了个二叉树实现了下遍历功能,好像比以前只会复制粘贴的自己强了点,安慰下自己。

实现树

二叉树的组成部分就是节点和关联关系。Java里一个节点就是一个类,关联关系直接设计成属性,结果树和节点就成了一个类了。

public class StreeNode {
private String name;
private Integer value;

// 父节点
private StreeNode parentNode;

// 左孩子节点
private StreeNode leftNode;
// 右孩子节点
private StreeNode rightNode;

public StreeNode(String name, Integer value) {
super();
this.name = name;
this.value = value;
}
···
}

为了方便构造二叉树,增加一个简单的增加节点的方法,同时实现成有序的

    /**
* 增加一个节点并排序
*
* @param node
*/

public void appendChildNode(StreeNode node) {
if (node.value > this.value) {
setRightNode(node);
return;
}
setLeftNode(node);
}

private void setLeftNode(StreeNode leftNode) {
if (this.leftNode == null) {
leftNode.setParentNode(this);
this.leftNode = leftNode;
} else {
this.leftNode.appendChildNode(leftNode);
}
}

private void setRightNode(StreeNode rightNode) {
if (this.rightNode == null) {
rightNode.setParentNode(this);
this.rightNode = rightNode;
} else {
this.rightNode.appendChildNode(rightNode);
}
}

因为有parentNode属性,简单实现了通过树关系中任意节点获得root节点的方法。

    public StreeNode getRootNode() {
if (parentNode != null) {
return parentNode.getRootNode();
}
return this;
}

实现树遍历

概念就不赘述了


/**
* 中序遍历
*/

public void middleForEach() {
if (getLeftNode() != null) {
getLeftNode().middleForEach();
}
System.out.println(this);
if (getRightNode() != null) {
getRightNode().middleForEach();
}
}

/**
* 后序遍历
*/

public void lastForEach() {
if (getLeftNode() != null) {
getLeftNode().lastForEach();
}
if (getRightNode() != null) {
getRightNode().lastForEach();
}
System.out.println(this);
}

/**
* 先序遍历
*/

public void fristForEach() {
System.out.println(this);
if (getLeftNode() != null) {
getLeftNode().fristForEach();
}
if (getRightNode() != null) {
getRightNode().fristForEach();
}
}

总结:

由于二叉树结构设计时是自身包含同类型的对象实现关系,所以几个方法都是回调方法,类内实现。
三种遍历方法,在概念的理解上的差异在程序实现中却很小,代码差异很小。

附完整代码

public class StreeNode {
private String name;
private Integer value;

// 父节点
private StreeNode parentNode;

// 左孩子节点
private StreeNode leftNode;
// 右孩子节点
private StreeNode rightNode;

public StreeNode(String name, Integer value) {
super();
this.name = name;
this.value = value;
}

public StreeNode getParentNode() {
return parentNode;
}

public void setParentNode(StreeNode parentNode) {
this.parentNode = parentNode;
}

public StreeNode getLeftNode() {
return leftNode;
}

/**
* 增加一个节点并排序
*
* @param node
*/

public void appendChildNode(StreeNode node) {
if (node.value > this.value) {
setRightNode(node);
return;
}
setLeftNode(node);
}

private void setLeftNode(StreeNode leftNode) {
if (this.leftNode == null) {
leftNode.setParentNode(this);
this.leftNode = leftNode;
} else {
this.leftNode.appendChildNode(leftNode);
}
}

private void setRightNode(StreeNode rightNode) {
if (this.rightNode == null) {
rightNode.setParentNode(this);
this.rightNode = rightNode;
} else {
this.rightNode.appendChildNode(rightNode);
}
}

public StreeNode getRightNode() {
return rightNode;
}

public StreeNode getRootNode() {
if (parentNode != null) {
return parentNode.getRootNode();
}
return this;
}

/**
* 中序遍历
*/

public void middleForEach() {
if (getLeftNode() != null) {
getLeftNode().middleForEach();
}
System.out.println(this);
if (getRightNode() != null) {
getRightNode().middleForEach();
}
}

/**
* 后序遍历
*/

public void lastForEach() {
if (getLeftNode() != null) {
getLeftNode().lastForEach();
}
if (getRightNode() != null) {
getRightNode().lastForEach();
}
System.out.println(this);
}

/**
* 先序遍历
*/

public void fristForEach() {
System.out.println(this);
if (getLeftNode() != null) {
getLeftNode().fristForEach();
}
if (getRightNode() != null) {
getRightNode().fristForEach();
}
}

@Override
public String toString() {
return "StreeNode [name=" + name + ", value=" + value + ", parentNode=" + checkNullName(parentNode)
+ ", leftNode=" + checkNullName(leftNode) + ", rightNode=" + checkNullName(rightNode) + "]";
}

private String checkNullName(StreeNode node) {
return node == null ? "null" : node.name;
}
}

测试用例

    @Test
public void test() throws InterruptedException {
StreeNode node = new StreeNode("A", 50);

List<String> names = Arrays.asList("B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L");
List<Integer> valuses = Arrays.asList(85, 14, 63, 27, 37, 29, 71, 22, 4, 75, 76);

for (int i = 0; i < valuses.size(); i++) {
node.appendChildNode(new StreeNode(names.get(i), valuses.get(i)));
}

System.out.println("先");
node.fristForEach();

System.out.println("中");
node.middleForEach();

System.out.println("后");
node.lastForEach();

}

测试结果


StreeNode [name=A, value=50, parentNode=null, leftNode=C, rightNode=B]
StreeNode [name=C, value=14, parentNode=A, leftNode=J, rightNode=E]
StreeNode [name=J, value=4, parentNode=C, leftNode=null, rightNode=null]
StreeNode [name=E, value=27, parentNode=C, leftNode=I, rightNode=F]
StreeNode [name=I, value=22, parentNode=E, leftNode=null, rightNode=null]
StreeNode [name=F, value=37, parentNode=E, leftNode=G, rightNode=null]
StreeNode [name=G, value=29, parentNode=F, leftNode=null, rightNode=null]
StreeNode [name=B, value=85, parentNode=A, leftNode=D, rightNode=null]
StreeNode [name=D, value=63, parentNode=B, leftNode=null, rightNode=H]
StreeNode [name=H, value=71, parentNode=D, leftNode=null, rightNode=K]
StreeNode [name=K, value=75, parentNode=H, leftNode=null, rightNode=L]
StreeNode [name=L, value=76, parentNode=K, leftNode=null, rightNode=null]

StreeNode [name=J, value=4, parentNode=C, leftNode=null, rightNode=null]
StreeNode [name=C, value=14, parentNode=A, leftNode=J, rightNode=E]
StreeNode [name=I, value=22, parentNode=E, leftNode=null, rightNode=null]
StreeNode [name=E, value=27, parentNode=C, leftNode=I, rightNode=F]
StreeNode [name=G, value=29, parentNode=F, leftNode=null, rightNode=null]
StreeNode [name=F, value=37, parentNode=E, leftNode=G, rightNode=null]
StreeNode [name=A, value=50, parentNode=null, leftNode=C, rightNode=B]
StreeNode [name=D, value=63, parentNode=B, leftNode=null, rightNode=H]
StreeNode [name=H, value=71, parentNode=D, leftNode=null, rightNode=K]
StreeNode [name=K, value=75, parentNode=H, leftNode=null, rightNode=L]
StreeNode [name=L, value=76, parentNode=K, leftNode=null, rightNode=null]
StreeNode [name=B, value=85, parentNode=A, leftNode=D, rightNode=null]

StreeNode [name=J, value=4, parentNode=C, leftNode=null, rightNode=null]
StreeNode [name=I, value=22, parentNode=E, leftNode=null, rightNode=null]
StreeNode [name=G, value=29, parentNode=F, leftNode=null, rightNode=null]
StreeNode [name=F, value=37, parentNode=E, leftNode=G, rightNode=null]
StreeNode [name=E, value=27, parentNode=C, leftNode=I, rightNode=F]
StreeNode [name=C, value=14, parentNode=A, leftNode=J, rightNode=E]
StreeNode [name=L, value=76, parentNode=K, leftNode=null, rightNode=null]
StreeNode [name=K, value=75, parentNode=H, leftNode=null, rightNode=L]
StreeNode [name=H, value=71, parentNode=D, leftNode=null, rightNode=K]
StreeNode [name=D, value=63, parentNode=B, leftNode=null, rightNode=H]
StreeNode [name=B, value=85, parentNode=A, leftNode=D, rightNode=null]
StreeNode [name=A, value=50, parentNode=null, leftNode=C, rightNode=B]

最后,中序遍历的输出结果是有序的。