20240225

二叉搜索树：

性质：节点的左子树只包含小于当前节点的数，节点的右子树只包含大于当前节点的数，且所有左子树和右子树自身必须也是二叉搜索树，且其中序遍历为单调递增序列。

二叉树中序遍历（非递归）：

public void Middle(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();//数据结构为栈
        TreeNode p = root;
        while(p != null || !queue.isEmpty()){
            while(p != null){
                queue.push(p);
                p = p.left;
            }
            TreeNode q = queue.pop();//出栈
            System.out.println(q.val);
            p = q.right;
        }
    }

大致思路：中序遍历顺序为左-根-右，初始节点为根节点，当节点非空时，一直向左走，将这些节点压入栈中，当节点为空时，从栈中取出栈顶的节点，输入值后将指针指向弹出节点的右子节点。

前缀树：

结构形式：

上图的前缀树由字符串"sea","sells","she"创建的，对应的层数为该节点字母在字符串中的下标位置（均从0开始），在数据结构上，包含和自己类型相同且长度为26的数组、是否为单词结尾的标识符（不是叶节点，因为可能存在如"ab","abb"两个字符串同时在前缀树上），初始化如下：

public Trie() {
    tree = new Trie[26];
    isEnd = false;
}

节点（即类本身，类本身不存储字母），然后遍历字符串，计算各字母应对应数组下标，若该下标处为空，则新建一个与类本身类型相同的类，并将新建的类赋值给初始值，反之直接将对应下标的类复制给初始值（上述操作相当于进入下一层进行插入），每一次遍历时是否为结尾标识符设置为false，当遍历完要插入的字符串时，该类的标识符设置为true，代码如下：

class Trie {
    Trie[] tree;
    boolean isEnd;
    public Trie() {
        tree = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        char[] cc = word.toCharArray();
        Trie T = this;
        for(int i = 0; i < cc.length; i++){
            char c = cc[i];
            int index = c - 'a';
            if(T.tree[index] == null){
                T.tree[index] = new Trie();//该下标未出现节点，新建
                T.tree[index].isEnd = false;
            }
            T = T.tree[index];
        }
        T.isEnd = true;
    }
}