求二叉樹的深度

對于二叉樹的最大的深度，可以采用遞歸算法。
算法描述如下：
如果根結點為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);   
            }   
        }   
    }  
 
}