package org.bintree;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 以数组方式实现二叉树
 * 
 * @author Administrator
 * 
 */
public class BiTree {

	public static void main(String[] args) {
		int Data; // 读取输入值的临时变量
		int Index = 1;//数组下标变量
		System.out.println("请输入二叉树数据元素(输入0退出!):");
		Scanner console = new Scanner(System.in);
		do {
			System.out.print("Data" + Index + ":");
			Data = console.nextInt();
			BiTreeArray.Create(Data);
			Index++;
		} while (Data != 0);
		BiTreeArray.printAll();//输入二叉树的节点值
	}

	static class BiTreeArray {
		static final int MaxSize = 16;
		static int[] ABiTree = new int[MaxSize];

		public BiTreeArray() {
			Arrays.fill(ABiTree, 0);
		}

		/**
		 * 创建一棵二叉树，核心部分
		 * @param Data
		 */
		public static void Create(int Data) {
			int level = 1;// 树的层数,从层1开始建立
			while (ABiTree[level] != 0)// 判断是否存在子树
			{
				if (Data < ABiTree[level])// 判断是左子树还是右子树
					level = level * 2;// 左子树
				else
					level = level * 2 + 1;// 右子树
			}
			ABiTree[level] = Data;// 将元素值插入节点
		}

		/**
		 * 输出二叉树所有的节点
		 */
		public static void printAll() {
			System.out.println("二叉树节点值依次为:");
			for (int i = 0; i < MaxSize; i++) {
				System.out.println("Node" + i + ":[" + ABiTree[i] + "}");
			}
		}
	}
}