数据结构——树_在树形数据结构中,一个节点可以有多个子节点,但每个子节点只能有一个父节点的结构

树是一种非线性的数据结构，它由一组节点组成，这些节点通过边连接。在树中，有一个被称为根节点的特殊节点，其他节点都是从根节点开始通过一条唯一的路径到达的。树中的每个节点可以有多个子节点，但每个节点只有一个父节点（除了根节点）。树的分支被称为子树。

树的特点包括：
1. 根节点：树的顶部节点，其他节点都是从根节点开始通过一条唯一的路径到达的。
2. 节点：树中的每个元素，通常包含一个值和指向其子节点的指针。
3. 子节点：一个节点的直接子节点，它们位于该节点的下一层。
4. 父节点：一个节点的直接上层节点。
5. 叶节点：没有子节点的节点。
6. 深度：从根节点到某个节点的路径上的边数。
7. 高度：树中任意节点到叶节点的最长路径的边数。

树的应用非常广泛，它可以用来表示层次关系、组织结构、文件系统等。常见的树的应用包括二叉树、AVL树、红黑树、B树等。

树的操作包括插入节点、删除节点、查找节点、遍历节点等。常见的树的遍历算法包括前序遍历、中序遍历和后序遍历。

二叉树：

二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的定义如下：

1.  二叉树可以为空树，也就是不包含任何节点。
2.  如果不为空树，那么每个节点包含一个数据元素和左子树、右子树两个指针。
3.  左子树和右子树都是二叉树。
4.  二叉树的左子树和右子树的位置是固定的。

二叉树的特点：

1.  每个节点最多有两个子节点。
2.  左子树的值小于等于父节点的值，右子树的值大于等于父节点的值（这是一棵二叉查找树）。
3.  左子树和右子树也都是二叉树。

二叉树的遍历方式：

1.  前序遍历（根-左-右）：先访问根节点，再前序遍历左子树，最后前序遍历右子树。
2.  中序遍历（左-根-右）：先中序遍历左子树，再访问根节点，最后中序遍历右子树。
3.  后序遍历（左-右-根）：先后序遍历左子树，再后序遍历右子树，最后访问根节点。
4.  层序遍历（逐层访问）：按照从上到下、从左到右的顺序逐层访问节点。

二叉树的应用：

1.  二叉搜索树：基于二叉树的特性，可以快速地进行查找、插入和删除操作。
2.  表达式树：将数学表达式表示为二叉树，方便进行计算。
3.  堆和优先队列：二叉树可以用来实现堆和优先队列，用于快速获取最大或最小的元素。
4.  文件系统：文件系统中的目录和子目录可以通过二叉树进行组织和管理。

需要注意的是，二叉树的高度可能会非常大，导致操作的时间复杂度较高。为了提高二叉树的效率，可以使用平衡二叉树等其他数据结构。

代码基本实现

package com.zlk.tree;
 
 
import com.zlk.line.Queue;
/**
 * @author zlk
 * @date  2023年09月03日 19:34
 * 二叉树的基本实现
 */
public class BinaryTree3<Key extends Comparable<Key>, Value> {
    //记录根结点
    private Node root;
    //记录树中元素的个数
    private int N;
 
    private class Node {
        //存储键
        public Key key;
        //存储值
        private Value value;
        //记录左子结点
        public Node left;
        //记录右子结点
        public Node right;
 
        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
 
    //获取树中元素的个数
    public int size() {
        return N;
    }
 
    //向树中添加元素key-value
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }
 
