解决二叉树的编程问题

女爷i 2021-09-18 09:34 349阅读 0赞

**目录**

（一）二叉树定义

（二）二叉树的相关术语

（三）二叉树的主要性质

二叉树的存储结构

1．顺序存储结构

2．二叉链式存储结构

用链式存储结构表示二叉树（Binary Tree）代码实现：

3．三叉链表存储结构

二叉树的遍历方法及递归实现

注意：如果中序遍历和后序遍历序列相同，则该树只有左子树没有右子树。如果中序遍历和先序遍历序列相同，则该树只有右子树没有左子树。

1.先序遍历（DLR）：先从二叉树的根开始，然后到左子树，再到右子树

2.中序遍历（LDR）：先从左子树开始，然后到根，再到右子树

3.后序遍历（LRD）：先从左子树开始，然后到右子树，再到根

4.层次遍历：从根结点开始，从上到下，从左到右依次访问

最优二叉树-哈夫曼树（Haffman）：https://mp.csdn.net/postedit

--------------------

# （一）二叉树定义 #

二叉树（Binary Tree）是n(n>=0)个有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的，被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称为一个结点。

二叉树由五种基本形态：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70][]

# （二）二叉树的相关术语 #

![20190304132414886.png][]

（1）结点的度。结点所拥有的子树的个数称为该结点的度。

（2）叶结点。度为0的结点称为叶结点，或者称为终端结点。

（3）分支结点。度不为0的结点称为分支结点，或称为非终端结点。一棵树的结点除了叶结点外，其余的都是分支结点。

（4）孩子，兄弟，双亲。顾名思义，不多做解释

（5）路径，路径长度。![20190304134838367.png][]

（6）祖先，子孙。在树种，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。

（7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1.

（8）树的深度。树中所有结点的最大层数称为树的深度。

（9）树的度。树中各结点度的最大值称为该树的度。二叉树的最大度为2.

（10）满二叉树。在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称为满二叉树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 1][]

（11）完全二叉树。一棵深度为K的有n个结点的二叉树，对树中的结点按从上到下，从左到右的顺序进行编号，如果编号为i（1<=i<=n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，但完全二叉树未必是满二叉树。

# （三）二叉树的主要性质 #

1.一颗非空二叉树的第i层上最多有![20190304140229958.png][]个结点。(i>=1)。

2.一颗深度为k的二叉树中，最多具有![20190304140213203.png][]个结点。（k>=1）

3.对任何一棵二叉树，如果其叶结点有n个，度为2的非叶子结点有m个，则n = m + 1。

4.具有n个结点的完全二叉树的深度k为![20190304140323441.png][]。  
5.对于有n个结点的完全二叉树，按层次对结点进行编号（从上到下，从左到右），对于任意编号为i的结点：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 2][]

# 二叉树的存储结构 #

二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。

它可采用**顺序存储结构**和**链式存储结构**。而链式存储结构有可以分为**二叉链表存储结构**、 三**叉链表存储结构（带双亲指针的二****叉链表存储结构）**

## 1．**顺序存储结构** ##

二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 3][]

对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图5-6给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图7.9所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。

## 2**．二叉****链式存储结构** ##

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：

其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 4][]

二叉树的二叉链表表示示意图

