重生之数据结构与算法----二叉树

简介

二叉树作为链表的衍生，本身不难。但它同样是其它复杂数据结构的前身。比如红黑树，多叉数，二叉堆，图，字典数等等。如果不熟悉二叉树，就会陷入一个难者不会，会者不难的境地。
几种简单的二叉树

树的顶点(1)，一般称为根节点,下方直接相连的节点称之为子节点,上方直接相连的节点称之为父节点，最下方没有子节点的(5，6) 被称为叶子节点。
一棵树从根节点到叶子节点的距离，被称为树的深度,比如1-5的深度为4，1-6的深度为4。
满二叉树

看图就能知道，除了叶子节点，其它所有节点都有左右节点，所以被称为满二叉树。

因为这个特性，可以很好的算出二叉树的节点数量。(2^深度)-1

完全二叉树

与满二叉树类似，二叉树的每一层节点都靠左排列，除了最后一层，其它每层都必须是满的。

由于完全二叉树向左排列的特质，所以它的节点非常紧凑。因此，如果我们按照从上到下,从左到右的顺序对它的节点编号，那么父子节点的索引会存在明显的规律。

例如使用数组来存储完全二叉树，就可以利用这些规律方便地访问节点的父子节点，从而实现诸如堆排序等算法

平衡二叉树(Balanced Binary Tree)

平衡二叉树的特点是：它的每个左右子树的高度差不会超过1.

根节点1的左子节点高度为3，右子节点高度为2。 节点5的左子节点高度为0，右子节高度为8.因此它是一个平衡二叉树。

节点2做左子节点高度为0，右子节点高度为2.超过了1.因此不是一个平衡二叉树 。
二叉搜索树(Binay Search Tree)

二叉搜索树的特点是:左小右大。对于树中的每个节点，其左节点的值要小于节点的值，其右节点的值要大于节点的值。

二叉搜索树是最常见的二叉树，因为它左小右大的特性。完美利用了二分法快速找到某个节点。
如果节点没有此特性，就只能遍历整棵树。

注意是整个树都要符合左小右大的定义，否则就不是BST

二叉树的简单实现

二叉树可以用链表与数组来实现，更多情况下，都是使用链表。从语义角度触发，使用链表也更加贴合语义。

1.     public class BinaryTreeNode
2.     {
3.         public static BinaryTreeNode CreatedRootTree()
4.         {
5.             var root = new BinaryTreeNode(1);
6.             root.Left = new BinaryTreeNode(2);
7.             root.Right = new BinaryTreeNode(3);
9.             root.Left.Left = new BinaryTreeNode(4);
10.             root.Left.Right = new BinaryTreeNode(5);
12.             root.Right.Left = new BinaryTreeNode(6);
13.             root.Right.Right = new BinaryTreeNode(7);
15.             return root;
16.         }
18.         public BinaryTreeNode(int value)
19.         {
20.             Value = value;
21.         }
22.         public int Value { get; set; }
23.         public BinaryTreeNode Left { get; set; }
24.         public BinaryTreeNode Right { get; set; }
25.     }

复制代码

当然，使用数组也无伤大雅.在二叉堆和并查集算法时，会更占优势。

1.     public class BinaryTreeNodeV2
2.     {
4.         public static Dictionary<int, List<int>> CreatedRootTree()
5.         {
6.             //字典的底层是数组
7.             Dictionary<int, List<int>> tree = new Dictionary<int, List<int>>();
9.             tree.Add(1, new List<int> { 2, 3 });
10.             tree.Add(2, new List<int> { 4, 5 });
11.             tree.Add(3, new List<int> { 6, 7 });
13.             return tree;
15.         }
16.     }

复制代码

二叉树遍历(DFS,深度优先)

1.         public static void TreverseDFS(BinaryTreeNode tree)
2.         {
3.                         //前序遍历 Console.WriteLine(tree.Value);
4.             if (tree.Left != null)
5.             {
6.                 TreverseDFS(tree.Left);
7.             }
8.                         //中序遍历 Console.WriteLine(tree.Value);
9.             if (tree.Right != null)
10.             {
11.                 TreverseDFS(tree.Right);
12.             }
13.                         //后序遍历 Console.WriteLine(tree.Value);
14.         }

复制代码

前序/中序/后序遍历

总所周知，二叉树遍历有三种遍历，顺序不同结果也不同

• 前序遍历
  先遍历根节点，然后左节点，右节点。
  输出结果为1，2，4，5，3，6，7
  
