二叉树的深度优先遍历和广度优先遍历

小灰灰 2022-01-31 14:04 305阅读 0赞

二叉树结构简单，存储效率高，算法简单，每个结点至多有两个子树，两个子树有左右之分，次序不能颠倒。

二叉树的存储结构分为：顺序存储结构和链式存储结构。

1.顺序存储结构

把一棵满二叉树自上而下，从左到右顺序编号，把编号依次存放在数组中，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2huem1kbGhj_size_16_color_FFFFFF_t_70][]

设满二叉树结点在数组中索引号为i，那么有如下性质：

（1）如果i=0，此结点无双亲，为根结点

（2）如果i>0,其双亲结点为（i-1)/2 ,这里为整除，保留整数位

（3）结点为i 的左孩子为2i+1，右孩子为2i+2

（4）如果i>0,当i为奇数时，它是双亲结点的左孩子，兄弟为i+1；当i为偶数时，它是双亲结点的右孩子，兄弟结点为i-1

（5）深度为k的满二叉树需要长度为2^k -1 的数组进行存储。

2.链式存储

当k值很大时，又有很多空结点的时候，使用顺序存储结构来存储，会造成极大的浪费，这时应使用链式存储结构来存储

![20190516202944424.png][]

3.二叉树遍历

树遍历的本质是将非线性结构线性化

二叉树的深度优先遍历，分为如下三种：（先左后右）

1.先序遍历，访问根结点，先序遍历左子树，先序遍历右子树，上图遍历结果为：0134256

2.中序遍历，中序遍历左子树，访问根结点，中序遍历右子树，遍历结果为：3140526

3.后序遍历，后序遍历左子树，后续遍历右子树，访问根结点，遍历结果：3415620

代码实现：

结点类：

class Node
        {
            //数据
            private object _data;
            //左孩子
            private Node _left;
            //右孩子
            private Node _right;
            public object Data
            {
                get
                {
                    return _data;
                }
            }
            public Node Left
            {
                get { return _left; }
                set { _left = value; }
            }
            public Node Right
            {
                get { return _right; }
                set { _right = value; }
            }
    
            public Node(object data)
            {
                _data = data;
            }
            public override string ToString()
            {
                return _data.ToString();
            }
    
        }

二叉树集合类：

//头指针
            private Node _head;
            //构造二叉树的字符串
            private string _Str;
            public Node Head
            {
                get
                {
                    return _head;
                }
            }
            public OurTree(string str)
            {
                _Str = str;
                //添加头结点
                _head = new Node(_Str[0]);
                //给头结点添加孩子结点
                Add(_head, 0);
    
            }
            private void Add(Node parent,int index)
            {
                //计算左孩子索引
                int leftIndex = 2 * index + 1;
                //如果索引没有超过字符串长度
                if (leftIndex<_Str.Length)
                {
                    // '#表示空结点'
                    if (_Str[leftIndex] != '#') 
                    {
                        //添加左孩子
                        parent.Left = new Node(_Str[leftIndex]);
                        //递归调用Add 给左孩子添加孩子结点
                        Add(parent.Left, leftIndex);
                    }
                }
                int rightIndex = 2 * index + 2;
                if (rightIndex < _Str.Length) 
                {
                    if (_Str[rightIndex] != '#') 
                    {
                        parent.Right = new Node(_Str[rightIndex]);
                        Add(parent.Right, rightIndex);
                    }
                }
            }

三种遍历方式：

//先序遍历
            public void PreOrder(Node node)
            {
                if (node!=null)
                {
                    Console.Write(node);
                    PreOrder(node.Left);
                    PreOrder(node.Right);
                }
            }
    
            //中序遍历
            public void MidOrder(Node node)
            {
                if (node!=null)
                {
                    MidOrder(node.Left);
                    Console.Write(node);
                    MidOrder(node.Right);
                }
            }
    
            //后序遍历
            public void AfterOrder(Node node)
            {
                if (node!=null)
                {
                    AfterOrder(node.Left);
                    AfterOrder(node.Right);
                    Console.Write(node);
                }
            }

测试代码：

OurTree tree = new OurTree("ABCDE#F");
                tree.PreOrder(tree.Head);
                Console.WriteLine();
                tree.MidOrder(tree.Head);
                Console.WriteLine();
                tree.AfterOrder(tree.Head);
                Console.ReadKey();

结果：![20190516212537815.png][]

4.二叉树的广度优先遍历

与深度优先遍历不同的是，广度优先遍历是先搜索所有兄弟和堂兄弟结点再搜索子孙结点。而深度优先遍历则是先搜索一个结点的所有子孙结点，再去搜索这个结点的兄弟结点。

广度优先遍历，不需要使用递归，借助队列来实现

代码如下：

public void LevelOrder()
            {
                Queue<Node> queue = new Queue<Node>();
                queue.Enqueue(_head);
                while (queue.Count>0)
                {
                    Node node = (Node)queue.Dequeue();
                    Console.Write(node);
                    if (node.Left != null) 
                    {
                        queue.Enqueue(node.Left);
                    }
                    if (node.Right!=null)
                    {
                        queue.Enqueue(node.Right);
                    }
                }
            }

将根结点放入队列，分别判断左右孩子。

测试结果：

ABCDEF

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2huem1kbGhj_size_16_color_FFFFFF_t_70]: /images/20220131/62c8ccefc9dc44068a2149484eb247f4.png
[20190516202944424.png]: /images/20220131/0500a2353808409db614ccbeacde0d58.png
[20190516212537815.png]: /images/20220131/45bd3a9b51ca429bbd4374a1e4a3a6f1.png