package ch11;import java.util.ArrayList;import java.util.List;import java.util.Stack;public class LinkBinTree 
      
       {    public static class TreeNode    {        Object data;        TreeNode left;        TreeNode right;        public TreeNode()        {                    }        public TreeNode(Object data)        {            this.data = data;            left = null;            right = null;        }        public TreeNode(Object data,TreeNode left,TreeNode right)        {            this.data = data;            this.left = left;            this.right = right;        }    }    private TreeNode root;    public LinkBinTree()    {        this.root = new TreeNode();    }    //以指定根元素创建二叉树    public LinkBinTree(T data)    {        this.root = new TreeNode(data);    }    //为指定节点添加子节点    public TreeNode addNode(TreeNode parent, T data,boolean isLeft)    {        if(parent == null)            throw new RuntimeException("节点为null，无法添加子节点");        if(isLeft && parent.left != null)            throw new RuntimeException(parent+"节点已经有左子节点，无法添加左子节点");        if(!isLeft && parent.right!=null)            throw new RuntimeException(parent+"节点已经有右子节点，无法添加右子节点");        TreeNode newNode = new TreeNode(data);        if(isLeft)            parent.left = newNode;        else            parent.right  = newNode;        return newNode;    }    //判空    public boolean empty()    {        return root.data ==null;    }    //返回固定节点的左子节点    public T leftChild(TreeNode parent)    {        if(parent ==null)            throw new RuntimeException("节点为Null，没有子节点");        return parent.left == null?null:(T)parent.left.data;    }    public T rightChild(TreeNode parent)    {        if(parent ==null)            throw new RuntimeException("节点为Null，没有子节点");        return parent.right == null?null:(T)parent.right.data;    }        public TreeNode root()    {        if(empty())            throw new RuntimeException("树为空，无法访问根节点");        return root;    }    public T parent(TreeNode node)    {        return null;    }    //递归，每棵子树的额深度为其所有子树的最大深度+1    public int deep(TreeNode node)    {        if(node == null)            return 0;        else{            int leftDeep = deep(node.left);            int rightDeep  = deep(node.right);            int max = leftDeep>rightDeep?leftDeep:rightDeep;            return max+1;        }    }        //先序遍历二叉树    public List
       
         preIterator()    {        return preIterator(root);    }    public List
        
          preIterator(TreeNode node)    {        List
         
           list = new ArrayList
          
           ();        //处理根节点        list.add(node);        if(node.left!=null)            list.addAll(preIterator(node.left));        if(node.right!=null)            list.addAll(preIterator(node.right));        return list;    }        //中序遍历    public List
           
             inIteratror() { return inIterator(root); } private List
            
              inIterator(TreeNode node) { List
             
               list = new ArrayList
              
               (); if(node.left!= null) list.addAll(inIterator(node.left)); list.add(node); if(node.right!=null) list.addAll(inIterator(node.right)); return list; } //非递归先序遍历二叉树 public List
               
                 nonCursivePreIterator(TreeNode node){ Stack
                
                 stack = new Stack
                 
                   (); List
                  
                    list = new ArrayList
                   
                    (); list.add(node); while(node!=null || !stack.empty()) { while(node!=null) { //System.out.println(node.data); list.add(node); stack.push(node); node=node.left; } if(!stack.empty()) { node = stack.pop(); node = node.right; } } return list; }}