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

2022-06-06 本文已影响0人 alex很累

一、树

定义

树是由根节点和若干颗子树构成的；
一棵树中的任意两个结点有且仅有唯一的一条路径连通；
一棵树如果有 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);
}