二叉树的特点是每个节点最多有两个分支，即二叉树中不存在度大于2的结点。
二叉树的遍历
- 先序遍历(根-左-右)
- 中序遍历(左-根-右)
- 后续遍历(左-右-根)
package com.lq.bintree;
import java.util.ArrayList;
import java.util.List;
public class BinTree {
private BinTree leftChild; //左孩子结点
private BinTree rightChild; //右孩子结点
private BinTree root; //根节点结点
private Object data; //数据域
private List<BinTree> datas;//存储所有的节点
public BinTree(BinTree leftChild, BinTree rightChild, Object data) {
super();
this.leftChild = leftChild;
this.rightChild = rightChild;
this.data = data;
}
public BinTree(Object data) {
this(null, null, data);
}
public BinTree() {
super();
}
public void createTree(Object[] objs){
datas=new ArrayList<BinTree>();
for (Object object : objs) {
datas.add(new BinTree(object));
}
root=datas.get(0);//将第一个作为根节点
for (int i = 0; i < objs.length/2; i++) {
datas.get(i).leftChild=datas.get(i*2+1);
if(i*2+2<datas.size()){//避免偶数的时候 下标越界
datas.get(i).rightChild=datas.get(i*2+2);
}
}
}
//先序遍历(递归)
public void preorder(BinTree root){
if(root!=null){
visit(root.getData());
preorder(root.leftChild);
preorder(root.rightChild);
}
}
//中序遍历(递归)
public void inorder(BinTree root){
if(root!=null){
inorder(root.leftChild);
visit(root.getData());
inorder(root.rightChild);
}
}
//后序遍历(递归)
public void afterorder(BinTree root){
if(root!=null){
afterorder(root.leftChild);
afterorder(root.rightChild);
visit(root.getData());
}
}
private void visit(Object obj) {
System.out.print(obj+" ");
}
public Object getData() {
return data;
}
public BinTree getRoot() {
return root;
}
}
测试
package com.lq.bintree;
public class TestTree {
public static void main(String[] args) {
BinTree binTree=new BinTree();
Object[] objs={0,1,2,3,4,5,6,7};
// Object[] objs={"a","b","c","d","e","f","g","h","i","j","k","l"};
binTree.createTree(objs);
binTree.preorder(binTree.getRoot()); //先序遍历
// binTree.inorder(binTree.getRoot()); //中序遍历
// binTree.afterorder(binTree.getRoot()); //后序遍历
}
}
先序遍历的结果为:0 1 3 7 4 2 5 6
中序遍历的结果为:7 3 1 4 0 5 2 6
后序遍历的结果为:7 3 4 1 5 6 2 0
