package tree.bintree;

/**
 * 创建 非xx二叉树、xx二叉树、满二叉树
 *
 * 由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一
 * 次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除
 * 
 * @author jzj
 * @date 2009-12-23
 */
public class BinTree {// Bin=Binary(二进位的, 二元的)

 protected Entry root;//根
 private int size;//树的节点数

 /**
  * 树的节点结构
  * @author jzj
  * @date 2009-12-23
  */
 protected static class Entry {
  int elem;//数据域，这里我们作为编号
  Entry left;//左子树
  Entry right;//右子树

  public Entry(int elem) {
   this.elem = elem;
  }

  public String toString() {
   return " number=" + elem;
  }
 }

 /**
  * 根据给定的节点数创建一个xx二叉树或是满二叉树
  * @param nodeCount 要创建节点总数
  */
 public void createFullBiTree(int nodeCount) {
  root = recurCreateFullBiTree(1, nodeCount);
 }

 /**
  * 递归创建xx二叉树
  * @param num 节点编号
  * @param nodeCount 节点总数
  * @return TreeNode 返回创建的节点
  */
 private Entry recurCreateFullBiTree(int num, int nodeCount) {
  size++;
  Entry rootNode = new Entry(num);//根节点
  //如果有左子树则创建左子树
  if (num * 2 <= nodeCount) {
   rootNode.left = recurCreateFullBiTree(num * 2, nodeCount);
   //如果还可以创建右子树，则创建
   if (num * 2 + 1 <= nodeCount) {
    rootNode.right = recurCreateFullBiTree(num * 2 + 1, nodeCount);
   }
  }
  return (Entry) rootNode;
 }

 /**
  * 根据给定的数组创建一棵树，这个棵树可以是xx二叉树也可是普通二叉树
  * 数组中为0的表示不创建该位置上的节点
  * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
  */
 public void createBinTree(int[] nums) {
  root = recurCreateBinTree(nums, 0);
 }

 /**
  * 递归创建二叉树
  * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
  * @param index 需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建
  * @return TreeNode 返回创建的节点，最终会返回树的根节点
  */
 private Entry recurCreateBinTree(int[] nums, int index) {
  //指定索引上的编号不为零上才需创建节点
  if (nums[index] != 0) {
   size++;
   Entry rootNode = new Entry(nums[index]);//根节点
   //如果有左子树则创建左子树
   if ((index + 1) * 2 <= nums.length) {
    rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1);
    //如果还可以创建右子树，则创建
    if ((index + 1) * 2 + 1 <= nums.length) {
     rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2);
    }
   }
   return (Entry) rootNode;
  }
  return null;

 }

 public int size() {
  return size;
 }

 //取树的最左边的节点
 public int getLast() {
  Entry e = root;
  while (e.right != null) {
   e = e.right;
  }
  return e.elem;
 }

 //测试
 public static void main(String[] args) {

  //创建一个满二叉树
  BinTree binTree = new BinTree();
  binTree.createFullBiTree(15);
  System.out.println(binTree.size());//15
  System.out.println(binTree.getLast());//15

  //创建一个xx二叉树
  binTree = new BinTree();
  binTree.createFullBiTree(14);
  System.out.println(binTree.size());//14
  System.out.println(binTree.getLast());//7

  //创建一棵非xx二叉树
  binTree = new BinTree();
  int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
  binTree.createBinTree(nums);
  System.out.println(binTree.size());//8
  System.out.println(binTree.getLast());//8

 }
}