二叉树的定义
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。(copy百度百科)
前序
先根节点再左节点最后右节点
中序
先左节点再根节点最后右节点
后序
先左节点后右最后根节点
可能这些定义大家都比较熟悉,但是了解起来还是比较麻烦。那么直接上代码:
package BinaryTree;
import java.util.LinkedList;
import java.util.List;
/**
* author micky.wang
* 创建二叉树并且使用先序,中序,后序显示出来。
*/
public class ConstructingBinaryTree {
private int[] array = {1,2,3,4,5,6,7,8,9,10};
private static List<Node> nodeList = null;
private static class Node{
Node leftChild;
Node rightChild;
int data;
Node (int newdata) {
leftChild = null;
rightChild = null;
data = newdata;
}
}
public void createBinTree() {
nodeList = new LinkedList<Node>();
for (int i =0;i<array.length;i++) {
nodeList.add(new Node(array[i]));
}
for (int j = 0; j<array.length / 2 - 1; j++) {
// 左孩子
nodeList.get(j).leftChild = nodeList.get(j * 2 + 1);
// 右孩子
nodeList.get(j).rightChild = nodeList.get(j * 2 + 2);
}
int lastboy = array.length / 2 - 1;
nodeList.get(lastboy).leftChild = nodeList.get(lastboy * 2 + 1);
if (array.length % 2 ==1) {
nodeList.get(lastboy).rightChild = nodeList.get(lastboy * 2 + 2);
}
}
// 先序 先跟再左后右
public void preording(Node node) {
if (node == null) {
return;
}
System.out.print(node.data);
preording(node.leftChild);
preording(node.rightChild);
}
// 中序 先左再跟最后右
public void middleOrder(Node node) {
if (node == null) {
return;
}
middleOrder(node.leftChild);
System.out.print(node.data);
middleOrder(node.rightChild);
}
// 后序 先左再右后中
public void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.print(node.data);
}
public static void main(String args[]) {
ConstructingBinaryTree constructingBinaryTree = new ConstructingBinaryTree();
constructingBinaryTree.createBinTree();
Node root = nodeList.get(0);
System.out.println("先序;");
constructingBinaryTree.preording(root);
System.out.println("中序;");
constructingBinaryTree.middleOrder(root);
System.out.println("后序;");
constructingBinaryTree.postOrder(root);
}
}
希望大家可以一起进步。
网友评论