解决树和森林的编程问题

迷南。 2021-09-18 10:42 302阅读 0赞

**目录**

树的2个特点：

树的常用相关术语：

（一）树的四种表示方法：直观表示法，嵌套集合表示法，凹入表示法，广义表表示法

（二）树的5种存储方式，即：多重链表表示法，双亲表示法，孩子链表表示法，双亲孩子表示法，孩子兄弟表示法

1.多重链表表示法代码实现：

2.双亲表示法

3.孩子链表表示法：（查找孩子比较方便，但查找双亲比较困难，故适用于对孩子操作多的应用）

4.双亲孩子表示法（将双亲表示法和孩子链表表示法相结合）

5.树的孩子兄弟表示法

（三）树，二叉树，森林的转换

1.树转换为二叉树

2.森林转换为二叉树

3.二叉树转换为树和森林

（四）解决树和森林的遍历问题

1.树的遍历（先序遍历，后序遍历，层次遍历）

（1）先序遍历（A B E F C D G）

（2）后序遍历（E F B C G D A）

（3）层次遍历（A B C D E F G）

2.森林的遍历（先序遍历，中序遍历）---森林的先序遍历和中序遍历与所转换的二叉树的先序遍历和中序遍历的结果序列相同！！！

（1）先序遍历（A B C D E F G H J I K）

（2）中序遍历（B A D E F C J H K I G）

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

### **树的2个特点：** ###

（1）树的根结点没有前驱结点，除了根结点之外的所有结点有且只有一个前驱结点

（2）树的所有结点可以有零个或多个后继结点

### **树的常用相关术语：** ###

结点（node）：表示树中的数据元素

结点的度：结点所拥有子树的个数

树的度：树中各结点度的最大值

双亲：结点的上层结点叫该结点的双亲

结点的层次：规定根结点的层次为1，其余结点的层次等于其双亲结点的层次加1

森林：很多树的集合。当然，根据定义，一棵树也可以称为森林

叶子结点（Leaf Node）：度为0的结点。也叫终端结点

# **（一）树的四种表示方法：直观表示法，嵌套集合表示法，凹入表示法，广义表表示法** #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70][]

树形结构是一种非常重要的非线性结构

树的遍历方式有：先序遍历，后序遍历，层次遍历

森林的遍历方式有：先序遍历，中序遍历。（森林的先序遍历和中序遍历与所转换的先序遍历和中序遍历的结果序列相同）

# （二）树的5种存储方式，即：多重链表表示法，双亲表示法，孩子链表表示法，双亲孩子表示法，孩子兄弟表示法 #

树的孩子多重链表表示法示意：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 1][]

## 1.多重链表表示法代码实现： ##

