统计二叉树叶子结点的数目

算法分析

统计叶子结点数目和输出叶子结点类似，不过是把输出换成累加。设计一个全局变量即可。

算法实现

TreeNode

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tree
{
    class TreeNode<T>
    {
        T data;
        TreeNode<T> LChrild;
        TreeNode<T> RChirld;
        
        public T Data { get => data; set => data = value; }
        internal TreeNode<T> LChrild1 { get => LChrild; set => LChrild = value; }
        internal TreeNode<T> RChirld1 { get => RChirld; set => RChirld = value; }

        public TreeNode(T data)
        {
            this.Data = data;
        }
    }
}

Program

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tree
{
    class Program
    {
        static int total = 0; //叶子结点数目

        static void Main(string[] args)
        {
            TreeNode<string> A = new TreeNode<string>("a");
            TreeNode<string> B = new TreeNode<string>("b");
            TreeNode<string> C = new TreeNode<string>("c");
            TreeNode<string> D = new TreeNode<string>("d");
            TreeNode<string> E = new TreeNode<string>("e");
            TreeNode<string> F = new TreeNode<string>("f");
            TreeNode<string> G = new TreeNode<string>("g");
            TreeNode<string> H = new TreeNode<string>("h");

            A.LChrild1 = B;
            B.RChirld1 = D;
            A.RChirld1 = C;
            D.LChrild1 = F;
            D.RChirld1 = G;
            C.RChirld1 = E;
            E.RChirld1 = H;

            Leef(A);
            Console.WriteLine(total);
        }

        /// <summary>
        /// 统计叶子结点数目，全局变量法
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        static void Leef(TreeNode<string> node)
        {
            if (node != null)
            {
                if (node.LChrild1 == null && node.RChirld1 == null)
                    ++total;
                Leef(node.LChrild1);
                Leef(node.RChirld1);
            }
        }
    }
}

思考

虽然用全局变量累加的方法统计叶子结点的数量实现起来很容易，不过这样做会加大程序间的耦合度。所以要换一种方法，最好是只需要调用一个函数就可以得到叶子结点数量，而函数所需要的条件都在函数内实现，从而加大其内聚度。
针对这个问题，可以换一种思路，统计叶子结点的数量，就是统计根节点左边的叶子结点数量和根节点右边的叶子结点数量。这样就会发现跟斐波那契题类似，斐波那契的解决思路是第i个数等于第i-1个数加上第i-2个数。
这样就把求树的叶子结点的大问题，分解成了求每个结点的左孩子的叶子节点数量和右孩子叶子结点数量的小问题。

实现

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tree
{
    class TreeNode<T>
    {
        T data;
        TreeNode<T> LChrild;
        TreeNode<T> RChirld;
        
        public T Data { get => data; set => data = value; }
        internal TreeNode<T> LChrild1 { get => LChrild; set => LChrild = value; }
        internal TreeNode<T> RChirld1 { get => RChirld; set => RChirld = value; }

        public TreeNode(T data)
        {
            this.Data = data;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tree
{
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode<string> A = new TreeNode<string>("a");
            TreeNode<string> B = new TreeNode<string>("b");
            TreeNode<string> C = new TreeNode<string>("c");
            TreeNode<string> D = new TreeNode<string>("d");
            TreeNode<string> E = new TreeNode<string>("e");
            TreeNode<string> F = new TreeNode<string>("f");
            TreeNode<string> G = new TreeNode<string>("g");
            TreeNode<string> H = new TreeNode<string>("h");

            A.LChrild1 = B;
            B.RChirld1 = D;
            A.RChirld1 = C;
            D.LChrild1 = F;
            D.RChirld1 = G;
            C.RChirld1 = E;
            E.RChirld1 = H;

            Console.WriteLine(Leef(A););
        }

        /// <summary>
        /// 统计叶子结点的数目
        /// /*采用递归算法，如果是空树，返回0；如果只有一个结点，返回1；否则为左右子树的叶子结点数之和*/
        /// </summary>
        /// <param name="node"></param>
        ///// <returns></returns>
        static int Leef(TreeNode<string> node)
        {
            //特殊情况
            if (node == null)
            {
                return 0;
            }
            //递归结束点
            else if (node.LChrild1 == null && node.RChirld1 == null)
            {
                return 1;
            }
            //递归过程
            else
            {
                return Leef(node.LChrild1) + Leef(node.RChirld1);
            }
        }
    }
}