二叉树的深度优先遍历和广度优先遍历 àì夳堔傛蜴生んèń 2022-02-02 05:31 273阅读 0赞 深度优先遍历:前序遍历,中序遍历,后序遍历 广度优先遍历:层次遍历 定义二叉树node节点: public class TreeNode { private int data; private TreeNode right,left; public int getData() { return data; } public void setData(int data) { this.data = data; } public TreeNode getRight() { return right; } public void setRight(TreeNode right) { this.right = right; } public TreeNode getLeft() { return left; } public void setLeft(TreeNode left) { this.left = left; } public TreeNode(int data) { this.data = data; } } 二叉树遍历方法: public class TreeNodeDemo { public static void main(String[] args) { TreeNode node1 = new TreeNode(1); TreeNode node2 = new TreeNode(2); TreeNode node3 = new TreeNode(3); TreeNode node4 = new TreeNode(4); TreeNode node5 = new TreeNode(5); TreeNode node6 = new TreeNode(6); TreeNode node7 = new TreeNode(7); TreeNode node8 = new TreeNode(8); node1.setLeft(node2); node1.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node5.setLeft(node7); node5.setRight(node8); node3.setLeft(node6); preOrderRecur(node1); System.out.println(); preOrderUnRecur(node1); System.out.println(); inOrderRecur(node1); System.out.println(); inOrderUnRecur(node1); System.out.println(); posOrderRecur(node1); System.out.println(); posOrderUnRecur(node1); System.out.println(); levelTraverse(node1); } /** * 递归前序遍历 根-左-右 * * @param head */ public static void preOrderRecur(TreeNode head) { if (head == null) { return; } System.out.print(head.getData() + " "); preOrderRecur(head.getLeft()); preOrderRecur(head.getRight()); } /** * 非递归前序遍历 栈实现 * 反着顺序,pop出栈先进后出 * 1、先放中节点 * 2、有右节点放右节点 * 3、有左节点放左节点 * * @param head */ public static void preOrderUnRecur(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.add(head); while (!stack.isEmpty()) { TreeNode pop = stack.pop(); System.out.print(pop.getData() + " "); if (pop.getRight() != null) { stack.add(pop.getRight()); } if (pop.getLeft() != null) { stack.add(pop.getLeft()); } } } /** * 递归中序遍历 左-根-右 * * @param head */ public static void inOrderRecur(TreeNode head) { if (head == null) { return; } inOrderRecur(head.getLeft()); System.out.print(head.getData() + " "); inOrderRecur(head.getRight()); } /** * 非递归中序遍历 栈实现 * 1、左节点不为null则压入左节点 * 2、左节点为null时,pop并打印左节点 * 3、再往右,右节点为null时,pop并打印 * 4、右节点不为null时,压入右节点 * * @param head */ public static void inOrderUnRecur(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || head != null) { if (head != null) { stack.add(head); head = head.getLeft(); } else { head = stack.pop(); System.out.print(head.getData() + " "); head = head.getRight(); } } } /** * 递归后序遍历 左-右-根 * * @param head */ public static void posOrderRecur(TreeNode head) { if (head == null) { return; } posOrderRecur(head.getLeft()); posOrderRecur(head.getRight()); System.out.print(head.getData() + " "); } /** * 非递归后序遍历 栈实现 * 和前序遍历一样的只不过是使用了两个栈 * 1、在前序遍历的时候将 中 右 左 节点压栈 * 2、在原来是打印的地方不打印,将本该打印的节点压到第二个栈中 * 3、这样第二个栈的出栈顺序就是 左 右 中了 * * @param head */ public static void posOrderUnRecur(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.add(head); while (!stack1.isEmpty()) { head = stack1.pop(); stack2.add(head); if (head.getLeft() != null) { stack1.add(head.getLeft()); } if (head.getRight() != null) { stack1.add(head.getRight()); } } while (!stack2.isEmpty()) { System.out.print(stack2.pop().getData() + " "); } } /** * 层序遍历 队列实现 * 先进先出 * * @param head */ public static void levelTraverse(TreeNode head) { if (head == null) { return; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(head); while (!queue.isEmpty()) { TreeNode poll = queue.poll(); System.out.print(poll.getData() + " "); if (poll.getLeft() != null) { queue.add(poll.getLeft()); } if (poll.getRight() != null) { queue.add(poll.getRight()); } } } }
还没有评论,来说两句吧...