package cn.itcast.test;

import sun.reflect.generics.tree.Tree;

public class SearchBinaryTree {
    public static void main(String[] args) {
        SearchBinaryTree binaryTree = new SearchBinaryTree();
        int[] intArray = new int[]{50, 30, 20, 44, 88, 33, 87, 16, 7, 77};
        for (int i : intArray) {
            TreeNode put = binaryTree.put(i);
        }
        binaryTree.midOrder(binaryTree.root);
    }

    private TreeNode root;

    public SearchBinaryTree() {

    }

    public void midOrder(TreeNode node) {
        if (node == null) {
            return ;
        } else {
            midOrder(node.leftChild);
            System.out.println(node.data);
            midOrder(node.rightChild);
        }
    }

    /**
     * 创建查找二叉树，添加结点
     */
    public TreeNode put(int data) {
        TreeNode node = null;//定义一个结点
        TreeNode parent = null;//定义一个父节点
        node = new TreeNode(0, data);//创建一个结点
        if (root == null) {
            root = node;//创建根节点
            return node;
        }
        node = root;
        while (node != null) {//找左右结点，直到note=null，跳出循环
            parent = node;//先暂时把当前结点当做父节点
            if (data > node.data) {//data：根节点
                node = node.rightChild;
            } else if (data < node.data) {
                node = node.leftChild;
            } else {
                return node;
            }
        }

        //表示将此结点添加到相应位置
        node = new TreeNode(0, data);
        if (data < parent.data) {//传data值
            parent.leftChild = node;
            node.parent = parent;
        } else {
            parent.rightChild = node;
            node.parent = parent;
        }
        return node;
    }

    class TreeNode {
        private int key;
        private TreeNode leftChild;
        private TreeNode rightChild;
        private TreeNode parent;
        private int data;

        public TreeNode(int key, int data) {
            //调用父类的构造方法，即Object类的无参构造方法
            super();
            this.key = key;
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
            this.parent = null;
        }
        
        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public TreeNode getLeftChild() {
            return leftChild;
        }

        public void setLeftChild(TreeNode leftChild) {
            this.leftChild = leftChild;
        }

        public TreeNode getRightChild() {
            return rightChild;
        }

        public void setRightChild(TreeNode rightChild) {
            this.rightChild = rightChild;
        }

        public TreeNode getParent() {
            return parent;
        }

        public void setParent(TreeNode parent) {
            this.parent = parent;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }
    }
}