二叉树的概念

什么是二叉树？

每个结点最多只有两个结点的树称为二叉树，如下图所示

如果二叉树的所有叶子结点都在最后一层并且结点的总数=2^n-1，其中n为层数，则称其为满二叉树

如果该二叉树的所有叶子结点都在最后一层或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的也自己结点在右边连续，我们称为完全二叉树

二叉树的遍历

二叉树的遍历分为三种：

前序遍历：先输出父结点,再遍历左子树,再遍历右子树

中序遍历：先遍历左子树,再输出父结点,再遍历右子树

后序遍历：先遍历左子树,再遍历右子树,再输出父节点

小结：看父结点输出的顺序就能确定是前序还是中序后序,左子树的遍历一定再右子树前

代码实现

Node：模拟结点

/*** 模拟结点*/
public class Node {private int id;private String name;/*左节点*/private Node left;/*右节点*/private Node right;/*构造方法*/public Node(int id, String name) {this.id = id;this.name = name;}/*前序遍历*/public void preDisplay(){/*输出当前结点*/System.out.println(this);if (this.left != null) {/*如果当前结点的左子节点不为空就递归前序遍历左子树*/this.left.preDisplay();}if (this.right != null) {/*如果当前结点的右子节点不为空就递归前序遍历右子树*/this.right.preDisplay();}}/*中序遍历*/public void midDisplay(){if (this.left != null) {this.left.midDisplay();}System.out.println(this);if (this.right != null) {this.right.midDisplay();}}/*后序遍历*/public void postDisplay(){if (this.left != null) {this.left.postDisplay();}if (this.right != null) {this.right.postDisplay();}System.out.println(this);}setter and getter方法@Overridepublic String toString() {return "[" + "id=" + id + ", name='" + name  + ']';}
}

BinaryTree：模拟二叉树

public class BinaryTree {/*根结点*/private Node root;public void setRoot(Node root) {this.root = root;}/*前序遍历*/public void preShow(){if (this.root != null) {this.root.preDisplay();}else{System.out.println("二叉树为空");}}/*中序遍历*/public void midShow(){if (this.root != null){this.root.midDisplay();}else{System.out.println("二叉树为空");}}/*后序遍历*/public void postShow(){if (this.root != null) {this.root.postDisplay();}else{System.out.println("二叉树为空");}}
}

BinaryTreeTest ：测试类

public class BinaryTreeTest {public static void main(String[] args) {/*手动创建结点*/Node node1 = new Node(1,"张三");Node node2 = new Node(2,"李四");Node node3 = new Node(3,"王五");Node node4 = new Node(4,"赵六");node1.setLeft(node2);node1.setRight(node3);node3.setRight(node4);/*创建二叉树*/BinaryTree tree = new BinaryTree();tree.setRoot(node1);System.out.println("前序遍历：");tree.preShow();//1,2,3,4System.out.println("中序遍历：");tree.midShow();//2,1,3,4System.out.println("后序遍历：");tree.postShow();//2,4,3,1}
}

结果输出

前序遍历：
[id=1, name='张三]
[id=2, name='李四]
[id=3, name='王五]
[id=4, name='赵六]
中序遍历：
[id=2, name='李四]
[id=1, name='张三]
[id=3, name='王五]
[id=4, name='赵六]
后序遍历：
[id=2, name='李四]
[id=4, name='赵六]
[id=3, name='王五]
[id=1, name='张三]Process finished with exit code 0