二叉树——深度、广度优先遍历
二叉树遍历一般都会使用深度遍历或者广度遍历。那什么是深度与广度遍历呢？
打个比方，在走迷宫的时候，有很多分岔口，深度遍历的方式就是，一直往左岔口走，走到头了，到上一个岔口的另一个岔口再走。广度遍历就是再分岔口的时候，变出很多个分身，每个分身走一个岔口。
在二叉树中深度遍历有3种方式：
有前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
广度遍历也叫层次遍历：将树按一层层的规律来遍历，一般依靠队列来使用。
01
—
Code
public class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null){this.val = val;this.left = left;this.right = right;}}/// <summary>/// 深度优先——前序遍历/// </summary>/// <param name="root"></param>public void DFS_preOrderTraverse1(TreeNode root){if (root != null){Console.WriteLine(root.val + " ");DFS_preOrderTraverse1(root.left);DFS_preOrderTraverse1(root.right);}}/// <summary>/// 深度优先——中序遍历/// </summary>/// <param name="root"></param>public void DFS_inOrderTraverse1(TreeNode root){if (root != null){DFS_inOrderTraverse1(root.left);Console.WriteLine(root.val + " ");DFS_inOrderTraverse1(root.right);}}/// <summary>/// 深度优先——后序遍历/// </summary>/// <param name="root"></param>public void DFS_postOrderTraverse1(TreeNode root){if (root != null){DFS_postOrderTraverse1(root.left);DFS_postOrderTraverse1(root.right);Console.WriteLine(root.val + " ");}}/// <summary>/// 广度优先/// </summary>/// <param name="root"></param>public void BFS_levelTraverse(TreeNode root){if (root == null){return;}Queue<TreeNode> queue = new Queue<TreeNode>();queue.Enqueue(root);while (queue.Peek()!=null){TreeNode node = queue.Dequeue();Console.WriteLine(node.val + "");if (node.left != null){queue.Enqueue(node.left);}if (node.right != null){queue.Enqueue(node.right);}}}
END
感谢阅读
你知道的越多，你不知道的越多
我是EAST
一个靠互联网苟且偷生的程序员
咱们下期见！
扫描二维码关注我吧