using System;
    
    namespace 用多重链表表示法存储树
    {
        class Program
        {
            static void Main(string[] args)
            {
            }
        }
        public interface ITree<T>
        {
            T Root();//求树的根结点。如果树非空，返回根结点，否则返回空
            T Parent(T t);//求结点t的双亲结点。如果t的双亲结点存在，返回双亲结点，否则返回空
            T Child(T t, int i);//求结点t的第i个子结点。如果存在，返回第i个子结点，否则返回空
            T RightSibling(T t);//求结点t的第一个右边兄弟结点。如果存在，返回第一个右边兄弟结点，否则返回空
            bool Insert(T s, T t, int i);//把以s为头结点的树插入到树中作为结点t的第i棵子树。成功返回ture，否则返回false
            T Delete(T t, int i);//删除结点t的第i棵子树。成功返回第i棵子树的根结点，否则返回空
            void Traverse(int TraverseType);//按某种方式遍历树
            void Clear();//清空树
            bool IsEmpty();//判断树是否为空。如果是空树，返回true，否则返回false
            int GetDepth();//求树的深度。如果树不为空，返回树的层次，否则返回0
        }
    
        //树的多链表表示法的结点的结构实现
        class MLNode<T>
        {
            private T data;//存储结点的数据
            private MLNode<T>[] childs;//存储子结点的数据
    
            public T Data { get => data; set => data = value; }
            public MLNode<T>[] Childs { get => childs; set => childs = value; }
    
            public MLNode(int max)
            {
                childs = new MLNode<T>[max];
                for (int i = 0; i < childs.Length; i++)
                {
                    childs[i] = null;
                }
            }
    
        }
    
        class MLTree<T> : ITree<MLNode<T>>
        {
            private MLNode<T> head;
    
            public  MLNode<T> Head { get => head; set => head = value; }
    
            //构造函数
            public MLTree()
            {
                head = null;
            }
            public MLTree (MLNode <T> node)
            {
                head = node;
            }
    
            /// <summary>
            /// 求树的根结点。如果树非空，返回根结点，否则返回空
            /// </summary>
            /// <returns></returns>
            public MLNode<T> Root()
            {
                return head;
            }
    
            /// <summary>
            /// 清空树
            /// </summary>
            public void Clear()
            {
                head = null;
            }
    
            /// <summary>
            /// 判断树是否为空。如果是空树，返回true，否则返回false
            /// </summary>
            /// <returns></returns>
            public bool IsEmpty()
            {
                return head == null;
            }
    
            /// <summary>
            /// 求结点t的第i个子结点。如果存在，返回第i个子结点，否则返回空
            /// </summary>
            /// <param name="t"></param>
            /// <param name="i"></param>
            /// <returns></returns>
            public MLNode<T> Child(MLNode<T> t, int i)
            {
                if (t != null&& i < t.Childs.Length)
                {
                    return t.Childs[i];
                }else
                {
                    return null;
                }
            }
    
            /// <summary>
            /// 求结点t的双亲结点。如果t的双亲结点存在，返回双亲结点，否则返回空。
            /// 按层次遍历的算法进行查找
            /// </summary>
            /// <param name="t"></param>
            /// <returns></returns>
            public MLNode<T> Parent(MLNode<T> t)
            {
                if(IsEmpty ()||t==null)
                {
                    return null;
                }
    
                MLNode<T> temp = head;
                if(temp .Data .Equals (t .Data))
                {
                    return null;
                }
    
                CSeqQuene<MLNode<T>> que = new CSeqQuene<MLNode<T>>();
                que.EnQuene(temp);
                while (que .GetLength() > 0)
                {
                    temp = que.DeQuene();
                    for (int i = 0; i < temp .Childs .Length ; i++)
                    {
                        if(temp .Childs [i]!=null)
                        {
                            if(temp .Childs [i].Data .Equals (t.Data))
                            {
                                return temp;
                            }else
                            {
                                que.EnQuene(temp.Childs[i]);
                            }
                        }
                    }
                }
                return null;
            }
    
            /// <summary>
            /// 查找结点t在兄弟中的排行，成功时返回位置索引，否则返回-1
            /// </summary>
            /// <param name="t"></param>
            /// <returns></returns>
            private int FindRank(MLNode <T> t)
            {
                MLNode<T> pn = Parent(t);
                for (int i = 0; i < pn .Childs .Length ; i++)
                {
                    MLNode<T> temp = pn.Childs[i];
                    if(temp !=null &&temp .Data .Equals (t.Data))
                    {
                        return i;
                    }
                }
                return -1;
            }
    
            /// <summary>
            /// 查找在树中的结点t，成功时返回结点t，否则返回null
            /// </summary>
            /// <param name="t"></param>
            /// <returns></returns>
            private MLNode <T> FindNode(MLNode <T> t)
            {
                if(head .Data .Equals (t.Data))
                {
                    return head;
                }
    
                MLNode<T> pn = Parent(t);
                foreach (MLNode <T> temp in pn .Childs )
                {
                    if (temp != null && temp.Data.Equals(t.Data))
                    {
                        return temp;
                    }
                }
                return null;
            }
    
            /// <summary>
            /// 删除结点t的第i棵子树。成功返回第i棵子树的根结点，否则返回空
            /// </summary>
            /// <param name="t"></param>
            /// <param name="i"></param>
            /// <returns></returns>
            public MLNode<T> Delete(MLNode<T> t, int i)
            {
                t = FindNode(t);
                MLNode<T> node = null;
                if(t!=null && i<t.Childs .Length)
                {
                    node = t.Childs[i];
                    t.Childs[i] = null;
                }
                return node;
            }
    
            /// <summary>
            /// 把以s为头结点的树插入到树中作为结点t的第i棵子树。成功返回ture，否则返回false
            /// </summary>
            /// <param name="s"></param>
            /// <param name="t"></param>
            /// <param name="i"></param>
            /// <returns></returns>
            public bool Insert(MLNode<T> s, MLNode<T> t, int i)
            {
                if(IsEmpty())
                {
                    head = t;
                }
                t = FindNode(t);
                if (t != null&&i<t.Childs .Length)
                {
                    t.Childs[i] = s;
                    return true;
                }
                else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 求结点t的第一个右边兄弟结点。如果存在，返回第一个右边兄弟结点，否则返回空
            /// </summary>
            /// <param name="t"></param>
            /// <returns></returns>
            public MLNode<T> RightSibling(MLNode<T> t)
            {
                MLNode<T> pn = Parent(t);
                if(pn!=null)
                {
                    int i = FindRank(t);
                    return Child(pn, i + 1);
                }
                else
                {
                    return null;
                }
            }
    
            /// <summary>
            /// 求树的深度。如果树不为空，返回树的层次，否则返回0
            /// </summary>
            /// <returns></returns>
            public int GetDepth()
            {
                return 0;//书上只有这一行代码。但我感觉这不完整，因为并没有进行树不为空的判断
            }
    
            /// <summary>
            /// 按某种方式遍历树 TraverseType:0:先序  1：后序  2：层序
            /// </summary>
            /// <param name="TraverseType"></param>
            public void Traverse(int TraverseType)
            {
                switch (TraverseType)
                {
                    case 0:
                        PreOrder(head);
                        break;
                    case 1:
                        PostOrder(head);
                        break;
                    default:
                        BroadOrder(head);
                        break;
                }
            }
    
            /// <summary>
            /// 先序遍历树结点。树有三种遍历方式，分别是：先序遍历，后序遍历，层次遍历。注意：没有中序遍历
            /// </summary>
            /// <param name="root"></param>
            public void PreOrder(MLNode <T> root)
            {
                if(root ==null)
                {
                    return;
                }
                Console.WriteLine(root.Data + "");
                for (int i = 0; i < root .Childs .Length ; i++)
                {
                    PreOrder(root.Childs[i]);
                }
            }
    
            /// <summary>
            /// 后序遍历树结点
            /// </summary>
            /// <param name="root"></param>
            public void PostOrder(MLNode <T> root)
            {
                if(root ==null)
                {
                    return;
                }
                for (int i = 0; i < root .Childs .Length ; i++)
                {
                    PostOrder(root.Childs[i]);
                }
                Console.WriteLine(root.Data + "");
            }
    
            /// <summary>
            /// 层次遍历
            /// </summary>
            /// <param name="root"></param>
            public void BroadOrder(MLNode <T> root)
            {
                Console.WriteLine("层序遍历开始:");
                if(root ==null)
                {
                    Console.WriteLine("没有结点！");
                    return;
                }
    
                MLNode<T> temp = root;
                CSeqQuene<MLNode<T>> que = new CSeqQuene<MLNode<T>>();
                que.Equals(temp);
                while (que .GetLength() > 0)
                {
                    temp = que.DeQuene();//结点出队列并访问
                    Console.WriteLine(temp.Data + "");
                    for (int i = 0; i < temp .Childs.Length ; i++)
                    {
                        if(temp .Childs [i]!=null)
                        {
                            que.EnQuene(temp.Childs[i]);
                        }
                    }
                }
                Console.WriteLine("遍历结束");
            }
        }
    }

##  2.双亲表示法 ##

树的双亲表示法的结点的结构如图，data存储结点的数据，parent保存当前结点的父结点的存储位置

树的双亲表示法数据：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 2][]