###  用链式存储结构表示二叉树（Binary Tree）代码实现： ###

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 用链式存储结构表示二叉树
    {
        class Program
        {
            static void Main(string[] args)
            {
            }
        }
        public class Node<T>
        {
            private T data;//数据域
            private Node<T> lChild;//左孩子
            private Node<T> rChild;//右孩子
    
            public T Data { get => data; set => data = value; }
            public Node<T> LChild { get => lChild; set => lChild = value; }
            public Node<T> RChild { get => rChild; set => rChild = value; }
    
            public Node()
            {
                data = default(T);
                LChild = null;
                rChild = null;
            }
            public Node (T val)
            {
                data = val;
                LChild = null;
                rChild = null;
            }
            public Node(Node <T> plchild,Node <T> prchild)
            {
                data = default(T);
                lChild = plchild;
                rChild = prchild;
            }
            public Node (T val ,Node <T> plchild,Node <T> prchild)
            {
                data = val;
                lChild = plchild;
                rChild = prchild;
            }
        }
    
        public class LinkBiTree<T>
        {
            private Node<T> head;//头引用
    
            public Node<T> Head { get => head; set => head = value; }
    
            //构造函数
            public LinkBiTree()
            {
                head = null;
            }
            public LinkBiTree (T val)
            {
                Node<T> p = new Node<T>(val);
                head = p;
            }
            public LinkBiTree (T val,Node <T> plchild,Node <T> prchild)
            {
                Node<T> p = new Node<T>(val, plchild, prchild);
                head = p;
            }
    
            /// <summary>
            /// 获取根结点
            /// </summary>
            /// <returns></returns>
            public Node <T> Root()
            {
                return head;
            }
    
            /// <summary>
            /// 判断二叉树是否为空
            /// </summary>
            /// <returns></returns>
            public bool IsEmpty()
            {
                if(head ==null)
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 判断是否是叶子结点
            /// </summary>
            /// <param name="p"></param>
            /// <returns></returns>
            public bool IsLeaf(Node <T> p)
            {
                if((p!=null )&&(p.LChild ==null )&&(p.RChild ==null))
                {
                    return true;
                }else
                {
                    return false;
                }
            }
            /// <summary>
            /// 获取结点的左孩子结点
            /// </summary>
            /// <param name="p"></param>
            /// <returns></returns>
            public Node <T> GetLChild(Node <T> p)
            {
                return p.LChild;
            }
    
            /// <summary>
            /// 获取结点的右孩子结点
            /// </summary>
            /// <param name="p"></param>
            /// <returns></returns>
            public Node <T> GetRChild(Node <T> p)
            {
                return p.RChild;
            }
    
            /// <summary>
            /// 将结点p的左子树插入值为val的新结点，原来的左子树称为新结点的左子树
            /// </summary>
            /// <param name="val"></param>
            /// <param name="p"></param>
            public void InsertL(T val,Node <T> p)
            {
                Node<T> temp = new Node<T>(val);
                temp.LChild = p.LChild;
                p.LChild = temp;
            }
    
            /// <summary>
            /// 将结点p的右子树插入值为val的新结点，原来的右子树称为新结点的右子树
            /// </summary>
            /// <param name="val"></param>
            /// <param name="p"></param>
            public void InsertR(T val, Node<T> p)
            {
                Node<T> temp = new Node<T>(val);
                temp.RChild = p.RChild;
                p.RChild = temp;
            }
    
            /// <summary>
            /// 若p或者p.Lchild非空，则删除p的左子树
            /// </summary>
            /// <param name="p"></param>
            /// <returns></returns>
            public Node <T> DeleteL(Node <T> p)
            {
                if((p==null )||(p.LChild ==null))
                {
                    return null;
                }
                Node<T> temp = p.LChild;
                p.LChild = null;
                return temp;
            }
    
            /// <summary>
            ///  若p或者p.Rchild非空，则删除p的右子树
            /// </summary>
            /// <param name="p"></param>
            /// <returns></returns>
            public Node <T> DeleteR(Node <T> p)
            {
                if((p==null )||p.RChild ==null)
                {
                    return null;
                }
                Node<T> temp = p.RChild;
                p.RChild = null;
                return temp;
            }
    
            /// <summary>
            /// 在二叉树中查找值为value的结点
            /// </summary>
            /// <param name="root"></param>
            /// <param name="value"></param>
            /// <returns></returns>
            public Node <T> Search(Node <T> root,T value)
            {
                Node<T> p = root;
                if(p ==null)
                {
                    return null;
                }
                if(!p.Data.Equals(value)) //很疑惑为什么要有“！”，我觉得不要“！”
                {
                    return p;
                }
                if(p .LChild !=null)
                {
                    return Search(p.LChild, value);
                }
                if(p .RChild !=null)
                {
                    return Search(p.RChild, value);
                }
                return null;
            }
    
            /// <summary>
            /// 先序遍历
            /// </summary>
            /// <param name="p"></param>
            public void PreOrder(Node <T> p)
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Tree is empty");
                    return;
                }
                if(p!=null)
                {
                    Console.WriteLine(p.Data);
                    PreOrder(p.LChild);
                    PreOrder(p.RChild);
                }
            }
    
            /// <summary>
            /// 中序遍历
            /// </summary>
            /// <param name="p"></param>
            public void InOrder(Node <T> p)
            {
                if (IsEmpty())
                {
                    Console.WriteLine("Tree is empty");
                    return;
                }
                if (p != null)
                {
                    PreOrder(p.LChild);
                    Console.WriteLine(p.Data); 
                    PreOrder(p.RChild);
                }
            }
    
            /// <summary>
            /// 后序遍历
            /// </summary>
            /// <param name="p"></param>
            public void PostOrder(Node<T> p)
            {
                if (IsEmpty())
                {
                    Console.WriteLine("Tree is empty");
                    return;
                }
                if (p != null)
                {
                    PreOrder(p.LChild);
                    PreOrder(p.RChild);
                    Console.WriteLine(p.Data);
                }
            }
    
            /// <summary>
            /// 层次遍历
            /// </summary>
            /// <param name="root"></param>
            public void LevelOrder(Node <T > root)
            {
                if(root==null)
                {
                    return;
                }
                CSeqQuene<Node<T>> sq = new CSeqQuene<Node<T>>(50);//使用队列的方式存储数据,先进先出
                sq.EnQuene(root);
                while (!sq .IsEmpty())//队列非空，结点没有处理完
                {
                    Node<T> temp = sq.DeQuene();
                    Console.WriteLine("{0}", temp);
                    if(temp .LChild !=null)
                    {
                        sq.EnQuene(temp.LChild);
                    }
                    if(temp .RChild !=null)
                    {
                        sq.EnQuene(temp.RChild);
                    }
                }
            }
        }
        
    }

