package com.hb.binaryTree;

class BinaryTreeNode {
 int data;

 BinaryTreeNode left;

 BinaryTreeNode right;

 public BinaryTreeNode(int data) {
  this.data = data;
  this.left = null;
  this.right = null;
 }
}

public class BinaryTree {

 private BinaryTreeNode root;

 public BinaryTree() {
  this.root = null;
 }

 public void insertIntoTree(int data) {

  BinaryTreeNode newNode = new BinaryTreeNode(data);

  if (root == null) {
   root = newNode;
  } else {
   BinaryTreeNode currentNode = root;
   BinaryTreeNode parentNode = root;
   while (currentNode != null) {
    if (data < currentNode.data) {
     parentNode = currentNode;
     currentNode = currentNode.left;
     if (currentNode == null) {
      parentNode.left = newNode;
     }
    } else if (data > currentNode.data) {
     parentNode = currentNode;
     currentNode = currentNode.right;
     if (currentNode == null) {
      parentNode.right = newNode;
     }
    }
   }
  }
 }

 public boolean isEmpty() {
  return root == null;
 }

 public BinaryTreeNode search(int data) {  
  return BinaryTreeSearch(root, data);
 }

 public BinaryTreeNode BinaryTreeSearch(BinaryTreeNode node, int data) {
  if (node == null)
   return null;
  if (data == node.data) {
   return node;
  } else if (data < node.data) {
   return BinaryTreeSearch(node.left, data);
  } else {
   return BinaryTreeSearch(node.right, data);
  }
 }
 
 public void preOrderTraverse(BinaryTreeNode root){
  if(root!=null){
   System.out.print(root.data+", ");
   preOrderTraverse(root.left);
   preOrderTraverse(root.right);
  }
 }
 
 public void inOrderTraverse(BinaryTreeNode root){
  if(root!=null){
   inOrderTraverse(root.left);
   System.out.print(root.data+", ");
   inOrderTraverse(root.right);
  }
 }
 
 public void postOrderTraverse(BinaryTreeNode root){
  if(root!=null){
   postOrderTraverse(root.left);
   postOrderTraverse(root.right);
   System.out.print(root.data+", ");
  }
 }
 
 public int getMaxValue(BinaryTreeNode root){
  while(root.right!=null){
   root = root.right;
  }
  return root.data;  
 }
 
 public int getMinValue(BinaryTreeNode root){
  while(root.left!=null){
   root = root.left;
  }
  return root.data;
 }
 
 public static void main(String[] args){
  BinaryTree binaryTree = new BinaryTree();
  binaryTree.insertIntoTree(12);
  binaryTree.insertIntoTree(1);
  binaryTree.insertIntoTree(2);
  binaryTree.insertIntoTree(45);
  binaryTree.insertIntoTree(24);
  binaryTree.insertIntoTree(68);
  binaryTree.insertIntoTree(89);
  binaryTree.insertIntoTree(23);
  
  System.out.println("中根遍历");
  binaryTree.inOrderTraverse(binaryTree.root);
  System.out.println("\n先根遍历");
  binaryTree.preOrderTraverse(binaryTree.root);
  System.out.println("\n后根遍历");
  binaryTree.postOrderTraverse(binaryTree.root);
  
  BinaryTreeNode node = binaryTree.search(89);
  System.out.println(node.data);
  
  System.out.println("最大数值："+binaryTree.getMaxValue(binaryTree.root));
  System.out.println("最小数值："+binaryTree.getMinValue(binaryTree.root));
 }
}