表中parent域的值为-1时表示该结点无双亲结点，即该结点是一个根结点

树的双亲表示法的结点的结构实现：

public class PNode<T>
        {
            private T data;
            private int parent;
    
            public T Data { get => data; set => data = value; }
            public int Parent { get => parent; set => parent = value; }
    
            public PNode (T val,int pos)
            {
                data = val;
                parent = pos; 
            }
            public PNode (PNode <T> node)
            {
                data = node.data;
                parent = node.parent;
            }
        }

树的双亲表示法的树类PTree<T>的定义如下：

public class PTree<T>
        {
            private PNode<T>[] nodes;
            public PTree (int size)
            {
                nodes = new PNode<T>[size];
            }
            ......
        }

## 3.孩子链表表示法：（查找孩子比较方便，但查找双亲比较困难，故适用于对孩子操作多的应用） ##

每个孩子结点保存有两个信息，一个是每个孩子结点在一维数组中的序号，另一个是下一个孩子结点的地址信息。

树的孩子链表表示法如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 3][]

孩子结点结构如下：pos表示该孩子结点在数组中的存储位置，nextChild存储下一个孩子结点的信息：

public class ChildNode
        {
            private int pos;
            private ChildNode nextChild;
    
            public int Pos { get => pos; set => pos = value; }
            public ChildNode NextChild { get => nextChild; set => nextChild = value; }
    
            public ChildNode()
            {
                pos = -1;
                nextChild = null;
            }
            public ChildNode(int p, ChildNode nc)
            {
                pos = p;
                nextChild = nc;
            }
        }

树的孩子链表表示法的结点的结构如下：

public class CLNode<T>
        {
            private T data;
            private ChildNode firstChild;
    
            public T Data { get => data; set => data = value; }
            public ChildNode FirstChild { get => firstChild; set => firstChild = value; }
    
            public CLNode()
            {
                data = default(T);
                firstChild = null;
            }
            public CLNode (T d,ChildNode c)
            {
                data = d;
                firstChild = c;
            }
        }

