二叉树遍历

遍历命名

根据访问结点操作发生位置命名： ① NLR：前序遍历(Preorder Traversal 亦称（先序遍历）） ——访问根结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(Inorder Traversal) ——访问根结点的操作发生在遍历其左右子树之中（间）。 ③ LRN：后序遍历(Postorder Traversal) ——访问根结点的操作发生在遍历其左右子树之后。 注意： 由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

 概念抄至百度百科：https://baike.baidu.com/item/二叉树遍历/9796049?fr=aladdin

 

Java代码实现：

public class BinaryTreeTraversal {/*** 1* 2 3* 4 5 6 7* 8 9 10 11 12 13 14 15** 前序 => 1|2|4|8|9|5|10|11|3|6|12|13|7|14|15|* 中序 => 8|4|9|2|10|5|11|1|12|6|13|3|14|7|15|* 后序 => 8|9|4|10|11|5|2|12|13|6|14|15|7|3|1|*/public static void main(String[] args) {Node n1 = new Node(1);BinaryTree binaryTree = new BinaryTree(n1);Node n2 = new Node(2);Node n3 = new Node(3);Node n4 = new Node(4);Node n5 = new Node(5);Node n6 = new Node(6);Node n7 = new Node(7);Node n8 = new Node(8);Node n9 = new Node(9);Node n10 = new Node(10);Node n11 = new Node(11);Node n12 = new Node(12);Node n13 = new Node(13);Node n14 = new Node(14);Node n15 = new Node(15);n1.setLeftSubNode(n2);n1.setRightSubNode(n3);n2.setLeftSubNode(n4);n2.setRightSubNode(n5);n3.setLeftSubNode(n6);n3.setRightSubNode(n7);n4.setLeftSubNode(n8);n4.setRightSubNode(n9);n5.setLeftSubNode(n10);n5.setRightSubNode(n11);n6.setLeftSubNode(n12);n6.setRightSubNode(n13);n7.setLeftSubNode(n14);n7.setRightSubNode(n15);binaryTree.preOrderTraversal();System.out.println("");binaryTree.inOrderTraversal();System.out.println("");binaryTree.postOrderTraversal();}public static class BinaryTree {private Node root;public void preOrderTraversal() {this.root.preOrderTraversal();}public void inOrderTraversal() {this.root.inOrderTraversal();}public void postOrderTraversal() {this.root.postOrderTraversal();}public BinaryTree(Node root) {this.root = root;}public Node getRoot() {return root;}public void setRoot(Node root) {this.root = root;}}public static class Node {private int id;private Node leftSubNode;private Node rightSubNode;public Node(int id) {this.id = id;}public int getId() {return id;}public void setId(int id) {this.id = id;}public Node getLeftSubNode() {return leftSubNode;}public void setLeftSubNode(Node leftSubNode) {this.leftSubNode = leftSubNode;}public Node getRightSubNode() {return rightSubNode;}public void setRightSubNode(Node rightSubNode) {this.rightSubNode = rightSubNode;}/*** NLR：前序遍历(Preorder Traversal 亦称（先序遍历））* 访问根结点的操作发生在遍历其左右子树之前。*/public void preOrderTraversal() {//NSystem.out.print(this);//Lif (this.leftSubNode != null) {this.leftSubNode.preOrderTraversal();}//Rif (this.rightSubNode != null) {this.rightSubNode.preOrderTraversal();}}/*** LNR：中序遍历(Inorder Traversal)* 访问根结点的操作发生在遍历其左右子树之中（间）。*/public void inOrderTraversal() {//Lif (this.leftSubNode != null) {this.leftSubNode.inOrderTraversal();}//NSystem.out.print(this);//Rif (this.rightSubNode != null) {this.rightSubNode.inOrderTraversal();}}/*** LRN：后序遍历(Postorder Traversal)* 访问根结点的操作发生在遍历其左右子树之后。*/public void postOrderTraversal() {//Lif (this.leftSubNode != null) {this.leftSubNode.postOrderTraversal();}//Rif (this.rightSubNode != null) {this.rightSubNode.postOrderTraversal();}//NSystem.out.print(this);}@Override public String toString() {return this.getId() + "|";}}}

 

转载于:https://www.cnblogs.com/sleepingDogs/p/11143957.html

总结

以上是生活随笔为你收集整理的BinaryTreeTraversal（二叉树遍历）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。