自动做图在线网站,腾讯云服务器 学生,建站网站加盟,上海做网站哪家便宜二叉树之遍历 二叉树遍历遍历分类前序遍历流程描述代码实现 中序遍历流程描述代码实现 后序遍历流程描述代码实现 层次遍历流程描述代码实现 总结 二叉树遍历
遍历分类
遍历二叉树的思路有 4 种#xff0c;分别是#xff1a;
前序遍历二叉树#xff0c;有递归和非递归两种… 二叉树之遍历 二叉树遍历遍历分类前序遍历流程描述代码实现 中序遍历流程描述代码实现 后序遍历流程描述代码实现 层次遍历流程描述代码实现 总结 二叉树遍历
遍历分类
遍历二叉树的思路有 4 种分别是
前序遍历二叉树有递归和非递归两种方式中序遍历二叉树有递归和非递归两种方式后序遍历二叉树有递归和非递归两种方式层次遍历二叉树
前序遍历
流程描述
所谓前序遍历二叉树指的是从根结点出发按照以下步骤访问二叉树的每个结点
访问当前结点进入当前结点的左子树以同样的步骤遍历左子树中的结点遍历完当前结点的左子树后再进入它的右子树以同样的步骤遍历右子树中的结点
举个简单的例子下图是一棵二叉树 前序遍历这棵二叉树的过程是
访问根节点 1
进入 1 的左子树执行同样的步骤访问结点 2进入 2 的左子树执行同样的步骤访问结点 4结点 4 没有左子树结点 4 没有右子树进入 2 的右子树执行同样的步骤访问结点 5结点 5 没有左子树结点 5 没有右子树
进入 1 的右子树执行同样的步骤访问结点 3进入 3 的左子树执行同样的步骤访问结点 6结点 6 没有左子树结点 6 没有右子树进入 3 的右子树执行同样的步骤访问结点 7结点 7 没有左子树结点 7 没有右子树 经过以上过程就访问了二叉树中的各个结点访问的次序是 1 2 4 5 3 6 7 代码实现
/*** 前序遍历- 递归实现* 访问当前结点* 进入当前结点的左子树以同样的步骤遍历左子树中的结点* 遍历完当前结点的左子树后再进入它的右子树以同样的步骤遍历右子树中的结点* param treeNode*/public static void preTraverseForRecursion(TreeNode treeNode){if (treeNode ! null){// 访问当前节点printTreeNode(treeNode);// 访问当前节点的左子节点preTraverseForRecursion(treeNode.left);// 访问当前节点的右子节点preTraverseForRecursion(treeNode.right);}}/*** 前序遍历- 非递归实现* 众所周知递归实现无非是使用了栈结构来实现的压栈出栈所以非是递归实现前序遍历就是自己实现栈* 访问当前结点* 进入当前结点的左子树以同样的步骤遍历左子树中的结点* 遍历完当前结点的左子树后再进入它的右子树以同样的步骤遍历右子树中的结点* param treeNode*/public static void preTraverseForNoRecursion(TreeNode treeNode){TreeNode curr treeNode;TreeNodeStack stack new TreeNodeStack();while (curr ! null || !stack.isEmpty()){if (curr ! null){// 访问当前节点printTreeNode(curr);stack.push(curr);curr curr.left;}else {TreeNode pop stack.pop();curr pop.right;}}}/*** 树节点栈*/
Data
public class TreeNodeStack {private int top -1;private TreeNode[] stack new TreeNode[10];public boolean isEmpty(){return top 0;}/*** 入栈* param treeNode*/public void push(TreeNode treeNode){top;stack[top] treeNode;}/*** 出栈* return*/public TreeNode pop(){if (top 0){return null;}TreeNode treeNode stack[top];top--;return treeNode;}
}中序遍历
流程描述
二叉树的中序遍历指的是从根结点出发按照以下步骤访问二叉树中的每个结点
先进入当前结点的左子树以同样的步骤遍历左子树中的结点访问当前结点最后进入当前结点的右子树以同样的步骤遍历右子树中的结点。 中序遍历这棵二叉树的过程是
进入结点 1 的左子树访问左子树中的结点进入结点 2 的左子树访问左子树中的结点试图进入结点 4 的左子树但该结点没有左子树访问结点 4试图进入结点 4 的右子树但该结点没有右子树访问结点 2进入结点 2 的右子树访问右子树中的结点试图进入结点 5 的左子树但该结点没有左子树访问结点 5试图进入结点 5 的右子树但该结点没有右子树
访问结点 1
进入结点 1 的右子树访问右子树中的结点进入结点 3 的左子树访问左子树中的结点试图进入结点 6 的左子树但该结点没有左子树访问结点 6试图进入结点 6 的右子树但该结点没有右子树访问结点 3进入结点 3 的右子树访问右子树中的结点试图进入结点 7 的左子树但该结点没有左子树访问结点 7试图进入结点 7 的右子树但该结点没有右子树最终中序遍历图 1 中的二叉树访问各个结点的顺序是 4 2 5 1 6 3 7 代码实现
/*** 中序遍历-递归实现* 二叉树的中序遍历指的是从根结点出发按照以下步骤访问二叉树中的每个结点* 1. 先进入当前结点的左子树以同样的步骤遍历左子树中的结点* 2. 访问当前结点* 3. 最后进入当前结点的右子树以同样的步骤遍历右子树中的结点。* param treeNode*/public static void inTraverseForRecursion(TreeNode treeNode){if (treeNode ! null){// 递归-当问当前节点的左子节点inTraverseForRecursion(treeNode.left);// 访问当前节点printTreeNode(treeNode);// 递归-访问当前节点的右子节点inTraverseForRecursion(treeNode.right);}}/*** 中序遍历-非递归实现* 二叉树的中序遍历指的是从根结点出发按照以下步骤访问二叉树中的每个结点* 1. 先进入当前结点的左子树以同样的步骤遍历左子树中的结点* 2. 访问当前结点* 3. 最后进入当前结点的右子树以同样的步骤遍历右子树中的结点。* param treeNode*/public static void inTraverseForNoRecursion(TreeNode treeNode){TreeNode curr treeNode;TreeNodeStack stack new TreeNodeStack();while (curr ! null || !stack.isEmpty()){if (curr ! null){// 入栈顺序1, 2, 4,stack.push(curr);curr curr.left;}else {// 出栈顺序4 2 1TreeNode pop stack.pop();printTreeNode(pop);// 然后访问右节点curr pop.right;}}}后序遍历
流程描述
后序遍历二叉树指的是从根结点出发按照以下步骤访问树中的每个结点
优先进入当前结点的左子树以同样的步骤遍历左子树中的结点如果当前结点没有左子树则进入它的右子树以同样的步骤遍历右子树中的结点直到当前结点的左子树和右子树都遍历完后才访问该结点。
以下图所示的二叉树为例 后序遍历这棵二叉树的过程是
从根节点 1 出发进入该结点的左子树进入结点 2 的左子树遍历左子树中的结点进入结点 4 的左子树但该结点没有左孩子进入结点 4 的右子树但该结点没有右子树访问结点 4进入结点 2 的右子树遍历右子树中的结点进入结点 5 的左子树但该结点没有左孩子进入结点 5 的右子树但该结点没有右孩子访问结点 5访问结点 2
进入结点 1 的右子树遍历右子树中的结点进入结点 3 的左子树遍历左子树中的结点进入结点 6 的左子树但该结点没有左孩子进入结点 6 的右子树但该结点没有右子树访问结点 6进入结点 3 的右子树遍历右子树中的结点进入结点 7 的左子树但该结点没有左孩子进入结点 7 的右子树但该结点没有右孩子访问结点 7访问结点 3
访问结点 1。最终后序遍历图 1 中的二叉树访问各个结点的顺序是 4 5 2 6 7 3 1 代码实现 /*** 后序遍历-递归实现* 后序遍历二叉树指的是从根结点出发按照以下步骤访问树中的每个结点* 1. 优先进入当前结点的左子树以同样的步骤遍历左子树中的结点* 2. 如果当前结点没有左子树则进入它的右子树以同样的步骤遍历右子树中的结点* 3. 直到当前结点的左子树和右子树都遍历完后才访问该结点。* param treeNode*/public static void postTraverseForRecursion(TreeNode treeNode){if (treeNode ! null){// 递归-当问当前节点的左子节点postTraverseForRecursion(treeNode.left);// 递归-访问当前节点的右子节点postTraverseForRecursion(treeNode.right);// 访问当前节点printTreeNode(treeNode);}}/*** 后序遍历-非递归实现* 后序遍历二叉树指的是从根结点出发按照以下步骤访问树中的每个结点* 1. 优先进入当前结点的左子树以同样的步骤遍历左子树中的结点* 2. 如果当前结点没有左子树则进入它的右子树以同样的步骤遍历右子树中的结点* 3. 直到当前结点的左子树和右子树都遍历完后才访问该结点。** 4, 5, 2, 6, 7, 3, 1* param treeNode*/public static void postTraverseForNoRecursion(TreeNode treeNode){TreeNode curr treeNode;LinkedListTreeNode stack new LinkedList();// 定义最后一次出栈节点防止陷入重复执行TreeNode pop null;while (curr ! null || !stack.isEmpty()){if (curr ! null){stack.push(curr);curr curr.left;}else {// peek方法是查询栈顶数据但是不弹出TreeNode last stack.peek();// last.right pop 如果相等那就说明已经执行过该右子节点了这个条件是防止有右子节点的数据陷入死循环中if (last.right null || last.right pop){pop stack.pop();printTreeNode(pop);}else {curr last.right;}}}}层次遍历
流程描述 上面这棵树一共有 3 层根结点位于第一层以此类推。
所谓层次遍历二叉树就是从树的根结点开始一层一层按照从左往右的次序依次访问树中的结点。
层次遍历用阻塞队列存储的二叉树可以借助队列存储结构实现具体方案是
将根结点入队从队列的头部提取一个结点并访问它将该结点的左孩子和右孩子依次入队重复执行第 2 步直至队列为空
假设将图 1 中的二叉树存储到链表中那么层次遍历的过程是
根结点 1 入队1
根结点 1 出队并访问它然后将 1 的左孩子 2 和右孩子 3 依次入队3, 2
将结点 2 出队并访问它然后将 2 的左孩子 4 和右孩子 5 依次入队5,4,3
将结点 3 出队并访问它然后将 3 的左孩子 6 和右孩子 7 依次入队7,6,5,4
根结点 4 出队并访问它然后将 4 的左孩子无和右孩子无依次入队7,6,5
将结点 5 出队并访问它然后将 5 的左孩子无和右孩子无依次入队7,6
将结点 6 出队并访问它然后将 6 的左孩子无和右孩子无依次入队7
将结点 7 出队并访问它然后将 6 的左孩子无和右孩子无依次入队
队列为空层次遍历结束最终后序遍历图 1 中的二叉树访问各个结点的顺序是 1 2 3 4 5 6 7 代码实现 /*** 层次遍历* 所谓层次遍历二叉树就是从树的根结点开始一层一层按照从左往右的次序依次访问树中的结点。* 1. 将根结点入队* 2. 从队列的头部提取一个结点并访问它将该结点的左孩子和右孩子依次入队* 3. 重复执行第 2 步直至队列为空* param treeNode*/public static void levelTraverseForRecursion(TreeNode treeNode){if (treeNode ! null){LinkedBlockingQueueTreeNode queue new LinkedBlockingQueue(10);queue.offer(treeNode);doPushQueue(queue);}}/*** 使用阻塞队列实现二叉树层次遍历* 阻塞队列的特点就是先进先出* param nowQueue*/private static void doPushQueue(LinkedBlockingQueueTreeNode nowQueue){if (nowQueue.isEmpty()){return;}// 从阻塞队列中弹出TreeNode poll nowQueue.poll();while (poll ! null){printTreeNode(poll);// 如果左子节点不为null, 则入队列if (poll.left ! null){nowQueue.offer(poll.left);}// 如果右子节点不为null, 则入队列if (poll.right ! null){nowQueue.offer(poll.right);}// 从阻塞队列中弹出poll nowQueue.poll();}}总结
总结各个遍历类型的流程 前序遍历根节点 - 左节点 - 右节点 中序遍历左节点 - 根节点 - 右节点 后序遍历左节点 - 右节点 - 根节点 层次遍历从根节点开始一层一层的遍历左节点-右节点