• 中序遍历
  先遍历左节点，然后根节点，右节点。
  输出结果为4，2，5，1，6，3，7
  
• 后序遍历
  先遍历左节点，然后右节点，根节点
  输出结果为4，5，2，6，7，3，1
  

实际上，遍历递归的顺序是不变的,默认情况下都是先遍历左子树，再遍历右子树。所谓的前中后序遍历，其实就是在上述二叉树遍历的不同位置写代码。
前序遍历的代码在进入节点时执行，中序遍历在左节点遍历完成后执行，后序遍历在左右节点遍历后执行。
二叉树遍历(BFS,广度优先)

1.         public static void TreverseBFS(BinaryTreeNode tree)
2.         {
3.             var treeQueue = new Queue<BinaryTreeNode>();
4.             treeQueue.Enqueue(tree);
6.             while (treeQueue.Count > 0)
7.             {
8.                 var node = treeQueue.Dequeue();
10.                 Console.WriteLine(node.Value);
11.                 if (node.Left != null)
12.                 {
13.                     treeQueue.Enqueue(node.Left);
14.                 }
15.                 if (node.Right != null)
16.                 {
17.                     treeQueue.Enqueue(node.Right);
18.                 }
19.             }
20.         }

复制代码

写法2

上面的写法最简单，但也有一个缺点。作为广度优先算法，竟然不知道自己在第一层，就很扯。
因此稍微改进一下，统计一下当前层。

1.         public static void TreverseBFS_Depth(BinaryTreeNode tree)
2.         {
3.             var treeQueue = new Queue<BinaryTreeNode>();
4.             treeQueue.Enqueue(tree);
5.             int depth = 1;
7.             while (treeQueue.Count > 0)
8.             {
9.                 var size = treeQueue.Count;
10.                
11.                 for (int i = 0; i < size; i++)
12.                 {
13.                     var node = treeQueue.Dequeue();
14.                     Console.WriteLine($"value= {node.Value} depth={depth}");
15.                     if (node.Left != null)
16.                     {
17.                         treeQueue.Enqueue(node.Left);
18.                     }
19.                     if (node.Right != null)
20.                     {
21.                         treeQueue.Enqueue(node.Right);
22.                     }
23.                 }
24.                 depth++;
25.             }
26.         }

复制代码

写法3

在写法2中，每下钻一层，depth++一次。
这里就衍生出一个问题，到目前为止，同一层的所有节点权重都是一样，路径权重和都是相同的。
如果每个节点的权重是任意值，然后让你打印当前depth+权重值=?，写法2无法做到了。

简单来说，就是写法2，节点是无状态的 or 状态恒定。如果节点是有状态的，那么写法2中，并没有记录这个状态。

1.         public static void TreverseBFS_Depth_State(BinaryTreeNode tree)
2.         {
3.             var treeQueue=new Queue<BinaryTreeNode>();
4.             int depth = 1;
5.             //状态维护，正好维护者当前depth，这里是一个抽象的概念，你想要维护任何状态都可以。
6.             tree.State = depth;
7.             treeQueue.Enqueue(tree);
9.             while (treeQueue.Count > 0)
10.             {
11.                 var node=treeQueue.Dequeue();
12.                 Console.WriteLine($"value= {node.Value} depth={node.State}");
14.                 if (node.Left != null)
15.                 {
16.                     //进入下一层，depth+1
17.                     node.Left.State = node.State + 1;
18.                     treeQueue.Enqueue(node.Left);
19.                 }
20.                 if (node.Right != null)
21.                 {
22.                     node.Right.State = node.State + 1;
23.                     treeQueue.Enqueue(node.Right);
24.                 }
25.             }
26.         }

复制代码

这样每个节点都有了自己的State变量，基本可以满足所有BFS算法的需求.

其本质就是空间换时间。可以定义更多字段来满足状态维护需求。

BFS与DFS适用范围

为什么DFS常用来寻找所有路径？

深度优先搜索（DFS）常用来寻找所有路径，主要是因为其具有路径探索彻底、空间利用高效、实现逻辑简单等特点

• 路径探索彻底：
  DFS 会从起始节点开始，沿着一条路径尽可能深地探索，直到无法继续或达到目标节点，然后回溯到上一个节点，继续探索其他路径。这种方式能够确保遍历到图中所有可达的节点和路径，不会遗漏任何可能的路径，从而可以找到从起始节点到目标节点的所有路径。
  
