一、樹

定義

• 樹是由根節(jié)點和若干顆子樹構成的；
• 一棵樹中的任意兩個結點有且僅有唯一的一條路徑連通；
• 一棵樹如果有 n 個結點，那么它一定恰好有 n-1 條邊；
• 一棵樹不包含回路（樹是特殊的圖，樹沒有環(huán)）。

示例

樹，二叉樹

二、二叉樹

定義

二叉樹（Binary tree）是每個節(jié)點最多只有兩個分支（即不存在分支度大于 2 的節(jié)點）的樹結構。

JAVA實現(xiàn)

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

二叉樹的遍歷(用遞歸實現(xiàn))

前序遍歷：根節(jié)點-左節(jié)點-右節(jié)點

public void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.println(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

中序遍歷：左節(jié)點-根節(jié)點-右節(jié)點

public void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrder(root.left);
    System.out.println(root.val);
    inOrder(root.right);
}

后序遍歷：左節(jié)點-右節(jié)點-根節(jié)點

public void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrder(root.left);
    inOrder(root.right);
    System.out.println(root.val);
}

三、二叉搜索樹

定義

二叉搜索樹，又稱有序二叉樹、排序二叉樹，是具有下列性質的二叉樹：

• 若任意結點的左子樹不空，則左子樹上所有結點的值均不大于它的根結點的值。
• 若任意結點的右子樹不空，則右子樹上所有結點的值均不小于它的根結點的值。
• 任意結點的左、右子樹也分別為二叉搜索樹；
  根據(jù)性質可知，中序遍歷二叉搜索樹即可得到升序排列的數(shù)據(jù)。

示例

二叉搜索樹

四、lintcode上的一些題目

94.二叉樹的中序遍歷

144. 二叉樹的前序遍歷

145. 二叉樹的后序遍歷

這三道題沒什么難的，看一下上文二叉樹的遍歷即可。

589. N 叉樹的前序遍歷

這道題也很簡單，只是簡單拓展一下。

429. N 叉樹的層序遍歷

這道題也很簡單，遍歷一下就結束啦。