对于二叉树的最大的深度,可以采用递归算法。
算法描述如下:
如果根结点为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); } } } }