珠海培训网站建设,中介如何做网站收客,设计师 网站 贵,东莞寮步在哪里递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。
二叉树图 定义 前序遍历#xff08;Preorder Traversal#xff09;#xff1a; 前序遍历的顺序是先访问根节点#xff0c;然后按照先左后右的顺序访问子节点。对于上面的二叉树#xff0c;前序遍历的结果是…递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。
二叉树图 定义 前序遍历Preorder Traversal 前序遍历的顺序是先访问根节点然后按照先左后右的顺序访问子节点。对于上面的二叉树前序遍历的结果是4 - 2 - 1 - 3 - 6 - 5 - 7。 中序遍历Inorder Traversal 中序遍历的顺序是按照先左后根再右的顺序访问子节点。对于上面的二叉树中序遍历的结果是1 - 2 - 3 - 4 - 5 - 6 - 7。 后序遍历Postorder Traversal 后序遍历的顺序是按照先左后右再根的顺序访问子节点。对于上面的二叉树后序遍历的结果是1 - 3 - 2 - 5 - 7 - 6 - 4。
通俗易懂 如果上面的定义看着有点晕看这里如上图在这三个节点中观察根节点2的遍历位置
前序遍历213
中序遍历123
后序遍历132
总结不管哪个遍历方式左右相比都是左先1在前3在后根节点2依次是前、中、后递归时把子树看成整体逻辑同理。
代码
public class BinaryTree {public static void main(String[] args) {int[] nums {1, 2, 3, 4, 5, 6, 7};TreeNode root TreeNode.buildTree(nums);System.out.print(前序遍历递归);preorderTraversal(root);System.out.println();System.out.print(中序遍历递归);inorderTraversal(root);System.out.println();System.out.print(后序遍历递归);postorderTraversal(root);System.out.println();System.out.print(前序遍历栈);preorderTraversal1(root);System.out.println();System.out.print(中序遍历栈);inorderTraversal1(root);System.out.println();System.out.print(后序遍历栈);postorderTraversal1(root);System.out.println();}//前序遍历(递归)public static void preorderTraversal(TreeNode root) {if (root null) {return;}System.out.print(root.val ); // 访问根节点preorderTraversal(root.left); // 访问左子树preorderTraversal(root.right); // 访问右子树}// 中序遍历(递归)public static void inorderTraversal(TreeNode root) {if (root null) {return;}inorderTraversal(root.left); // 访问左子树System.out.print(root.val ); // 访问根节点inorderTraversal(root.right); // 访问右子树}// 后序遍历(递归)public static void postorderTraversal(TreeNode root) {if (root null) {return;}postorderTraversal(root.left); // 访问左子树postorderTraversal(root.right); // 访问右子树System.out.print(root.val ); // 访问根节点}// 前序遍历(栈)public static void preorderTraversal1(TreeNode root) {if (root null) {return;}StackTreeNode stack new Stack();stack.push(root);while (!stack.isEmpty()) {TreeNode node stack.pop();System.out.print(node.val ); // 打印当前节点的值if (node.right ! null) {stack.push(node.right); // 先将右子节点入栈}if (node.left ! null) {stack.push(node.left); // 再将左子节点入栈}}}// 中序遍历(栈)public static void inorderTraversal1(TreeNode root) {if (root null) {return;}StackTreeNode stack new Stack();TreeNode node root;while (node ! null || !stack.isEmpty()) {while (node ! null) {stack.push(node);node node.left; // 先将左子节点入栈}node stack.pop();System.out.print(node.val ); // 打印当前节点的值node node.right; // 再处理右子节点}}// 后序遍历(栈)public static void postorderTraversal1(TreeNode root) {if (root null) {return;}StackTreeNode stack1 new Stack();StackTreeNode stack2 new Stack();stack1.push(root);while (!stack1.isEmpty()) {TreeNode node stack1.pop();if (node.left ! null) {stack1.push(node.left); // 先将左子节点入栈}if (node.right ! null) {stack1.push(node.right); // 再将右子节点入栈}stack2.push(node); // 将当前节点入栈用于后序遍历}while (!stack2.isEmpty()) {System.out.print(stack2.pop().val ); // 打印栈中的节点值即后序遍历结果}}
}
TreeNode
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val x; }// 构建二叉树public static TreeNode buildTree(int[] nums) {if (nums null || nums.length 0) {return null;}return buildTree(nums, 0, nums.length - 1);}private static TreeNode buildTree(int[] nums, int left, int right) {if (left right) {return null;}int mid (left right) / 2;TreeNode root new TreeNode(nums[mid]);root.left buildTree(nums, left, mid - 1);root.right buildTree(nums, mid 1, right);return root;}
} 运行结果 前序遍历递归4 2 1 3 6 5 7 中序遍历递归1 2 3 4 5 6 7 后序遍历递归1 3 2 5 7 6 4 前序遍历栈4 2 1 3 6 5 7 中序遍历栈1 2 3 4 5 6 7 后序遍历栈1 3 2 5 7 6 4
