绵阳梓潼网站制作公司

求二叉树的深度

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

在东光等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都网站设计、做网站 网站设计制作按需策划设计,公司网站建设,企业网站建设,高端网站设计,成都营销网站建设,成都外贸网站建设,东光网站建设费用合理。

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

 

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

 

假设构造出2棵树

求二叉树的深度

字母树

求二叉树的深度

数字树

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

结果如下：

求二叉树的深度

具体代码如下：

 

  1. using System;   
  2. using System.Collections.Generic;   
  3. using System.Linq;   
  4. using System.Text;  
  5.  
  6. namespace tree   
  7. {  
  8.     #region 节点的定义  
  9.     class node   
  10.     {   
  11.         public string nodevalue;   
  12.         public node leftchild, rightchild;  
  13.  
  14.         public node()   
  15.         { }   
  16.         public node(string value)   
  17.         {   
  18.             nodevalue = value;   
  19.         }  
  20.  
  21.         public void assignchild(node left, node right)//设定左右孩子  
  22.         {   
  23.             this.leftchild = left;   
  24.             this.rightchild = right;   
  25.         }  
  26.  
  27.         public bool hasleftchild//是否有左孩子  
  28.         {   
  29.             get   
  30.             {   
  31.                 return (leftchild != null);   
  32.             }   
  33.         }  
  34.  
  35.         public bool hasrightchild//是否有右孩子  
  36.         {   
  37.             get   
  38.             {   
  39.                 return (rightchild != null);   
  40.             }   
  41.         }  
  42.  
  43.         public bool haschild//是否有右孩子  
  44.         {   
  45.             get   
  46.             {   
  47.                 return hasleftchild || hasrightchild;   
  48.             }   
  49.         }   
  50.     }  
  51.     #endregion  
  52.     class Program   
  53.     {   
  54.         static void Main(string[] args)   
  55.         {   
  56.             node node_a = new node("a");   
  57.             node node_b = new node("b");   
  58.             node node_c = new node("c");   
  59.             node node_d = new node("d");   
  60.             node node_e = new node("e");   
  61.             node node_f = new node("f");   
  62.             node node_g = new node("g");   
  63.             node node_h = new node("h");   
  64.             node node_i = new node("i");   
  65.             //构造一棵二叉树  
  66.             node_a.assignchild(node_b, node_c);   
  67.             node_b.assignchild(node_d, node_e);   
  68.             node_c.assignchild(node_f, node_g);   
  69.             node_e.assignchild(node_h, node_i);  
  70.  
  71.             Console.WriteLine("maxDepth:" + maxDepth(node_a));   
  72.             preorder_visit_depth(node_a, 1);   
  73.             Console.WriteLine();  
  74.  
  75.             node node_1 = new node("1");   
  76.             node node_2 = new node("2");   
  77.             node node_3 = new node("3");   
  78.             node node_4 = new node("4");   
  79.             node node_5 = new node("5");   
  80.             node node_6 = new node("6");   
  81.             node node_7 = new node("7");   
  82.             node node_8 = new node("8");   
  83.             node node_9 = new node("9");   
  84.             node node_10 = new node("10");   
  85.             node node_11 = new node("11");   
  86.             node node_12 = new node("12");   
  87.             node node_13 = new node("13");  
  88.  
  89.             //构造一棵二叉树  
  90.             node_1.assignchild(node_2, node_3);   
  91.             node_2.assignchild(node_4, node_5);   
  92.             node_3.assignchild(null, node_7);   
  93.             node_5.assignchild(node_6, null);   
  94.             node_7.assignchild(node_8, null);   
  95.             node_8.assignchild(node_9, null);   
  96.             node_9.assignchild(node_10, node_11);   
  97.             node_10.assignchild(null, node_12);   
  98.             node_6.assignchild(null, node_13);  
  99.  
  100.  
  101.             Console.WriteLine("maxDepth:"+maxDepth(node_1));   
  102.             preorder_visit_depth(node_1, 1);   
  103.             Console.WriteLine();  
  104.  
  105.         }  
  106.  
  107.          
  108.         //计算深度  
  109.         static int maxDepth(node root)   
  110.         {   
  111.             if (root == null)   
  112.             {   
  113.                 return 0;   
  114.             }   
  115.             else   
  116.             {   
  117.                 int leftdepth = maxDepth(root.leftchild);//递归计算左孩子的深度  
  118.                 int rightdepth = maxDepth(root.rightchild);//递归计算右孩子的深度 
  119.  
  120.                 if (leftdepth >= rightdepth)   
  121.                 {   
  122.                     return leftdepth + 1;   
  123.                 }   
  124.                 else   
  125.                 {   
  126.                     return rightdepth + 1;   
  127.                 }   
  128.             }   
  129.         }  
  130.  
  131.    
  132.  
  133.         //先序遍历 //DLR  
  134.         static void preorder_visit_depth(node Anode,int depth)   
  135.         {   
  136.             Console.WriteLine(Anode.nodevalue + "-depth:" + depth);   
  137.             depth++; 
  138.             if (Anode.hasleftchild)   
  139.             {   
  140.                 preorder_visit_depth(Anode.leftchild, depth);   
  141.             }  
  142.  
  143.             if (Anode.hasrightchild)   
  144.             {   
  145.                 preorder_visit_depth(Anode.rightchild, depth);   
  146.             }   
  147.         }   
  148.     }  
  149.  
  150. }   

 


名称栏目：求二叉树的深度
文章分享：http://myzitong.com/article/jecohh.html

其他资讯