## **3．三叉链表存储结构** ##

为了方便访问某结点的双亲，还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。每个结点由四个域组成，其结点结构为：

这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 5][]

尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，**二叉链表是最常用的二叉树存储方式**。

# 二叉树的遍历方法及递归实现 #

二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。

通过一次完整的遍历，可使二叉树中的结点信息由非线性排列变为某种意义上的线性序列，也就是说，遍历操作使非线性结构线性化。

对于二叉树的遍历方式，如果限定先左后右，则有三种遍历方式：先序遍历，中序遍历，后序遍历

**三种遍历都有一个规律，就是：逆时针沿着二叉树外缘移动，即方向相同。并且，三种遍历都有一个“若二叉树为空，遍历结束”的判断**

### **注意：如果中序遍历和后序遍历序列相同，则该树只有左子树没有右子树。如果中序遍历和先序遍历序列相同，则该树只有右子树没有左子树。** ###

## 1.先序遍历（DLR）：先从二叉树的根开始，然后到左子树，再到右子树 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 6][]

上图中：先序遍历序列是ABDCEF，重点是记住第一个字母“A”是根，出发点是根“A”

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 7][]

/// <summary>
            /// 先序遍历
            /// </summary>
            /// <param name="p"></param>
            public void PreOrder(Node <T> p)
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Tree is empty");
                    return;
                }
                if(p!=null)
                {
                    Console.WriteLine(p.Data);
                    PreOrder(p.LChild);
                    PreOrder(p.RChild);
                }
            }

## 2.中序遍历（LDR）：先从左子树开始，然后到根，再到右子树 ##

![20190305090718635.png][]

上图中：中序遍历序列是DBAECF，重点是记住中序遍历的根位置，是在序列的第一个字母和最后一个字母之间，出发点是左子树的最下边的左边的开始

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 8][]

