数据结构——二叉树(递归与非递归遍历)

xiaoxiao2021-02-28  5

二叉树的递归遍历

首先定义我们的二叉树的节点结构,节点包括数据,左节点,右节点。

class Node { private Object data; private Node left; private Node right; public Node(Object data) { this.data = data; } public Object getData() { return data; } public Object setData(Object data) { return this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } }

先序遍历

先输出根节点,然后输出左节点,右节点。对于每个节点都是按照这个规律进行的。

// 先序遍历 public void preOrder(Node root) { if (root != null) { System.out.print(root.getData() + ","); preOrder(root.getLeft()); preOrder(root.getRight()); } }

中序遍历

先输出左节点,然后是根节点,最后是右节点。

// 中序遍历 public void inOrder(Node root) { if (root != null) { inOrder(root.getLeft()); System.out.print(root.getData() + ","); inOrder(root.getRight()); } }

后序遍历

先输出左节点,右节点,最后输出根节点

// 后序遍历 public void postOrder(Node root) { if (root != null) { postOrder(root.getLeft()); postOrder(root.getRight()); System.out.print(root.getData() + ","); } }

二叉树的非递归遍历

非递归先序遍历

// 非递归先序遍历 public void preOrder2(Node root) { Stack<Object> stack = new Stack<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { Node T = (Node) stack.pop(); System.out.print(T.getData() + ","); while (T != null) { if (T.getLeft() != null) { System.out.print(T.getLeft().getData() + ","); } if (T.getRight() != null) { stack.push(T.getRight()); } // 遍历左子树 T = T.getLeft(); } } }

非递归中序遍历

// 非递归中序遍历 public void midOrder2(Node root) { Node T = root; Stack<Node> stack = new Stack<>(); if (T != null) { stack.push(T); while (!stack.isEmpty()) { while (stack.peek() != null) {// 用于判断是否被访问过 stack.push(stack.peek().getLeft()); } stack.pop();// null出栈 if (!stack.isEmpty()) { T = stack.pop(); System.out.print(T.getData()+","); //放入右子树 stack.push(T.getRight()); } } } }

非递归后序遍历

//非递归后序遍历 public void postOrder2(Node root){ Node T = root; if (T!=null) { Stack<Node> stack = new Stack<>(); stack.push(T); boolean flag = false;//false未访问,true访问 Node P = null;//指向刚访问过的节点 while(!stack.isEmpty()){ while (stack.peek()!=null) {//循环遍历左子树 stack.push(stack.peek().getLeft()); } stack.pop();//null出栈 while(!stack.isEmpty()){ T = stack.peek(); if (T.getRight()==null||T.getRight()==P) {//当右子树为空或者访问过,输出 System.out.print(T.getData()+","); stack.pop(); flag = true; P = T; }else {//右子树入栈,循环遍历 stack.push(T.getRight()); flag = false; } if (!flag) { break;//未访问节点,跳出循环,去访问左右子树 } } } } }

完整代码

import java.util.Stack; class Node { private Object data; private Node left; private Node right; public Node(Object data) { this.data = data; } public Object getData() { return data; } public Object setData(Object data) { return this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } } public class Tree { public static void main(String[] args) { Node node = new Node("A"); Node node2 = new Node("B"); node.setLeft(node2); node2.setLeft(new Node("D")); node.setRight(new Node("C")); Tree tree = new Tree(); System.out.println("先序遍历"); tree.preOrder(node); System.out.println("\n中序遍历"); tree.inOrder(node); System.out.println("\n后序遍历"); tree.postOrder(node); System.out.println("\n非递归先序遍历"); tree.preOrder2(node); System.out.println("\n非递归中序遍历"); tree.midOrder2(node); System.out.println("\n非递归后序遍历"); tree.postOrder2(node); } // 先序遍历 public void preOrder(Node root) { if (root != null) { System.out.print(root.getData() + ","); preOrder(root.getLeft()); preOrder(root.getRight()); } } // 中序遍历 public void inOrder(Node root) { if (root != null) { inOrder(root.getLeft()); System.out.print(root.getData() + ","); inOrder(root.getRight()); } } // 后序遍历 public void postOrder(Node root) { if (root != null) { postOrder(root.getLeft()); postOrder(root.getRight()); System.out.print(root.getData() + ","); } } /*********************** 非递归算法 ********************************/ // 非递归先序遍历 public void preOrder2(Node root) { Stack<Object> stack = new Stack<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { Node T = (Node) stack.pop(); System.out.print(T.getData() + ","); while (T != null) { if (T.getLeft() != null) { System.out.print(T.getLeft().getData() + ","); } if (T.getRight() != null) { stack.push(T.getRight()); } // 遍历左子树 T = T.getLeft(); } } } // 非递归中序遍历 public void midOrder2(Node root) { Node T = root; Stack<Node> stack = new Stack<>(); if (T != null) { stack.push(T); while (!stack.isEmpty()) { while (stack.peek() != null) {// 用于判断是否被访问过 stack.push(stack.peek().getLeft()); } stack.pop();// null出栈 if (!stack.isEmpty()) { T = stack.pop(); System.out.print(T.getData()+","); //放入右子树 stack.push(T.getRight()); } } } } //非递归后序遍历 public void postOrder2(Node root){ Node T = root; if (T!=null) { Stack<Node> stack = new Stack<>(); stack.push(T); boolean flag = false;//false未访问,true访问 Node P = null;//指向刚访问过的节点 while(!stack.isEmpty()){ while (stack.peek()!=null) {//循环遍历左子树 stack.push(stack.peek().getLeft()); } stack.pop();//null出栈 while(!stack.isEmpty()){ T = stack.peek(); if (T.getRight()==null||T.getRight()==P) {//当右子树为空或者访问过,输出 System.out.print(T.getData()+","); stack.pop(); flag = true; P = T; }else {//右子树入栈,循环遍历 stack.push(T.getRight()); flag = false; } if (!flag) { break;//未访问节点,跳出循环,去访问左右子树 } } } } } }

输出结果

先序遍历 A,B,D,C, 中序遍历 D,B,A,C, 后序遍历 D,B,C,A, 非递归先序遍历 A,B,D,C, 非递归中序遍历 D,B,A,C, 非递归后序遍历 D,B,C,A,
转载请注明原文地址: https://www.6miu.com/read-250217.html

最新回复(0)