大话数据结构十三：二叉树的特点和遍历（前序，中序，后序）

1. 关于树

① 树的度 — 也即是宽度，简单地说，就是结点的分支数。

② 树的深度 — 组成该树各结点的最大层次。

③ 森林 — 指若干棵互不相交的树的集合。

④ 有序树 — 指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

2. 二叉树的特点

i、每个结点最多有两颗子树

ii、左子树和右子树是有顺序的，次序不能任意颠倒

iii、即使树中某结点只有一颗子树，也要区分它是左子树还是右子树

3. 二叉树五种形态

① 空二叉树

② 只有一个根结点

③ 根结点只有左子树

④ 根结点只有右子树

⑤ 根结点既有左子树又有右子树

4. 特殊的二叉树

① 斜树：所有的结点都只有左子树的二叉树叫左斜树，所有的结点都只有右子树的二叉树叫右斜树，这两者统称为斜树。

② 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

③ 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i (1<=i<=n) 的结点与同样深度的满二叉树中编号为i的结点位置完全相同，则这棵二叉树称为完全二叉树。

下图中不是完全二叉树，因为5没有左右子树：

5. 二叉树的转换

将树转换为二叉树的步骤如下：

① 加线：所有兄弟节点之间加线

② 去线：保留树中每个结点与它第一个孩子的连线，删除其与其他孩子的连线

③ 层次调整：以根结点为轴心，将整棵树旋转，使之层次分明。

6. 二叉树的遍历(Java实现)

public class BinaryTree {private Node root; // 根节点/** * 内部节点类 */private class Node {private Node left; // 左节点private Node right; // 右节点private int data;public Node(int data) {this.left = null;this.right = null;this.data = data;}}public BinaryTree() {root = null;}/** * 递归创建二叉树 *  * @param node * @param data */public void buildTree(Node node, int data) {if (root == null) {root = new Node(data);} else {if (data < node.data) {if (node.left == null) {node.left = new Node(data);} else {buildTree(node.left, data); // 递归}} else {if (node.right == null) {node.right = new Node(data);} else {buildTree(node.right, data); // 递归}}}}/** * 前序遍历: ，再访问左子树,最后访问右子树 *  * @param node */public void preOrder(Node node) {if (node != null) {System.out.println(node.data);preOrder(node.left);preOrder(node.right);}}/** * 中序遍历: 先访问左子树，再访问根节点，最后访问右子树 *  * @param node */public void inOrder(Node node) {if (node != null) {inOrder(node.left);System.out.println(node.data);inOrder(node.right);}}/** * 后序遍历: 先访问左子树，再访问右子树，最后访问根节点 *  * @param node */public void postOrder(Node node) {if (node != null) {postOrder(node.left);postOrder(node.right);System.out.println(node.data);}}/** * 测试方法 *  * @param args */public static void main(String[] args) {int[] arr = { 6, 4, 8, 1, 7, 3, 9, 2, 5 };BinaryTree bTree = new BinaryTree();// 构建一棵二叉树for (int i = 0; i < arr.length; i++) {bTree.buildTree(bTree.root, arr[i]);}bTree.preOrder(bTree.root); // 前序遍历bTree.inOrder(bTree.root); // 中序遍历bTree.postOrder(bTree.root); // 后序遍历}}