求二叉树的深度

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

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

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

 

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

 

假设构造出2棵树

字母树

数字树

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

结果如下：

具体代码如下：

 

using System;   
using System.Collections.Generic;   
using System.Linq;   
using System.Text;  
 
namespace tree   
{  
    #region 节点的定义  
    class node   
    {   
        public string nodevalue;   
        public node leftchild, rightchild;  
 
        public node()   
        { }   
        public node(string value)   
        {   
            nodevalue = value;   
        }  
 
        public void assignchild(node left, node right)//设定左右孩子  
        {   
            this.leftchild = left;   
            this.rightchild = right;   
        }  
 
        public bool hasleftchild//是否有左孩子  
        {   
            get   
            {   
                return (leftchild != null);   
            }   
        }  
 
        public bool hasrightchild//是否有右孩子  
        {   
            get   
            {   
                return (rightchild != null);   
            }   
        }  
 
        public bool haschild//是否有右孩子  
        {   
            get   
            {   
                return hasleftchild || hasrightchild;   
            }   
        }   
    }  
    #endregion  
    class Program   
    {   
        static void Main(string[] args)   
        {   
            node node_a = new node("a");   
            node node_b = new node("b");   
            node node_c = new node("c");   
            node node_d = new node("d");   
            node node_e = new node("e");   
            node node_f = new node("f");   
            node node_g = new node("g");   
            node node_h = new node("h");   
            node node_i = new node("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();  
 
            node node_1 = new node("1");   
            node node_2 = new node("2");   
            node node_3 = new node("3");   
            node node_4 = new node("4");   
            node node_5 = new node("5");   
            node node_6 = new node("6");   
            node node_7 = new node("7");   
            node node_8 = new node("8");   
            node node_9 = new node("9");   
            node node_10 = new node("10");   
            node node_11 = new node("11");   
            node node_12 = new node("12");   
            node node_13 = new node("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();  
 
        }  
 
         
        //计算深度  
        static int maxDepth(node root)   
        {   
            if (root == null)   
            {   
                return 0;   
            }   
            else   
            {   
                int leftdepth = maxDepth(root.leftchild);//递归计算左孩子的深度  
                int rightdepth = maxDepth(root.rightchild);//递归计算右孩子的深度 
 
                if (leftdepth >= rightdepth)   
                {   
                    return leftdepth + 1;   
                }   
                else   
                {   
                    return rightdepth + 1;   
                }   
            }   
        }  
 
   
 
        //先序遍历 //DLR  
        static void preorder_visit_depth(node Anode,int depth)   
        {   
            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);   
            }   
        }   
    }  
 
}   

 

当前名称：求二叉树的深度
分享URL：http://bjjierui.cn/article/jecohh.html