树、二叉树、二叉搜索树的特性与实现

一、树

定义

• 树是由根节点和若干颗子树构成的；
• 一棵树中的任意两个结点有且仅有唯一的一条路径连通；
• 一棵树如果有 n 个结点，那么它一定恰好有 n-1 条边；
• 一棵树不包含回路（树是特殊的图，树没有环）。

示例

树，二叉树

二、二叉树

定义

二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。

JAVA实现

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

二叉树的遍历(用递归实现)

前序遍历：根节点-左节点-右节点

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

中序遍历：左节点-根节点-右节点

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

后序遍历：左节点-右节点-根节点

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

三、二叉搜索树

定义

二叉搜索树，又称有序二叉树、排序二叉树，是具有下列性质的二叉树：

• 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
• 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
• 任意结点的左、右子树也分别为二叉搜索树；
  根据性质可知，中序遍历二叉搜索树即可得到升序排列的数据。

示例

二叉搜索树
可以在这个网址尝试进行一些二叉搜索树的操作。

四、lintcode上的一些题目

94.二叉树的中序遍历

144. 二叉树的前序遍历

145. 二叉树的后序遍历

这三道题没什么难的，看一下上文二叉树的遍历即可。

589. N 叉树的前序遍历

这道题也很简单，只是简单拓展一下。

429. N 叉树的层序遍历

这道题也很简单，遍历一下就结束啦。