1.1. 树的基本概念

树是n(n>=0)个节点的有限集，当n为0时，称为空树。对于任意一棵非空树，应满足：

1） 有且仅有一个特定的称为根的节点

2）当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每个集合本省又是一棵树，并且称为根的子树

由此可见，树的定义是递归的，即在树的定义中有用到了自身，树是一种递归的数据结构，树作为一种逻辑结构，同时也是一种分层结构，具有以下特点：

1）树的根节点没有前驱，除根节点外的所有节点有且只有一个前驱

2）树中所有节点可以有零个或多个后继

对于n个节点的树，有n-1条边。

1.2. 二叉树的概念

二叉树本质上也是树，它的特点是，每个节点至多只有两棵子树，并且二叉树的子树有左右之分，它是有序树，如果将其左右子树颠倒，那么会成为另一棵不同的二叉树，二叉树的5种基本形态如下：

1.3. 几种特殊的二叉树

1）斜树

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

2）满二叉树

一棵高度为h，且含有2^h - 1个节点的二叉树，称为满二叉树，即树的每层都含有最多的节点，满二叉树的叶子节点集中在二叉树的最下一层，并且除叶子节点之外的每个节点，度数均为2。假设编号从根节点开始为1，自上而下，从左到右，那么，对于编号为n的节点，如果有父节点， 父节点为n/2，如果有左孩子，左孩子为2n，如果有右孩子，右孩子为2n+1， 如下图所示：

3）完全二叉树

对于高度为h，有n个节点的二叉树，除了第h层外，其他各层(1~h-1)的节点数都达到最大格式（即1~h-1层是一个满二叉树），第h层所有节点都连续集中在最左边，这就是完全二叉树。

2. 二叉搜索树

二叉搜索树有以下特点：

1）左子树上所有节点的值均小于它的根节点的值

2）右子树上所有节点的值均大于它的根节点的值

3）任意节点的左右子树也分别为二叉搜索树

4）没有键值相等的节点

2.1. 二叉搜索树的插入

1）对于插入，如果一开始为空树，那么新建一个节点，作为该树的根节点。

2）当不为空树时，判断插入的数字，与当前根节点的大小进行比较，如果比当前值小，插入到左子树

3）当不为空树时，判断插入的数字，与当前根节点的大小进行比较，如果比当前值大，插入到右子树

2.2. 二叉搜索树的查找

1）判断当前节点是否为空，为空直接返回

2）当前节点不为空，判断查询值域当前节点值的大小，如果比当前值小，进入左子树查询

3）当前节点不为空，判断查询值域当前节点值的大小，如果比当前值大，进入右子树查询

2.3. 二叉搜索树的删除

1）判断当前节点是否为空，为空直接返回

2）当前节点不为空，删除值小于当前节点值，进入左子树删除

3）当前节点不为空，删除值大于当前节点值，进入右子树删除

4）当前节点不为空，删除值等于当前值：

4.1）如果当前节点左右子树都为空，直接删除当前节点

4.2）如果当前节点左子树不为空，右子树为空，使用左节点取代当前节点

4.3）如果当前节点右子树不为空，左子树为空，使用右节点取代当前节点

4.4）左右子树都不为空，选择左子树的最右节点或右子树的最左节点，代替当前节点

2.4. 遍历

对于树的遍历，一般有前序遍历、中序遍历、后序遍历这几种方式。

1）前序遍历：对树按照根、左、右的规律进行访问，如下图所示，遍历结果为F,B,A,D,C,E,G,I,H

2) 中序遍历：对树，按照左、根、右的规律进行访问。如下图所示，遍历结果为:A,B,C,D,E,F,G,H,I

3) 后序遍历：对树，按照左、右、根的规律进行访问。如下图所示，遍历结果为:A, C, E, D, B,H, I, G, F

2.5. 二叉搜索树示例代码

完整代码如下：

public class BinarySearchTree {    class Node {        private int val;        private Node left;        private Node right;        public Node(int val) {            this.val = val;            this.left = null;            this.right = null;        }        public void setVal(int val) {            this.val = val;        }        public int getVal() {            return this.val;        }        public Node getLeft() {            return left;        }        public void setLeft(Node left) {            this.left = left;        }        public Node getRight() {            return right;        }        public void setRight(Node right) {            this.right = right;        }    }    // 根节点    private Node root;    private Node insert(Node root, int val) {        if (root == null) {            root = new Node(val);            return root;        }        if (root.val < val) {            root.right = insert(root.right, val);        } else if(root.val > val) {            root.left = insert(root.left, val);        }        return root;    }    private Node search(Node root, int val) {        if (root == null) {            return null;        }        if (root.val < val) {            return search(root.right, val);        } else if (root.val > val) {            return search(root.left, val);        }        return root;    }    private Node remove(Node root, int val) {        if (root == null) {            return null;        }        if (root.val < val) {            return remove(root.right, val);        } else if (root.val > val) {            return remove(root.left, val);        }        if (root.left == null && root.right == null) {            root = null;            return root;        } else if (root.left == null) {            Node temp = root;            root = root.right;            temp = null;            return root;        } else if (root.right == null) {            Node temp = root;            root = root.left;            temp = null;            return root;        } else {            Node min = findMin(root.right);            root.val = min.val;            root.right = remove(root.right, root.val);        }        return root;    }    private Node findMin(Node t) {        while (t.left != null) {            t = t.left;        }        return t;    }    private void preOrderTraversal(Node t) {        if (t == null) {            return;        }        System.out.println(t.val);        preOrderTraversal(t.left);        preOrderTraversal(t.right);    }    private void midOrderTraversal(Node t) {        if (t == null) {            return;        }        midOrderTraversal(t.left);        System.out.println(t.val);        midOrderTraversal(t.right);    }    private void postOrderTraversal(Node t) {        if (t == null) {            return;        }        postOrderTraversal(t.left);        postOrderTraversal(t.right);        System.out.println(t.val);    }    public BinarySearchTree() {    }    public void insert(int val) {        root = insert(root, val);    }    public Node search(int val) {        return search(root, val);    }    public void remove(int val) {        root = remove(root, val);    }        public void preOrderTraversal() {        postOrderTraversal(this.root);    }        public void midOrderTraversal() {        midOrderTraversal(this.root);    }        public void postOrderTraversal() {        postOrderTraversal(this.root);    }}