【数据结构】-java实现- 完全二叉树的创建以及递归遍历算法实现_java创建完全二叉树

文章中主要用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;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

完全二叉树的创建

//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));
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

访问操作

//访问数组的操作，这里仅仅是 打印的操作，也可以输出
	public static void visit(BTNode btnode){
		if(btnode!=null)
			System.out.print(btnode.getdata() + " ,");
	}

1
2
3
4
5
6

递归遍历

//先序遍历的递归操作
  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);
  	}
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

测试代码

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));
 }
1
2
3
4
5
6
7
8
9
10
11
12
13

总结

各种方法的创建我都已经码在上面，测试结果我重新跑了遍也都正确。
本文创建二叉树的核心思想就是：先将数据存在一个树结点中，并将树结点放在arraylist数组里。由于完全二叉树的性质，我们可以对arraylist数组中的结点进行操作，也就是分出其左右结点。