遍历二叉树
二叉树定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public interface ITreeNode<T>
{
public TreeNode<T> Left { get; set; }
public TreeNode<T> Right { get; set; }
}
public class TreeNode<T> : ITreeNode<T>
{
public T Data { get; set; }
public TreeNode<T> Left { get; set; }
public TreeNode<T> Right { get; set; }
public int Deep { get; set; }
public override string ToString()
{
return $"Data:{Data},Deep:{Deep}";
}
}
测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void Main()
{
var tree = new TreeNode<string>
{
Data = "1",
Deep = 1,
Left = new TreeNode<string>
{
Data = "2",
Deep = 2,
Left = new TreeNode<string>
{
Data = "4",
Deep = 3,
},
Right = new TreeNode<string>
{
Data = "5",
Deep = 3
},
},
Right = new TreeNode<string>
{
Data = "3",
Deep = 2,
Left = new TreeNode<string>
{
Data = "6",
Deep = 3,
},
Right = new TreeNode<string>
{
Data = "7",
Deep = 3
},
},
};
var list = new List<ITreeNode<string>>();
Loop(tree, n => { list.Add(n); n.ToString().Dump(); });
tree.Dump();
list.Count().Dump();
}
广度优先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Loop<T>(ITreeNode<T> tree, Action<ITreeNode<T>> loopAction)
{
var list = new List<ITreeNode<T>>() { tree };
while (list.Any())
{
var newList = new List<ITreeNode<T>>();
foreach (var element in list)
{
if (element.Left != null)
{
newList.Add(element.Left);
}
if (element.Right != null)
{
newList.Add(element.Right);
}
loopAction?.Invoke(element);
}
list = newList;
}
}
深度优先
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
void Loop<T>(ITreeNode<T> tree, Action<ITreeNode<T>> loopAction)
{
loopAction?.Invoke(tree);
if (tree?.Left != null)
{
Loop(tree.Left, loopAction);
}
if (tree?.Right != null)
{
Loop(tree.Right, loopAction);
}
}
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
void Loop<T>(ITreeNode<T> tree, Action<ITreeNode<T>> loopAction)
{
if (tree?.Left != null)
{
Loop(tree.Left, loopAction);
}
loopAction?.Invoke(tree);
if (tree?.Right != null)
{
Loop(tree.Right, loopAction);
}
}
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
void Loop<T>(ITreeNode<T> tree, Action<ITreeNode<T>> loopAction)
{
loopAction?.Invoke(tree);
if (tree?.Left != null)
{
Loop(tree.Left, loopAction);
}
if (tree?.Right != null)
{
Loop(tree.Right, loopAction);
}
loopAction?.Invoke(tree);
}
参考资料
本文会经常更新，请阅读原文： https://dashenxian.github.io/post/%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91 ，以避免陈旧错误知识的误导，同时有更好的阅读体验。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。欢迎转载、使用、重新发布，但务必保留文章署名 小神仙 （包含链接： https://dashenxian.github.io ），不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请 与我联系 (125880321@qq.com) 。