    //向指定的树x中添加key-value,并返回添加元素后新的树
    private Node put(Node x, Key key, Value value) {
        //如果x子树为空，
        if (x==null){
            N++;
            return new Node(key,value, null,null);
        }
 
        //如果x子树不为空
        //比较x结点的键和key的大小：
 
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            //如果key大于x结点的键，则继续找x结点的右子树
            x.right = put(x.right,key,value);
 
        }else if(cmp<0){
            //如果key小于x结点的键，则继续找x结点的左子树
            x.left = put(x.left,key,value);
        }else{
            //如果key等于x结点的键，则替换x结点的值为value即可
            x.value = value;
        }
        return x;
    }
    //查询树中指定key对应的value
    public Value get(Key key) {
        return get(root,key);
    }
 
    //从指定的树x中，查找key对应的值
    private Value get(Node x, Key key) {
        //x树为null
        if (x==null){
            return null;
        }
        //x树不为null
        //比较key和x结点的键的大小
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            //如果key大于x结点的键，则继续找x结点的右子树
            return get(x.right,key);
 
        }else if(cmp<0){
            //如果key小于x结点的键，则继续找x结点的左子树
            return get(x.left,key);
        }else{
            //如果key等于x结点的键，就找到了键为key的结点，只需要返回x结点的值即可
            return x.value;
        }
    }
    //删除树中key对应的value
    public void delete(Key key) {
        delete(root, key);
    }
    //删除指定树x中的key对应的value，并返回删除后的新树
    private Node delete(Node x, Key key) {
        //x树为null
        if (x==null){
            return null;
        }
        //x树不为null
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            //如果key大于x结点的键，则继续找x结点的右子树
            x.right = delete(x.right,key);
 
        }else if(cmp<0){
            //如果key小于x结点的键，则继续找x结点的左子树
            x.left = delete(x.left,key);
        }else{
            //如果key等于x结点的键，完成真正的删除结点动作，要删除的结点就是x；
 
            //让元素个数-1
            N--;
            //得找到右子树中最小的结点
            if (x.right==null){
                return x.left;
            }
            if (x.left==null){
                return x.right;
            }
 
            Node minNode = x.right;
            while(minNode.left!=null){
                minNode = minNode.left;
            }
 
            //删除右子树中最小的结点
            Node n = x.right;
            while(n.left!=null){
                if (n.left.left==null){
                    n.left=null;
                }else{
                    //变换n结点即可
                    n = n.left;
                }
            }
 
            //让x结点的左子树成为minNode的左子树
            minNode.left = x.left;
            //让x结点的右子树成为minNode的右子树
            minNode.right = x.right;
            //让x结点的父结点指向minNode
            x = minNode;
        }
        return x;
    }
 
    //查找整个树中最小的键
    public Key min(){
        return min(root).key;
    }
 
    //在指定树x中找出最小键所在的结点
    private Node min(Node x){
 
        //需要判断x还有没有左子结点，如果有，则继续向左找，如果没有，则x就是最小键所在的结点
        if (x.left!=null){
            return min(x.left);
        }else{
            return x;
        }
    }
 
    //在整个树中找到最大的键
    public Key max(){
        return max(root).key;
    }
 
    //在指定的树x中，找到最大的键所在的结点
    public Node max(Node x){
        //判断x还有没有右子结点，如果有，则继续向右查找，如果没有，则x就是最大键所在的结点
        if (x.right!=null){
            return max(x.right);
        }else{
            return x;
        }
    }
 
    //获取整个树中所有的键
    public Queue<Key> preErgodic(){
        Queue<Key> keys = new Queue<>();
        preErgodic(root, keys);
        return keys;
    }
 
    //获取指定树x的所有键，并放到keys队列中
    private void preErgodic(Node x,Queue<Key> keys){
        if (x==null){
            return;
        }
        //把x结点的key放入到keys中
        keys.enqueue(x.key);
 
        //递归遍历x结点的左子树
        if (x.left!=null){
            preErgodic(x.left,keys);
        }
 
        //递归遍历x结点的右子树
        if (x.right!=null){
            preErgodic(x.right,keys);
        }
 
    }
 
    //使用中序遍历获取树中所有的键
    public Queue<Key> midErgodic(){
        Queue<Key> keys = new Queue<>();
        midErgodic(root,keys);
        return keys;
    }
 
    //使用中序遍历，获取指定树x中所有的键，并存放到key中
    private void midErgodic(Node x,Queue<Key> keys){
        if (x==null){
            return;
        }
        //先递归，把左子树中的键放到keys中
        if (x.left!=null){
            midErgodic(x.left,keys);
        }
        //把当前结点x的键放到keys中
        keys.enqueue(x.key);
        //在递归，把右子树中的键放到keys中
        if(x.right!=null){
            midErgodic(x.right,keys);
        }
 
    }
 
    //使用后序遍历，把整个树中所有的键返回
    public Queue<Key> afterErgodic(){
        Queue<Key> keys = new Queue<>();
        afterErgodic(root,keys);
        return keys;
    }
 
    //使用后序遍历，把指定树x中所有的键放入到keys中
    private void afterErgodic(Node x,Queue<Key> keys){
        if (x==null){
            return ;
        }
 
        //通过递归把左子树中所有的键放入到keys中
        if (x.left!=null){
            afterErgodic(x.left,keys);
        }
        //通过递归把右子树中所有的键放入到keys中
        if (x.right!=null){
            afterErgodic(x.right,keys);
        }
        //把x结点的键放入到keys中
        keys.enqueue(x.key);
    }
 
 
    //使用层序遍历，获取整个树中所有的键
    public Queue<Key> layerErgodic() throws InterruptedException {
        //定义两个队列，分别存储树中的键和树中的结点
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();
 
        //默认，往队列中放入根结点
        nodes.enqueue(root);
 
        while(!nodes.isEmpty()){
            //从队列中弹出一个结点，把key放入到keys中
            Node n = nodes.dequeue();
            keys.enqueue(n.key);
            //判断当前结点还有没有左子结点，如果有，则放入到nodes中
            if (n.left!=null){
                nodes.enqueue(n.left);
            }
            //判断当前结点还有没有右子结点，如果有，则放入到nodes中
            if (n.right!=null){
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }
 
 
    //获取整个树的最大深度
    public int maxDepth(){
        return maxDepth(root);
    }
 
    //获取指定树x的最大深度
    private int maxDepth(Node x){
        if (x==null){
            return 0;
        }
        //x的最大深度
        int max=0;
        //左子树的最大深度
        int maxL=0;
        //右子树的最大深度
        int maxR=0;
 
        //计算x结点左子树的最大深度
        if (x.left!=null){
            maxL = maxDepth(x.left);
        }
        //计算x结点右子树的最大深度
        if (x.right!=null){
            maxR = maxDepth(x.right);
        }
        //比较左子树最大深度和右子树最大深度，取较大值+1即可
 
        max = maxL>maxR?maxL+1:maxR+1;
 
        return max;
    }
 
}