package data.structure;

import java.util.Stack;
/**
   * 二叉树
   * 排序二叉树：若它的左子树不为空，则左子树上所有节点值都小于根节点的值
                             若它的右子树不为空，则右子树上所有节点值都大于根节点的值
                             左子树和右子树都一颗排序
   * 平衡二叉树：具备排序二叉树的特性
                             所有节点的左子树和右子树的高度差不超过1
   * 红黑树：红黑树是一种非完美平衡的自平衡二叉树，它的时间复杂度为O(longn)红黑树的特征如下
                    所有节点都有颜色，要么是红色，要么是黑色
                    根节点是黑色的
                    所有叶子节点（NIL）都是黑色的空节点
                    红色节点的子节点必须是黑色的
                    任何一个节点到它的叶子节点包含相同的黑色节点
 * B树(二叉搜索树)：
 * AVL树：
 * 
 * @author 72060564
 *
 */

public class BinaryTreeTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
         BinaryTree head=new BinaryTree(12);  
         
         insert(head,16);
         insert(head,8);         
         insert(head,17);
         insert(head,15);              
         insert(head,9);
         insert(head,6);
       
         inOrder(head); 
//         preOrderTraverse(head);
    }
    
    public static void insert(BinaryTree root,int data){
         if(data>root.data){ //如果插入的节点大于跟节点
             if(root.right==null){          //如果右子树为空，就插入，如果不为空就再创建一个节点                                                         
             root.right=new BinaryTree(data); //就把插入的节点放在右边
             }else{
                insert(root.right, data);
             }
         }else{  //如果插入的节点小于根节点
             if(root.left==null){ //如果左子树为空，就插入，如果不为空就再创建一个节点           
                 root.left=new BinaryTree(data); //就把插入的节点放在左边边
             }else{
                insert(root.left, data);
             }
         }
     }
    //先跟遍历 非递归
    public static void preOrderTraverse(BinaryTree root) {
        System.out.println();
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree node = root;
        while (node != null || !stack.empty()) {
            if (node != null) {
//             先跟   System.out.print(node.data + "->");
                stack.push(node);
                node = node.left;
            } else {
                BinaryTree tem = stack.pop();
//            中跟     System.out.print(tem.val + "->");
                node = tem.right;
            }
        }
    }

    //先跟遍历 访问顺序：先根节点，再左子树，最后右子树；
    public static void preOrder(BinaryTree root) { 
        if (root != null) {
            System.out.print(root.data + "-");
            preOrder(root.left);
            preOrder(root.right);
        }   
    }
    // 中跟遍历 访问顺序：先左子树，再根节点，最后右子树；
    public static void inOrder(BinaryTree root) { // 中根遍历
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.data + "--");
            inOrder(root.right);
        }
    }
 // 后跟遍历 访问顺序：先左子树，再右子树，最后根节点 
    public static void postOrder(BinaryTree root) { // 后根遍历
 
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.data + "---");
        }
    }
    //后跟遍历 非递归
    public void postOrderTraverse(BinaryTree root) {
        BinaryTree cur, pre = null;
        Stack<BinaryTree> stack = new Stack<>();
        stack.push(root);

        while (!stack.empty()) {
            cur = stack.peek();
            if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) {
                System.out.print(cur.data + "->");
                stack.pop();
                pre = cur;
            } else {
                if (cur.right != null)
                    stack.push(cur.right);
                if (cur.left != null)
                    stack.push(cur.left);
            }
        }
    }


}