树的孩子链表表示法的树类CLTree<T>的定义如下：

public class CLTree<T>
        {
            private CLNode<T>[] nodes;
            public CLTree (int size)
            {
                nodes = new CLNode<T>[size];
            }
    
            //索引器
            public CLNode <T> this[int index]
            {
                get { return nodes[index]; }
                set { nodes[index] = value; }
            }
            ......
        }

##  4.双亲孩子表示法（将双亲表示法和孩子链表表示法相结合） ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 4][]

## 5.树的孩子兄弟表示法 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 5][]

# （三）树，二叉树，森林的转换 #

## 1.树转换为二叉树 ##

方法：

（1）树中所有兄弟加一条连线

（2）对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点之间的连线

（3）以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 6][]

## 2.森林转换为二叉树 ##

方法：

（1）将森林中的每棵树转换成相应的二叉树

（2）第一课二叉树不动，从第二课二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是有森林转换得到的二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 7][]

## 3.二叉树转换为树和森林 ##

方法：

（1）若某结点是其双亲的左孩子，则把该节点的左孩子，右孩子的右孩子...都与该结点的双亲结点用线连起来

（2）删去原二叉树中所有的双亲结点与右孩子结点的连线

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 8][]

# （四）解决树和森林的遍历问题 #

以此树作为例子分析：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 9][]

## 1.树的遍历（先序遍历，后序遍历，层次遍历） ##

### （1）先序遍历（A B E F C D G） ###

/// <summary>
            /// 先序遍历树结点。树有三种遍历方式，分别是：先序遍历，后序遍历，层次遍历。注意：没有中序遍历
            /// </summary>
            /// <param name="root"></param>
            public void PreOrder(MLNode <T> root)
            {
                if(root ==null)
                {
                    return;
                }
                Console.WriteLine(root.Data + "");
                for (int i = 0; i < root .Childs .Length ; i++)
                {
                    PreOrder(root.Childs[i]);
                }
            }

### （2）后序遍历（E F B C G D A） ###

/// <summary>
            /// 后序遍历树结点
            /// </summary>
            /// <param name="root"></param>
            public void PostOrder(MLNode <T> root)
            {
                if(root ==null)
                {
                    return;
                }
                for (int i = 0; i < root .Childs .Length ; i++)
                {
                    PostOrder(root.Childs[i]);
                }
                Console.WriteLine(root.Data + "");
            }

### （3）层次遍历（A B C D E F G） ###

/// <summary>
            /// 层次遍历
            /// </summary>
            /// <param name="root"></param>
            public void BroadOrder(MLNode <T> root)
            {
                Console.WriteLine("层序遍历开始:");
                if(root ==null)
                {
                    Console.WriteLine("没有结点！");
                    return;
                }
    
                MLNode<T> temp = root;
                CSeqQuene<MLNode<T>> que = new CSeqQuene<MLNode<T>>();
                que.Equals(temp);
                while (que .GetLength() > 0)
                {
                    temp = que.DeQuene();//结点出队列并访问
                    Console.WriteLine(temp.Data + "");
                    for (int i = 0; i < temp .Childs.Length ; i++)
                    {
                        if(temp .Childs [i]!=null)
                        {
                            que.EnQuene(temp.Childs[i]);
                        }
                    }
                }
                Console.WriteLine("遍历结束");
            }

## 2.森林的遍历（先序遍历，中序遍历）---森林的先序遍历和中序遍历与所转换的二叉树的先序遍历和中序遍历的结果序列相同！！！ ##

### （1）先序遍历（A B C D E F G H J I K） ###

### （2）中序遍历（B A D E F C J H K I G） ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70]: /images/20210725/22f431f4e45f4b42ae4a893662403116.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 1]: /images/20210725/f1ddf48e912840ac8ddaf010c520ae75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 2]: /images/20210725/93a23a02159041a4b0f15dd9a966be23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 3]: /images/20210725/0029b40e35b647f7b5d1abf1d8b8295c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 4]: /images/20210725/98719d37ac96465e8fcf51a43752873f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 5]: /images/20210725/2ad1600cb64c4f4e9be685504411da7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 6]: /images/20210725/b79d86e5572d47e4998ee1c6eacf9902.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 7]: /images/20210725/7cb1f3e9353544c0b272efcbbde0f819.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 8]: /images/20210725/67cf380d611843fb9c02b917d40523a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzIzMjU2_size_16_color_FFFFFF_t_70 9]: /images/20210725/3c1ac6e0afd14bb192671493710f9ef0.png