java二叉树的深度理解

[来源] 达内    [编辑] 达内   [时间]2012-09-17

但是,我写个小例子来跟踪,就觉得,其实递归算法很复杂,要是规模大的话,我估计效率不高,我自己面对问题,解决问题的时候,几乎很难想到递归算法,想到了,我也写不出来。

   我感觉我对递归算法不是的那么敏感。我每次在读算法的时候,我都是喜欢用一个简单的小实例,一步一步的看,看是否执行的对。递归算法对我来说,看别人的递归算法,有的时候看着很简单,但是,我写个小例子来跟踪,就觉得,其实递归算法很复杂,要是规模大的话,我估计效率不高,我自己面对问题,解决问题的时候,几乎很难想到递归算法,想到了,我也写不出来。

       下面是是实现二叉树的递归算法的实现,其思想就是,若为空,则其深度为0,否则,其深度等于左子树和右子树的深度的最大值加1:

class Node{
 String name;
 Node left;
 Node right;
 public Node(String name) {
  this.name = name;
 }
 @Override
 public String toString() {
  return name;
 }
}
//定义二叉树
class BinaryTree{
 Node root;
 
 public BinaryTree(){
  root = null;
 }
 //为了方便起见,我就直接写个初始化的二叉树,详细的可以见以前的日志
 public void initTree(){
  
  Node node1 = new Node("a");
  Node node2 = new Node("b");
  Node node3 = new Node("c");
  Node node4 = new Node("d");
  Node node5 = new Node("e");
  root = node1;
  node1.left = node2;
  node2.right = node3;
  node1.right = node4;
  node3.left = node5;
 }
 //求二叉树的深度
 int length(Node root){
  int depth1;
  int depth2;
  if(root == null) return 0;
  //左子树的深度
  depth1 = length(root.right);
  //右子树的深度
  depth2 = length(root.left);
  if(depth1>depth2)
   return depth1+1;
  else
   return depth2+1;
 }
}
public class TestMatch{

 public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();
  tree.initTree();
  System.out.println(tree.length(tree.root));
 }
}

资源下载