/// <summary>
            /// 中序遍历
            /// </summary>
            /// <param name="p"></param>
            public void InOrder(Node <T> p)
            {
                if (IsEmpty())
                {
                    Console.WriteLine("Tree is empty");
                    return;
                }
                if (p != null)
                {
                    PreOrder(p.LChild);
                    Console.WriteLine(p.Data); 
                    PreOrder(p.RChild);
                }
            }

## 3.后序遍历（LRD）：先从左子树开始，然后到右子树，再到根 ##

![20190305090751536.png][]

上图中：后序遍历序列式DBECFCA,重点是知道了根是最后面一个字母“A”， 出发点是左子树的最下边左边

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 9][]

/// <summary>
            /// 后序遍历
            /// </summary>
            /// <param name="p"></param>
            public void PostOrder(Node<T> p)
            {
                if (IsEmpty())
                {
                    Console.WriteLine("Tree is empty");
                    return;
                }
                if (p != null)
                {
                    PreOrder(p.LChild);
                    PreOrder(p.RChild);
                    Console.WriteLine(p.Data);
                }
            }

## 4.层次遍历：从根结点开始，从上到下，从左到右依次访问 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 10][]

层次遍历的算法（用队列存储数据）：

（1）从队列中取出一个结点引用，并访问该结点；

（2）若结点的左子树非空，则将该结点的左子树引用入队；

（3）若结点的右子树非空，则将该结点的右子树引用入队。

/// <summary>
            /// 层次遍历
            /// </summary>
            /// <param name="root"></param>
            public void LevelOrder(Node <T > root)
            {
                if(root==null)
                {
                    return;
                }
                CSeqQuene<Node<T>> sq = new CSeqQuene<Node<T>>(50);//使用队列的方式存储数据,先进先出
                sq.EnQuene(root);
                while (!sq .IsEmpty())//队列非空，结点没有处理完
                {
                    Node<T> temp = sq.DeQuene();
                    Console.WriteLine("{0}", temp);
                    if(temp .LChild !=null)
                    {
                        sq.EnQuene(temp.LChild);
                    }
                    if(temp .RChild !=null)
                    {
                        sq.EnQuene(temp.RChild);
                    }
                }
            }

# 最优二叉树-哈夫曼树（Haffman）：[https://mp.csdn.net/postedit][https_mp.csdn.net_postedit] #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70]: /images/20210725/43f6120077a84435a649fae0ebb77a8c.png
[20190304132414886.png]: /images/20210725/69cd94e0b47d431f963672ae45843284.png
[20190304134838367.png]: /images/20210725/7d3f01663efb488d9e4e143e56f9c733.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 1]: /images/20210725/74bd49aa697240618df0e3407dd6d2c8.png
[20190304140229958.png]: /images/20210725/2dede19dfd82403cad078b3d3b9defe6.png
[20190304140213203.png]: /images/20210725/9e889d7cbafd44469d901bebf750a09c.png
[20190304140323441.png]: /images/20210725/ec31b94339d34b9e9524f455a8b1722e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 2]: /images/20210725/92d7b343991b4230ad81f0bad1b799bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 3]: /images/20210725/9c824471be3a48a69c389e256a79acb6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 4]: /images/20210725/e27b9522f1674515bce349ec636f4c51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 5]: /images/20210725/693ed3e984ec454eb395eb8f91557913.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 6]: /images/20210725/b7ebbad00c05426b87eabe8822362ebc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 7]: /images/20210725/b9e54d7b3ada48ae878bede534f8f2a7.png
[20190305090718635.png]: /images/20210725/85da6945958c4d308314e9ef27f86932.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 8]: /images/20210725/1d1edeb6677e41bb87e9b1be8e16d52d.png
[20190305090751536.png]: /images/20210725/a043b2e671dc405db211f032429fca0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 9]: /images/20210725/d015b164908f40069af8cc739609cc7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 10]: /images/20210725/e5c2835efac34acda07f1acfc07454a5.png
[https_mp.csdn.net_postedit]: https://mp.csdn.net/postedit