《编程之美》-逐层遍历二叉树

时间：2010-09-05 来源：小伦

《编程之美》中有个关于逐层遍历二叉树的算法：

按照书中的算法思想实现如下：

首先定义数据结构：

代码

 /// <summary>
    /// 结点类
    /// </summary>
    /// <typeparam name="T">结点包含数据的数据类型</typeparam>
    public class Node<T>
    {
        private T _data;
        /// <summary>
        /// 结点数据
        /// </summary>
        public T Data
        {
            get { return _data; }
            set { _data = value; }
        }
        private Node<T> _right;
        /// <summary>
        /// 左孩子结点
        /// </summary>
        public Node<T> Right
        {
            get { return _right; }
            set { _right = value; }
        }
        private Node<T> _left;
        /// <summary>
        /// 右孩子结点
        /// </summary>
        public Node<T> Left
        {
            get { return _left; }
            set { _left = value; }
        }


        public Node(T data)
        {
            _data = data;
        }

        public Node(T data, Node<T> left, Node<T> right)
        {
            _data = data;
            _left = left;
            _right = right;
        }
    

    }

1.要逐层打印二叉树的结点，则可以先实现打印该二叉树某一层的算法：

代码

        //打印以root为根节点的二叉树的第level层的元素的
        void PrintNodeOfLevel(Node<int> root, int level)
        {
            if (root == null || level < 0)
                return;

            if (level == 0)
            {
                Console.Write(root.Data+"  ");
            }

            if (root.Left != null)
                PrintNodeOfLevel(root.Left, level - 1);

            if(root.Right != null)
                PrintNodeOfLevel(root.Right, level - 1);

        }

2.逐层打印需要知道二叉树的深度：

代码

//求二叉树深度
        int GetDepth(Node<int> root)
        {
            //分别求左右子树的深度，通过加1得到该树的深度，分而治之
            int ldepth=0, rdepth = 0;

            if (root == null)
                return 0;
            //求左子树的深度(均假设深度已求出)
            if (root.Left != null)
                ldepth = GetDepth(root.Left);

            //求右子树的深度(均假设深度已求出)
            if (root.Right != null)
                rdepth = GetDepth(root.Right);

            //关键之处，递归逻辑体(Math.max(ldepth,rdepth)替换之
            int temp = 0;
            if (ldepth >= rdepth)
                temp = ldepth;
            else
                temp = rdepth;
            return temp + 1;
            
        }

3.最后就是逐层打印该二叉树了：

代码

  void PrintBTree(Node<int> root)
        {
            int depth = GetDepth(root);
            for (int i = 0; i < depth; i++)
            {
                PrintNodeOfLevel(root, i);
                Console.Write("\n");
            }
        }

这是通过递归是比较耗时的做法，但是不需要额外的空间来计算，下面是通过空间换取时间的做法：

代码

  //逐层遍历二叉树，分开层
        static void PrintBTreeByBFS(Node<int> root)
        {
            List<Node<int>> list = new List<Node<int>>();
            list.Add(root);
            int current = 0;
            int next = 1;
            while (current < list.Count)//还有下层
            {
                next = list.Count;
                while (current < next)//该层还有元素
                {
                    Node<int> q = list[current];
                    Console.Write(q.Data + " ");

                    if (q.Left != null)//放入左孩子
                        list.Add(q.Left);

                    if (q.Right != null)//放入右孩子
                        list.Add(q.Right);

                    current++;
                }
                Console.Write("\n");
            }
        }

我还想起了逐层遍历二叉树的算法，但是没有不能按照书中的要求把层次分开：

代码

        //逐层遍历二叉树，但是没有分开层
        static void PrintBTreeByBFS(Node root)
        {
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                Node q = queue.Dequeue();
                Console.Write(q.Data + " ");

                if (q.Left != null)
                    queue.Enqueue(q.Left);
                if (q.Right != null)
                    queue.Enqueue(q.Right);
            }
        }

复习知识，欢迎拍砖！