2019独角兽企业重金招聘Python工程师标准>>>

/**
* @title:   二叉树遍历,求深度
* @author : Jay Chang
* @version : ver 1.0
* @date : 2009.7.25
*/
import java.util.Scanner;

/*二叉树的结点的定义*/
class BiTreeNode
{
private String nodeName;
private int    value;
/*没有解决好lChild,rChild两个属性的封装，存在些问题，不知道为什么,有待改进*/
public BiTreeNode lChild;   
public BiTreeNode rChild;

public BiTreeNode(){}

/*创建结点对象的构造器*/
public BiTreeNode(String nodeName,int value)
{
     this.nodeName=nodeName;
     this.value=value;
    this.lChild=null;
    this.rChild=null;
}

/*setName,getName,setValue,getValue,是对结点两个属性的封装 */
public void setName(String nodeName)
{
      this.nodeName=nodeName;
}

public String getName()
{
    return nodeName;
}

public void setValue(int value)
{
     this.value=value;
}

public int getValue()
{
    return this.value;
}

}

/*二叉树类定义*/
class BiTree
{
private BiTreeNode root;

public BiTree(){}

public BiTreeNode getRoot()
{
   return this.root;
}

public void create()
{
this.root=createBiTree(this.root);
}
/*递归创建二叉树*/
private BiTreeNode createBiTree(BiTreeNode node)
{
     String name;int value;
      Scanner sc=new Scanner(System.in);
    System.out.println("输入结点名称及值:");
    name=sc.next();value=sc.nextInt();
    if(name!="#"&&value!=-1){
        node =new BiTreeNode(name,value);
        node.lChild=createBiTree(node.lChild);     //node.lChild和node.rChild本应使用封装，但是不能用?
        node.rChild=createBiTree(node.rChild);
        return node;
      }else{
        return null;
      }
}

/*求二叉树的高度*/
public int getDepth(BiTreeNode node)
{
    int lDepth,rDepth;
    if(node==null){
    return 0;
    }
    lDepth=getDepth(node.lChild);
    rDepth=getDepth(node.rChild);
    return (lDepth>rDepth?lDepth:rDepth)+1;
}

   /*先序遍历二叉树*/
public void fTraverse(BiTreeNode node)
{
     if(node!=null){
         System.out.println("Node Name:"+node.getName()+" Node Value:"+node.getValue());
         fTraverse(node.lChild);
         fTraverse(node.rChild);
      }else{
         return;
      }
}

/*中序遍历二叉树*/
public void mTraverse(BiTreeNode node)
{
     if(node!=null){
      mTraverse(node.lChild);
          System.out.println("Node Name:"+node.getName()+" Node Value:"+node.getValue());
      mTraverse(node.rChild);
    }else{
        return;
     }
}

/*后序遍历二叉树*/
public void lTraverse(BiTreeNode node)
{
   if(node!=null){
          lTraverse(node.lChild);
       lTraverse(node.rChild);
           System.out.println("Node Name:"+node.getName()+" Node Value:"+node.getValue());
      }else{
       return;
    }
}

}

 

public class TestBiTree
{
   public static void main(String[] args)
   {
     BiTree biTree=new BiTree();
     biTree.create();
     System.out.println("先序遍历:");
     biTree.fTraverse(biTree.getRoot());
     System.out.println("中序遍历:");
     biTree.mTraverse(biTree.getRoot());
     System.out.println("后序遍历:");
     biTree.lTraverse(biTree.getRoot());
     System.out.println("二叉树的高度:");
     System.out.println(biTree.getDepth(biTree.getRoot()));
   }

}

转载于:https://my.oschina.net/u/1167421/blog/546499