• 空间利用高效：
  在实现 DFS 时，通常可以使用栈（Stack）来辅助记录遍历的路径和状态，无论是显式地使用栈数据结构，还是利用函数调用栈的隐式特性，都能在一定程度上节省空间。尤其对于大型复杂的图结构，相比一些需要存储大量中间状态和路径信息的算法，DFS 在空间效率上具有优势，使其能够更有效地处理寻找所有路径的任务。
  
• 实现逻辑简单：
  DFS 的实现相对简单直观，通过递归或栈操作就可以很方便地实现对图的遍历。在寻找所有路径的场景中，只需要在遍历过程中记录下经过的节点和路径信息，当找到目标节点时，就可以将当前路径保存下来。这种简单的实现方式使得 DFS 在处理寻找所有路径问题时易于理解和编码，也更容易进行调试和优化。
  
• 适应不同图结构：
  DFS 对图的结构没有严格要求，无论是有向图还是无向图，连通图还是非连通图，都可以使用 DFS 来寻找所有路径。它能够根据图的实际结构和连接关系，自适应地进行路径搜索，具有很强的通用性和灵活性，能够适应各种复杂的图数据结构和路径寻找需求。
  
• 深度优先特性利于路径搜索：
  DFS 的深度优先特性使得它在搜索路径时，能够快速深入到图的内部，优先探索那些可能通向目标的较长路径。这种特性在一些需要寻找最长路径或特定长度路径的问题中非常有用，能够更快地找到符合条件的路径，并且在探索过程中可以根据需要及时调整搜索策略，提高搜索效率。
  
• BFS
  BFS常用来寻找最短路径
  

为什么BFS常用来寻找最短路径?

广度优先搜索（BFS）常用来寻找最短路径，主要是基于其层序遍历特性、路径搜索的均匀扩展、距离计算的准确性、对复杂图的适应性以及实现的简便性等原因。

• 层序遍历特性：
  BFS 从起始节点开始，按照层的顺序逐层向外扩展搜索。这意味着它会先访问距离起始节点最近的一层节点，然后再逐步向外扩展到更远的层。这种遍历方式能够保证在找到目标节点时，所经过的路径一定是最短路径，因为它是按照距离递增的顺序进行搜索的。
  
• 路径搜索均匀扩展：
  BFS 在搜索过程中，会以起始节点为中心，像水波一样均匀地向四周扩展搜索。它不会像深度优先搜索那样沿着一条路径深入下去，而是同时探索所有可能的方向，并且优先探索距离起始节点较近的区域。这样可以确保不会错过任何更短的路径，能够全面且有序地搜索到所有可能的路径，从而找到最短路径。
  
• 距离计算准确：
  在 BFS 的搜索过程中，可以很方便地记录每个节点到起始节点的距离。通过在遍历过程中维护一个距离标记数组，每当访问到一个新的节点时，就可以根据其前驱节点的距离来更新它到起始节点的距离。这样，当找到目标节点时，就能够准确地得到从起始节点到目标节点的最短距离，以及对应的最短路径。
  
• 适应复杂图结构：
  BFS 对图的结构适应性强，无论是有向图还是无向图，稀疏图还是稠密图，都能有效地工作。它能够根据图的实际连接关系，按照层序规则进行搜索，不受图的具体结构和节点分布的影响，始终能够找到最短路径。这使得 BFS 在处理各种不同类型的图数据结构时，都能成为寻找最短路径的可靠算法。
  
• 实现简单高效：
  BFS 的实现通常使用队列（Queue）来辅助，将待访问的节点加入队列，按照先进先出的原则进行访问。这种实现方式相对简单直观，代码实现难度较低，而且在执行过程中效率较高。它不需要像一些其他复杂算法那样进行大量的计算和比较，就能够快速地找到最短路径，因此在实际应用中被广泛采用
  

多叉树

多叉树本质是二叉树的衍生，每个节点可以有多个子节点，而不仅仅是两个。常见有三叉树，四叉树，B树，字典树等。
相对于普通的二叉树遍历，多叉树遍历唯一的区别就是少了中序遍历，这个也好理解，多个节点，中序的位置是无法定义的。

1.     /// <summary>
2.     /// 多叉树
3.     /// </summary>
4.     public class MultipleTree
5.     {
6.         public int Value { get; set; }
7.         public List<MultipleTree> ChildrenTree { get; set; }
8.     }
10.     /// <summary>
11.     /// 二叉树
12.     /// </summary>
13.     public class BinnaryTree
14.     {
15.         public int Value { get; set; }
16.         public BinnaryTree Left { get; set; }
17.         public BinnaryTree Right { get; set; }
18.     }

