求二叉树的深度(二叉树,孩子,算法,编程语言)

对于二叉树的最大的深度，可以采用递归算法。
算法描述如下：
如果根结点为null，那么深度=0
如果根结点不是null，那么就看该当前结点的左孩子的深度和右孩子的深度
如果左孩子深度>=右孩子的深度，那么当前根结点的深度就是左孩子的深度+1.
反之则为右孩子的深度+1

对每个左孩子右孩子也是采用同样的算法。到某一节点是null的时候，才能返回0；

之前的文章有关于二叉树遍历的算法的描述。此处，对于遍历可以做一些小的改进，使它可以在遍历的时候计算出当前节点的深度。只要在递归方法中加入一个深度参数，每次调用的递归方法的时候，该参数都会自增1.则可以计算出深度。

假设构造出2棵树

字母树

数字树

采用算法计算深度，和遍历。

结果如下：

具体代码如下：

usingSystem; 
usingSystem.Collections.Generic; 
usingSystem.Linq; 
usingSystem.Text; 
namespacetree 
{ 
#region节点的定义 
classnode 
{ 
publicstringnodevalue; 
publicnodeleftchild,rightchild; 
publicnode() 
{} 
publicnode(stringvalue) 
{ 
nodevalue=value; 
} 
publicvoidassignchild(nodeleft,noderight)//设定左右孩子 
{ 
this.leftchild=left; 
this.rightchild=right; 
} 
publicboolhasleftchild//是否有左孩子 
{ 
get 
{ 
return(leftchild!=null); 
} 
} 
publicboolhasrightchild//是否有右孩子 
{ 
get 
{ 
return(rightchild!=null); 
} 
} 
publicboolhaschild//是否有右孩子 
{ 
get 
{ 
returnhasleftchild||hasrightchild; 
} 
} 
} 
#endregion 
classProgram 
{ 
staticvoidMain(string[]args) 
{ 
nodenode_a=newnode("a"); 
nodenode_b=newnode("b"); 
nodenode_c=newnode("c"); 
nodenode_d=newnode("d"); 
nodenode_e=newnode("e"); 
nodenode_f=newnode("f"); 
nodenode_g=newnode("g"); 
nodenode_h=newnode("h"); 
nodenode_i=newnode("i"); 
//构造一棵二叉树 
node_a.assignchild(node_b,node_c); 
node_b.assignchild(node_d,node_e); 
node_c.assignchild(node_f,node_g); 
node_e.assignchild(node_h,node_i); 
Console.WriteLine("maxDepth:"+maxDepth(node_a)); 
preorder_visit_depth(node_a,1); 
Console.WriteLine(); 
nodenode_1=newnode("1"); 
nodenode_2=newnode("2"); 
nodenode_3=newnode("3"); 
nodenode_4=newnode("4"); 
nodenode_5=newnode("5"); 
nodenode_6=newnode("6"); 
nodenode_7=newnode("7"); 
nodenode_8=newnode("8"); 
nodenode_9=newnode("9"); 
nodenode_10=newnode("10"); 
nodenode_11=newnode("11"); 
nodenode_12=newnode("12"); 
nodenode_13=newnode("13"); 
//构造一棵二叉树 
node_1.assignchild(node_2,node_3); 
node_2.assignchild(node_4,node_5); 
node_3.assignchild(null,node_7); 
node_5.assignchild(node_6,null); 
node_7.assignchild(node_8,null); 
node_8.assignchild(node_9,null); 
node_9.assignchild(node_10,node_11); 
node_10.assignchild(null,node_12); 
node_6.assignchild(null,node_13); 
Console.WriteLine("maxDepth:"+maxDepth(node_1)); 
preorder_visit_depth(node_1,1); 
Console.WriteLine(); 
} 
 
//计算深度 
staticintmaxDepth(noderoot) 
{ 
if(root==null) 
{ 
return0; 
} 
else 
{ 
intleftdepth=maxDepth(root.leftchild);//递归计算左孩子的深度 
intrightdepth=maxDepth(root.rightchild);//递归计算右孩子的深度 
if(leftdepth>=rightdepth) 
{ 
returnleftdepth+1; 
} 
else 
{ 
returnrightdepth+1; 
} 
} 
} 
 
//先序遍历//DLR 
staticvoidpreorder_visit_depth(nodeAnode,intdepth) 
{ 
Console.WriteLine(Anode.nodevalue+"-depth:"+depth); 
depth++;
if(Anode.hasleftchild) 
{ 
preorder_visit_depth(Anode.leftchild,depth); 
} 
if(Anode.hasrightchild) 
{ 
preorder_visit_depth(Anode.rightchild,depth); 
} 
} 
} 
}