Java简易二叉树排序

通过一个简单的二叉树例子,捋一捋思考的思路

比如需要对下列数组进行排序

int[] arr = {17, 12, 19, 10, 15, 18, 25, 8, 11, 13, 16, 22};

这里可以根据数组里的元素创建一个二叉树,要求就是父节点的值大于左子树节点的值,不大于右子树节点的值;当然父节点的值不小于左子树节点的值,小于右子树节点的值也行,最后再按中序遍历进行输出,也就是左中右,那么就能保证从小到大排序输出

具体二叉树如下

首先添加一个Node类,二叉树由很多个Node组成,Node类里定义三个成员变量,一个是值,这里是整型数字,还有分别指向左子树和右子树Node的引用,同时添加构造方法

package Love;

public class Node {
private int data;
private Node left;
private Node right;

public Node() {

}

public Node(int data) {
this.data = data;
}
}

然后添加一个BinaryTree类,一个根节点即可,构造方法不写也可以,不用传参

package Love;

public class BinaryTree {
private Node root;

public BinaryTree() {

}
}

考虑到需要将数组里所有整型元素添加到一个一个Node里,首先得添加Node,BinaryTree类里得实现addNode方法,先考虑第一个Node的情况,本来二叉树为空,root为null,在创建第一个Node保存data为17的时候,直接用root来引用,因此第一个分支,将data传进去创建一个Node,根root引用即可

package Love;

public class BinaryTree {
private Node root;

public BinaryTree() {

}

public void addNode(int data) {
if (root == null) {
root = new Node(data);
}
}
}

然后再来考虑root不为null的时候,比如这时根节点已经非null,那么创建第二个Node的时候,需要知道对应的data和17的大小关系,如果比17小,就放到left子树节点里,如果大于或者等于17,就放到right子树节点里,这段逻辑可以在Node类里添加一个add方法来实现,而在BinaryTree类里addNode方法只需要调用父节点的add方法,传入父节点的data值供add方法来判断

具体add的实现逻辑:

如果新来的data比root节点的data小,那么就需要在root的左边创建这个Node,如果此时left子树节点为空,那么就直接new一个left子树Node,值为data;如果此时left子树节点非空,那么就递归,root.left再次调用add方法,进行逻辑判断最终创建Node

如果新来的data比root节点的data不小于,那么就需要在root的右边创建这个Node,如果此时right子树节点为空,那么就直接new一个right子树Node,值为data;如果此时right子树节点非空,那么就递归,root.right再次调用add方法,进行逻辑判断最终创建Node

package Love;

public class Node {
private int data;
private Node left;
private Node right;

public Node() {

}

public Node(int data) {
this.data = data;
}

public void add(int data) {
if (this.data > data) {
if (this.left == null) {
this.left = new Node(data);
} else {
this.left.add(data);
}
} else {
if (this.right == null) {
this.right = new Node(data);
} else {
this.right.add(data);
}
}
}
}

这里完事之后,就再回到BinaryTree类里,完成addNode方法里的else,如果root非空,就需要添加字树节点,具体调用add方法来完成

package Love;

public class BinaryTree {
private Node root;

public BinaryTree() {

}

public void addNode(int data) {
if (root == null) {
root = new Node(data);
} else {
root.add(data);
}
}
}

到这里整个二叉树就创建完了,测试一下是否出现问题,main里调用一下二叉树的创建,编译运行不出错即可

package Love;

/**
* Hello world!
*/

public class App {

public static void main(String[] args) {
int[] arr = {17, 12, 19, 10, 15, 18, 25, 8, 11, 13, 16, 22};
BinaryTree bt = new BinaryTree();
for (int a : arr) {
bt.addNode(a);
}

}
}

再来考虑输出,BinaryTree类里添加一个printNode方法打印输出,如果root为null,也就是二叉树里啥都没有,那就不打印不管了,非null同样就直接调用Node的print方法

package Love;

public class BinaryTree {
private Node root;

public BinaryTree() {

}

public void addNode(int data) {
if (root == null) {
root = new Node(data);
} else {
root.add(data);
}
}

public void printNode() {
if (root != null) {
root.print();
}
}
}

再来实现Node类里的print方法,这里输出的方法是中序遍历,也就是先左子树,然后父节点,最后右子树

先左子树,如果为null,不管了;如果非null,说明左子树节点已经有了,但是有可能左子树节点并不是叶子节点,还有子树,因此这里直接递归,通过this.left作为父节点调用print方法进行递归

然后父节点,上面左边一堆输出完了之后,就直接输出当前this.data

最后右子树,如果为null,不管了;如果非null,说明右子树节点已经有了,但是有可能右子树节点并不是叶子节点,还有子树,因此这里直接递归,通过this.right为父节点调用print方法进行递归

这里的递归,比如图中;先找到17,调用print,发现有左子树12,调用print,发现有左子树10,调用print,发现有左子树8,调用print,这部分就是一直递归,条件就是this.left != null,而8是叶子节点,是此时的this,this.left = null,因此就打印8,this.right = null,退回到10作为this,左子树8这边输出完了,输出10,接着this.right != null,递归右边,11变成了this,当然这里11也是叶子节点,因此只打印一个11,假如此时11还有个左子树和右子树非null,又要将11作为this,先递归left,打印11,再递归right,如此循环

package Love;

public class Node {
private int data;
private Node left;
private Node right;

public Node() {

}

public Node(int data) {
this.data = data;
}

public void add(int data) {
if (this.data > data) {
if (this.left == null) {
this.left = new Node(data);
} else {
this.left.add(data);
}
} else {
if (this.right == null) {
this.right = new Node(data);
} else {
this.right.add(data);
}
}
}

public void print() {
if (this.left != null) {
this.left.print();
}
System.out.print(this.data + " ");
if (this.right != null) {
this.right.print();
}
}
}

最后再在main调用二叉树中序遍历的输出方法

package Love;

/**
* Hello world!
*/

public class App {

public static void main(String[] args) {
int[] arr = {17, 12, 19, 10, 15, 18, 25, 8, 11, 13, 16, 22};
BinaryTree bt = new BinaryTree();
for (int a : arr) {
bt.addNode(a);
}

bt.printNode();
}
}

输出结果正确无误

8 10 11 12 13 15 16 17 18 19 22 25

如果需要三种遍历方式,只需要修改Node类里的输出方法即可

public void preOrderPrint() {
System.out.print(this.data + " ");
if (this.left != null) {
this.left.preOrderPrint();
}
if (this.right != null) {
this.right.preOrderPrint();
}
}

public void inOrderPrint() {
if (this.left != null) {
this.left.inOrderPrint();
}
System.out.print(this.data + " ");
if (this.right != null) {
this.right.inOrderPrint();
}
}

public void postOrderPrint() {
if (this.left != null) {
this.left.preOrderPrint();
}
if (this.right != null) {
this.right.preOrderPrint();
}
System.out.print(this.data + " ");
}

输出结果和二叉树图一致

17 12 10 8 11 15 13 16 19 18 25 22
8 10 11 12 13 15 16 17 18 19 22 25
12 10 8 11 15 13 16 19 18 25 22 17

发表评论