文章中主要用java实现完全二叉树的创建以及二叉树的递归遍历算法
。
重点在于完全二叉树的创建
,递归算法比较容易些。
完全二叉树的创建
创建之前首先要了解完全二叉树的一些性质
。
性质
:如果有一颗有n个节点的完全二叉树的节点按层次序编号,对任一层的节点i(0<=i<=n)有(注意i的取值)
1.如果i=0,则节点是二叉树的根,无双亲,如果i>0,则其双亲节点为[i/2],向下取整
2.如果2i+1>n那么节点i没有左孩子,否则其左孩子为2i+1
3.如果2i+2>n那么节点没有右孩子,否则右孩子为2i+2
结点创建
//单独一个类创建结点
public class BTNode {
//定义一个二叉树的结点
private int data;
private BTNode lchild;
private BTNode rchild;
//主要是为了构造函数的初始
public BTNode(){
}
//新的构造函数,其实也可以简写
public BTNode(int data ,BTNode lchild ,BTNode rchild){
this.data=data;
this.lchild=lchild;
this.rchild=rchild;
}
//以下就是data lchild rchild的set,get函数
public void setdata(int data){
this.data=data;
}
public int getdata(){
return data;
}
public void setlchild(BTNode lchild ){
this.lchild=lchild;
}
public BTNode getlchild(){
return this.lchild;
}
public void setrchild(BTNode rchild ){
this.rchild=rchild;
}
public BTNode getrchild(){
return this.rchild;
}
完全二叉树的创建
//List和ArrayList的区别?
public static List<BTNode> list=new ArrayList<BTNode>();
//由数组建树的方法
public void creatTree(int[] array){
for(int i=0;i<array.length;i++){
BTNode btnode =new BTNode(array[i],null,null);
list.add(btnode);
}
//首先在list的长度 大于1的情况下进行
if(list.size()>0){
//for循环比较巧妙,注意for循环的次数,i代表的是每一个带有孩子的结点,0代表的是根节点
for(int i=0;i<array.length/2;i++){
if(2*i+1<list.size())//这里不能等于,原因是list的长度必须大于2*i+1不然会数组越界
list.get(i).setlchild(list.get(2 * i + 1));
if(2*i+2<list.size())// 这里也不能等于,原因是数组会越界
list.get(i).setrchild(list.get(2 * i + 2));
}
}
}
访问操作
//访问数组的操作,这里仅仅是 打印的操作,也可以输出
public static void visit(BTNode btnode){
if(btnode!=null)
System.out.print(btnode.getdata() + " ,");
}
递归遍历
//先序遍历的递归操作
public static void preorder(BTNode btnode) {
if(btnode!=null){
visit(btnode);
preorder(btnode.getlchild());
preorder(btnode.getrchild());
}
}
//中序遍历的递归操作
public static void inorder(BTNode btnode){
if(btnode!=null){
inorder(btnode.getlchild());
visit(btnode);
inorder(btnode.getrchild());
}
}
//后序遍历的递归操作
public static void afterorder(BTNode btnode){
if(btnode!=null){
afterorder(btnode.getlchild());
afterorder(btnode.getrchild());
visit(btnode);
}
}
测试代码
public static void main(String[] args) {
int[] array = { 0,1, 2, 3, 4, 5, 6, 7, 8,9,10,11,12};
BuildTree demo = new BuildTree();
demo.creatTree(array);
System.out.print("二叉树的先序排序为:");
preorder(list.get(0));
System.out.println();
System.out.print("二叉树的中序排序为:");
inorder(list.get(0));
System.out.println();
System.out.print("二叉树的后序排序为:");
afterorder(list.get(0));
}
总结
各种方法的创建我都已经码在上面,测试结果我重新跑了遍也都正确。
本文创建二叉树的核心思想就是:先将数据存在一个树结点中,并将树结点放在arraylist数组里。由于完全二叉树的性质,我们可以对arraylist数组中的结点进行操作,也就是分出其左右结点。