1.树的结构： 节点（每个节点 = 数据 + 左孩子 + 右孩子)

                      每个节点可以指向多个其他的节点

2.叶子节点：没有子节点的节点

3.二叉树：一个节点有两个子节点的树

---

二、hash算法：

作用：让 不同类型、无法比较的对象(如：'1' 和 'a')可以进行比较

流程：数据输入 > 算法 > 输出一个 hash 值 ( 整数值 )

算法： 可以将对象的属性转成整数值，累加

原理：把对象的属性转成整数累加，用 Hash 值大小来对比两个对象谁大谁小。

---

三、hash算法在树中的应用：

1.将对象的属性转换成整数值把字符串、自定义对象等无法直接比较的内容，转为数字。

2.通过公式累加计算使用固定算法（如字符串 31 加权和）将所有属性值累加。

3.生成唯一代表该对象的整数用于二叉搜索树中比较大小、确定插入位置。

---

四、二叉树能存储任意类型数据、并正确排序的核心原理：

将任意对象（数字、字符、字符串、自定义对象等）统一转换成整数，让原本不能比较大小的对象，都能进行大小比较，从而满足二叉搜索树的排序存储要求。

新数据的哈希值更小，就放入原数据的左子树

新数据的哈希值更大 / 相等 ，就放入原数据放入右子树

---

五、具体实现

1.自定义实现泛型二叉搜索树：

<E>是泛型，代表TreeNode可以存任意类型数据。

// E 指代任何一种类型 表示当前节点存储的数据的类型
public class TreeNode<E> {
        E data;
        TreeNode<E> left;
        TreeNode<E> right;
        public TreeNode(E data) {
            this.data = data;
        }
}

class Tree<E> {
    // 根节点
    TreeNode<E> root;
    int size;
}

2.利用 hash算法实现任意类型数据的大小比较：

通过 hashCode() 把对象转成整数，实现任意对象比较大小。

if (data.hashCode() < temp.data.hashCode()) {

}

3.完成二叉树节点定义：

public class TreeNode<E> {
    E data;          // 节点数据
    TreeNode<E> left;  // 左孩子
    TreeNode<E> right; // 右孩子
    public TreeNode(E data) {
        this.data = data;
    }
}

4.添加元素：

小的放左边，大的放右边

public void add(E data) {
    TreeNode<E> node = new TreeNode<>(data);
    if (root == null) {
        root = node;
        size++;
        return;
    }
    TreeNode<E> temp = root;
    while (true) {
        if (data.hashCode() < temp.data.hashCode()) { // 比节点小 → 左边
            if (temp.left == null) {
                temp.left = node;
                size++;
                break;
            } else {
                temp = temp.left;
            }
        } else {                                     // 大于等于 → 右边
            if (temp.right == null) {
                temp.right = node;
                size++;
                break;
            } else {
                temp = temp.right;
            }
        }
    }
}

5.递归 中序遍历打印：

节点为空时递归终止

数据从小到大有序输出

public void print(TreeNode<E> node) {
    if (node == null) {
        return;
    }
    TreeNode<E> temp = node;
    print(temp.left);      // 先遍历左子树
    System.out.println(temp.data + ","); //  打印自己
    print(temp.right);     // 再遍历右子树
}

6.验证 hashCode 能把字符串转为整数:

String str = "hello worldoo";
System.out.println(str.hashCode());

7.最后检测树是否可以正确存储：

通过循环 100 次生成字符串，并插入树中，测试树的存储与遍历功能

Tree<String> tree = new Tree<>();
Random r = new Random();
for (int i = 0; i < 100; i++) {
    int n = r.nextInt(100);
    tree.add("hello" + n);
}
System.out.println(tree.size);
tree.print(tree.root);

---

六、总结：

1.可以借助哈希值间接完成不同类型数据大小对比

2.树的新增、查找都要从根节点开始自上而下遍历，不能随意起始。

3.递归遍历二叉树的终止条件是：节点为空

---

七、完整代码：

package 树;
import java.util.Random;

// E 指代任何一种类型 表示当前节点存储的数据的类型
public class TreeNode<E> {
        E data;
        TreeNode<E> left;
        TreeNode<E> right;
        public TreeNode(E data) {
            this.data = data;
        }
    }
    class Tree<E> {
        // 根节点
        TreeNode<E> root;
        int size;
        // 添加元素必须按照从左到右 按照高度存储
// 二叉搜索排序树 与节点数据比大小来决定存在左 还是右边
        public void add(E data) {
            TreeNode<E> node = new TreeNode<>(data);
            if (root == null) {
                root = node;
                size++;
                return;
            }
            TreeNode<E> temp = root;
            while (true) {
                if (data.hashCode() < temp.data.hashCode()) {
                    if (temp.left == null) {
                        temp.left = node;
                        size++;
                        break;
                    } else {
// 左子树
                        temp = temp.left;
                    }
                } else {
                    if (temp.right == null) {
                        temp.right = node;
                        size++;
                        break;
                    } else {
// 右子树
                        temp = temp.right;
                    }
                }
            }
        }
        public void remove(E data) {
        }
        // 包含
        public boolean contains(E data) {
            return false;
        }
        public void getTree() {
// 返回一个存储了树所有的数据的数组
        }
        // 打印
        public void print(TreeNode<E> node) {
            if (node == null) {
                return;
            }
            TreeNode<E> temp = node;

            print(temp.left);
            System.out.println(temp.data + ",");
            print(temp.right);
        }
        public static void main(String[] args) {
            String str = "hello worldoo";
            System.out.println(str.hashCode());

            Tree<String> tree = new Tree<>();
            Random r = new Random();
            for (int i = 0; i < 100; i++) {
                int n = r.nextInt(100);
                System.out.println(n);
                tree.add("hello" + n);
            }
            System.out.println(tree.size);
            tree.print(tree.root);
        }

}