数据结构（树和二叉树的转换与遍历）

淡淡的烟草味﹌ 2022-06-05 03:43 112阅读 0赞

## 二叉树的遍历 ##

![这里写图片描述][SouthEast]  
**先序遍历(DLR)**：先遍历根节点，再遍历左子树，最后遍历右子树  
遍历结果：ABDHIEJCFG

public void PreOrder(Node<T> root)
            {
                if (root==null)
                {
                    return;
                }
                Console.WriteLine(root.Data);
                PreOrder(root.LChild);
                PreOrder(root.RChild);
            }

**中序遍历(LDR)**：先遍历左子树，再遍历根节点，最后遍历右子树  
遍历结果：HDIBJEAFCG

public void InOrder(Node<T> root)
            {
                if (root == null)
                {
                    return;
                }
                InOrder(root.LChild);
                Console.WriteLine(root.Data);
                InOrder(root.RChild);
            }

**后序遍历(LRD)**：先遍历左子树，再遍历右子树，最后遍历根节点  
遍历结果：HIDJEBFGCA

public void PostOrder(Node<T> root)
            {
                if (root == null)
                {
                    return;
                }
                PostOrder(root.LChild);
                PostOrder(root.RChild);
                Console.WriteLine(root.Data);
            }

**层序遍历**：从上到下，从左到右进行遍历  
遍历结果：ABCDEFGHIJ

public void LevelOrder(Node<T> root)
            {
                Queue<Node<T>> myQueue=new Queue<Node<T>>();
                myQueue.Enqueue(root);
                while (myQueue.Count!=0)
                {
                    Node<T> temp=myQueue.Dequeue();
                    Console.WriteLine(temp.Data);
                    if (temp.LChild!=null)
                    {
                        myQueue.Enqueue(temp.LChild);
                    }
                    if (temp.RChild!=null)
                    {
                        myQueue.Enqueue(temp.RChild);
                    }
                }
            }

## 树和二叉树的转换 ##

**树转换成二叉树**  
1>加线：就是在所有兄弟之间加一条线  
2>抹线：就是对书中的每个节点，只保留他与第一个孩子之间的线，删除他与其他孩子之间的连线  
3>旋转：就是以树的根节点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明  
![这里写图片描述][SouthEast 1]  
**森林转换为二叉树**  
1>先把每棵树转换为二叉树  
2>第一课二叉树不动，从第二棵二叉树开始一次吧后一棵二叉树的根节点作为前一棵二叉树的根节点的有孩子结点，用线连接起来。  
![这里写图片描述][SouthEast 2]  
**二叉树转换为树**：  
1>若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；  
2>删除原二叉树中所有结点与其右孩子结点的连线；  
3>整理（1）和（2）两步得到的树，使之结构层次分明。  
![这里写图片描述][SouthEast 3]  
**二叉树转换为森林**：  
1>先把每个结点与右孩子结点的连线删除，得到分离的二叉树；  
2>把分离后的每棵二叉树转换为树；  
3>整理第（2）步得到的树，使之规范，这样得到森林。

## 树和森林的遍历 ##

![这里写图片描述][SouthEast 4]  
树的遍历  
**先序遍历**：先遍历根节点，之后遍历每颗子树  
遍历结果：ABEFGCHDIJ  
**后序遍历**：先遍历每颗字数，之后遍历根节点  
遍历结果：EFGBHCIJDA  
![这里写图片描述][SouthEast 5]  
森林的遍历  
**先序遍历**：依次先序遍历每一棵树  
遍历结果：ABCDEFGHJI  
**中序遍历**：依次后序遍历每一棵树  
遍历结果：BCDAFEJHIG

[SouthEast]: /images/20220605/ac2dc0c39efd403799a4d487e8d57634.png
[SouthEast 1]: /images/20220605/ff474ee4565d48a2bd4ef7e699440cde.png
[SouthEast 2]: /images/20220605/e60f44b30c7d4fed918ac15a28acb865.png
[SouthEast 3]: /images/20220605/6b6ef71b339846e4adadd4f98540e7af.png
[SouthEast 4]: /images/20220605/62db8050a2cb4f7c901e22a32d9413e0.png
[SouthEast 5]: /images/20220605/e31cdcf310d8403e954deaef28060f46.png