就不做多余的讲解相关的原理的,直接上代码,代码中有相关的注释,代码也比较简单容易看懂)
结点的代码:
public class TreeNode {
/**
* 左孩子
*/
private TreeNode leftChildren;
/**
* 数据域
*/
private Integer data;
/**
* 右孩子
*/
private TreeNode rightChildren;
public TreeNode() {
}
public TreeNode(TreeNode leftChildren, Integer data, TreeNode rightChildren) {
this.leftChildren = leftChildren;
this.data = data;
this.rightChildren = rightChildren;
}
public TreeNode getLeftChildren() {
return leftChildren;
}
public void setLeftChildren(TreeNode leftChildren) {
this.leftChildren = leftChildren;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public TreeNode getRightChildren() {
return rightChildren;
}
public void setRightChildren(TreeNode rightChildren) {
this.rightChildren = rightChildren;
}
}
实现三种排序的代码,都是可以直接使用的.
public class SortBTree {
public static void main(String[] args) {
/**
* 初始化二叉树
* 1
* 2 3
* 4 5 6 7
*/
TreeNode node7 = new TreeNode(null, 7, null);
TreeNode node6 = new TreeNode(null, 6, null);
TreeNode node5 = new TreeNode(null, 5, null);
TreeNode node4 = new TreeNode(null, 4, null);
TreeNode node3 = new TreeNode(node6, 3, node7);
TreeNode node2 = new TreeNode(node4, 2, node5);
TreeNode node1 = new TreeNode(node2, 1, node3);
System.out.println("先序遍历: ");
preOrder(node1);
System.out.println();
System.out.println("中序遍历: ");
middleOrder(node1);
System.out.println();
System.out.println("后序遍历: ");
lastOrder(node1);
}
/**
* 先序遍历: 根结点->左孩子->右孩子 ==>扩展到整个二叉树是: 根结点->左子树->右子树
* 1
* 2 3
* 先序就是: 1->2->3 看懂顺序了吧
*
* @param node 根结点
*/
public static void preOrder(TreeNode node) {
//最先访问根结点
System.out.print(node.getData() + " ");
if (!Objects.isNull(node.getLeftChildren())) {
preOrder(node.getLeftChildren());
} else {
if (!Objects.isNull(node.getRightChildren())) {
preOrder(node.getRightChildren());
} else {
return;
}
}
if (!Objects.isNull(node.getRightChildren())) {
preOrder(node.getRightChildren());
} else {
return;
}
}
/**
* 中序遍历: 左孩子->根结点->右孩子 ==>扩展到整个二叉树是: 左子树->根结点->右子树
* 1
* 2 3
* 中序就是: 2->1->3 看懂顺序了吧
*
* @param node 根结点
*/
public static void middleOrder(TreeNode node) {
if (!Objects.isNull(node.getLeftChildren())) {
middleOrder(node.getLeftChildren());
} else {
if (!Objects.isNull(node.getRightChildren())) {
middleOrder(node.getRightChildren());
} else {
System.out.print(node.getData() + " ");
return;
}
}
//左子树遍历完之后访问根结点
System.out.print(node.getData() + " ");
if (!Objects.isNull(node.getRightChildren())) {
middleOrder(node.getRightChildren());
} else {
System.out.print(node.getData() + " ");
return;
}
}
/**
* 后序遍历: 左孩子->右孩子->根结点 ==>扩展到整个二叉树是: 左子树->右子树->根结点
* 1
* 2 3
* 中序就是: 2->3->1 看懂顺序了吧
*
* @param node 根结点
*/
public static void lastOrder(TreeNode node) {
if (!Objects.isNull(node.getLeftChildren())) {
lastOrder(node.getLeftChildren());
} else {
System.out.print(node.getData() + " ");
if (!Objects.isNull(node.getRightChildren())) {
lastOrder(node.getRightChildren());
} else {
return;
}
}
if (!Objects.isNull(node.getRightChildren())) {
lastOrder(node.getRightChildren());
} else {
return;
}
//左子树->右子树访问完后->根结点
System.out.print(node.getData() + " ");
}
}
输出结果
先序遍历:
1 2 4 5 3 6 7
中序遍历:
4 2 5 1 6 3 7
后序遍历:
4 5 2 6 7 3 1
这些是方便大家理解的.下面精简一下
public class SortBTree {
public static void main(String[] args) {
/**
* 初始化二叉树
* 1
* 2 3
* 4 5 6 7
*/
TreeNode node7 = new TreeNode(null, 7, null);
TreeNode node6 = new TreeNode(null, 6, null);
TreeNode node5 = new TreeNode(null, 5, null);
TreeNode node4 = new TreeNode(null, 4, null);
TreeNode node3 = new TreeNode(node6, 3, node7);
TreeNode node2 = new TreeNode(node4, 2, node5);
TreeNode node1 = new TreeNode(node2, 1, node3);
System.out.println("先序遍历: ");
preOrder(node1);
System.out.println();
System.out.println("中序遍历: ");
middleOrder(node1);
System.out.println();
System.out.println("后序遍历: ");
lastOrder(node1);
preOrder(null);
}
/**
* 先序遍历: 根结点->左孩子->右孩子 ==>扩展到整个二叉树是: 根结点->左子树->右子树
* 1
* 2 3
* 先序就是: 1->2->3 看懂顺序了吧
*
* @param node 根结点
*/
public static void preOrder(TreeNode node) {
if (Objects.isNull(node)) {
return;
}
System.out.print(node.getData()+" ");
preOrder(node.getLeftChildren());
preOrder(node.getRightChildren());
}
/**
* 中序遍历: 左孩子->根结点->右孩子 ==>扩展到整个二叉树是: 左子树->根结点->右子树
* 1
* 2 3
* 中序就是: 2->1->3 看懂顺序了吧
*
* @param node 根结点
*/
public static void middleOrder(TreeNode node) {
if (Objects.isNull(node)) {
return;
}
middleOrder(node.getLeftChildren());
System.out.print(node.getData()+" ");
middleOrder(node.getRightChildren());
}
/**
* 后序遍历: 左孩子->右孩子->根结点 ==>扩展到整个二叉树是: 左子树->右子树->根结点
* 1
* 2 3
* 中序就是: 2->3->1 看懂顺序了吧
*
* @param node 根结点
*/
public static void lastOrder(TreeNode node) {
if (Objects.isNull(node)) {
return;
}
lastOrder(node.getLeftChildren());
lastOrder(node.getRightChildren());
System.out.print(node.getData()+" ");
}
}
结果当然是相同的.
网友评论