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; }}
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

 

package ch11;import java.util.List;import ch11.LinkBinTree.TreeNode;public class LinkBinTreeTest {    public static void main(String[] args){        LinkBinTree
     
       binTree = new LinkBinTree
      
       ("根节点");        TreeNode tn1= binTree.addNode(binTree.root(), "第二层左节点", true);        TreeNode tn2 = binTree.addNode(binTree.root(), "第二层右节点", false);        TreeNode tn3 = binTree.addNode(tn2,"第三层左节点", true);        TreeNode tn4 = binTree.addNode(tn2,"第三层右节点",false);        TreeNode tn5 = binTree.addNode(tn3, "第四层左节点", true);        System.out.println("根节点是哪个？"+binTree.root().data);        System.out.println("tn2的左子节点是： "+binTree.leftChild(tn2));        System.out.println("tn2的右子节点是： "+binTree.rightChild(tn2));        System.out.println(binTree.deep(binTree.root()));                /*List
       
         list = binTree.inIteratror();        for (int i = 0; i < list.size(); i++) {            System.out.println(list.get(i).data);        }*/        List
        
          list  = binTree.nonCursivePreIterator(binTree.root());        for (int i = 0; i < list.size(); i++) {            System.out.println(list.get(i).data);        }    }}