求二叉樹(shù)的深度

對(duì)于二叉樹(shù)的最大的深度，可以采用遞歸算法。
算法描述如下：
如果根結(jié)點(diǎn)為null，那么深度=0
如果根結(jié)點(diǎn)不是null，那么就看該當(dāng)前結(jié)點(diǎn)的左孩子的深度和右孩子的深度
如果左孩子深度>=右孩子的深度，那么當(dāng)前根結(jié)點(diǎn)的深度就是左孩子的深度+1.
反之則為右孩子的深度+1

對(duì)每個(gè)左孩子右孩子也是采用同樣的算法。到某一節(jié)點(diǎn)是null的時(shí)候，才能返回0；

之前的文章有關(guān)于二叉樹(shù)遍歷的算法的描述。此處，對(duì)于遍歷可以做一些小的改進(jìn)，使它可以在遍歷的時(shí)候計(jì)算出當(dāng)前節(jié)點(diǎn)的深度。只要在遞歸方法中加入一個(gè)深度參數(shù)，每次調(diào)用的遞歸方法的時(shí)候，該參數(shù)都會(huì)自增1.則可以計(jì)算出深度。

假設(shè)構(gòu)造出2棵樹(shù)

字母樹(shù)

數(shù)字樹(shù)

采用算法計(jì)算深度，和遍歷。

結(jié)果如下：

具體代碼如下：

using System;   
using System.Collections.Generic;   
using System.Linq;   
using System.Text;  
 
namespace tree   
{   
    #region 節(jié)點(diǎn)的定義   
    class node   
    {   
        public string nodevalue;   
        public node leftchild, rightchild;  
 
        public node()   
        { }   
        public node(string value)   
        {   
            nodevalue = value;   
        }  
 
        public void assignchild(node left, node right)//設(shè)定左右孩子   
        {   
            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");   
            //構(gòu)造一棵二叉樹(shù)   
            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");  
 
            //構(gòu)造一棵二叉樹(shù)   
            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();  
 
        }  
 
         
        //計(jì)算深度   
        static int maxDepth(node root)   
        {   
            if (root == null)   
            {   
                return 0;   
            }   
            else   
            {   
                int leftdepth = maxDepth(root.leftchild);//遞歸計(jì)算左孩子的深度   
                int rightdepth = maxDepth(root.rightchild);//遞歸計(jì)算右孩子的深度  
 
                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);   
            }   
        }   
    }  
 
}