复制代码

多叉树遍历

点击查看代码

1.     /// <summary>
2.     /// 多叉树
3.     /// </summary>
4.     public class MultipleTree
5.     {
6.         public int Value { get; set; }
7.         public List<MultipleTree> ChildrenTree { get; set; }
8.         public int State { get; set; }
9.         public MultipleTree(int value)
10.         {
11.             Value = value;
12.         }
15.         public static MultipleTree Created()
16.         {
17.             var root = new MultipleTree(1);
18.             root.ChildrenTree = new List<MultipleTree>()
19.             {
20.                 new MultipleTree(2)
21.                 {
22.                     ChildrenTree=new List<MultipleTree>()
23.                     {
24.                         new MultipleTree(5),
25.                         new MultipleTree(6),
26.                         new MultipleTree(7)
27.                     }
28.                 },
29.                 new MultipleTree(3)
30.                 {
31.                     ChildrenTree=new List<MultipleTree>()
32.                     {
33.                         new MultipleTree(8),
34.                         new MultipleTree(9),
35.                     }
36.                 },
37.                 new MultipleTree(4)
38.                 {
39.                     ChildrenTree=new List<MultipleTree>()
40.                     {
41.                         new MultipleTree(10),
42.                         new MultipleTree(11),
43.                         new MultipleTree(12),
44.                     }
45.                 }
46.             };
47.             return root;
48.         }
50.         public static void Run()
51.         {
52.             var tree = Created();
53.             TreverseBFS_Depth_State(tree);
54.         }
56.         /// <summary>
57.         /// DFS
58.         /// </summary>
59.         /// <param name="tree"></param>
60.         public static void TreverseDFS(MultipleTree tree)
61.         {
62.             //前序遍历
63.             Console.WriteLine(tree.Value);
65.             if (tree.ChildrenTree != null)
66.             {
67.                 foreach (var child in tree.ChildrenTree)
68.                 {
69.                     TreverseDFS(child);
70.                 }
71.             }
73.             //后续遍历
74.             Console.WriteLine(tree.Value);
75.         }
77.         /// <summary>
78.         /// BFS
79.         /// </summary>
80.         /// <param name="tree"></param>
81.         public static void TreverseBFS(MultipleTree tree)
82.         {
83.             var queue=new Queue<MultipleTree>();
84.             queue.Enqueue(tree);
86.             while (queue.Count > 0)
87.             {
88.                 var node = queue.Dequeue();
89.                 Console.WriteLine(node.Value);
91.                 if (node.ChildrenTree == null)
92.                 {
93.                     continue;
94.                 }
96.                 foreach (var child in node.ChildrenTree)
97.                 {
98.                     queue.Enqueue(child);
99.                 }
100.             }
101.         }
103.         /// <summary>
104.         /// BFS Depth
105.         /// </summary>
106.         /// <param name="tree"></param>
107.         public static void TreverseBFS_Depth(MultipleTree tree)
108.         {
109.             var queue = new Queue<MultipleTree>();
110.             queue.Enqueue(tree);
111.             var depth = 1;
113.             while (queue.Count > 0)
114.             {
115.                 var size = queue.Count;
118.                 for (var i = 0; i < size; i++)
119.                 {
120.                     var node = queue.Dequeue();
121.                     Console.WriteLine($"value={node.Value},depth={depth}");
123.                     if (node.ChildrenTree == null)
124.                     {
125.                         continue;
126.                     }
127.                     foreach( var child in node.ChildrenTree)
128.                     {
129.                         queue.Enqueue(child);
130.                     }
131.                 }
132.                 depth++;
133.             }
134.         }
135.         /// <summary>
136.         /// BFS Depth State
137.         /// </summary>
138.         /// <param name="tree"></param>
139.         public static void TreverseBFS_Depth_State(MultipleTree tree)
140.         {
141.             var queue = new Queue<MultipleTree>();
142.             var depth = 1;
143.             tree.State = depth;
144.             queue.Enqueue(tree);
146.             while (queue.Count > 0)
147.             {
148.                 var node= queue.Dequeue();
149.                 Console.WriteLine($"value={node.Value},depth={node.State}");
151.                 if (node.ChildrenTree == null)
152.                 {
153.                     continue;
154.                 }
156.                 foreach ( var child in node.ChildrenTree)
157.                 {
158.                     child.State = node.State + 1;
159.                     queue.Enqueue(child);
160.                 }
161.             }
162.         }
163.     }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！