自学内容网 自学内容网
自学内容网 > 正文

数据结构--树

🕗 发布于 2024-09-27 16:40 数据结构  树  二叉树  

文章目录

树

1. 树的理解

在这里插入图片描述

专有名词解释：

结点：树中的数据元素都称之为结点

根节点：最上面的结点称之为根，一颗树只有一个根且由根发展而来，从另外一个角度来说，每个结点都可以认为是其子树的根

父节点：结点的上层结点，如图中，结点K的父节点是E、结点L的父节点是G

子节点：节点的下层结点，如图中，节点E的子节点是K节点、节点G的子节点是L节点

兄弟节点：具有相同父节点的结点称为兄弟节点，图中F、G、H互为兄弟节点

结点的度数：每个结点所拥有的子树的个数称之为结点的度，如结点B的度为3

树叶：度数为0的结点，也叫作终端结点，图中D、K、F、L、H、I、J都是树叶

非终端节点（或分支节点）：树叶以外的节点，或度数不为0的节点。图中根、A、B、C、E、G都是

树的深度（或高度）：树中结点的最大层次数，图中树的深度为4

结点的层数：从根节点到树中某结点所经路径上的分支树称为该结点的层数，根节点的层数规定为1，其余结点的层数等于其父亲结点的层数+1

同代：在同一棵树中具有相同层数的节点

2. 二叉树的基本概念

二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

3. 二叉树的遍历

  • 前序遍历：中左右（根左右）

    即先访问根结点，再前序遍历左子树，最后再前序遍历右子 树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。

    在这里插入图片描述

    前序遍历：ABDEGCFHI

public class TreeSearch {

    // 创建一个二叉树
    public TreeNode getTargetTree() {
        // 叶子节点
        TreeNode G = new TreeNode("G");
        TreeNode D = new TreeNode("D");
        TreeNode E = new TreeNode("E", G, null);
        TreeNode B = new TreeNode("B", D, E);
        TreeNode H = new TreeNode("H");
        TreeNode I = new TreeNode("I");
        TreeNode F = new TreeNode("F", H, I);
        TreeNode C = new TreeNode("C", null, F);
        // 构造根节点
        TreeNode root = new TreeNode("A", B, C);
        return root;
    }


    /**
 * 前序遍历
 */
    public void preorderVistTreeNode(TreeNode node) {
        if (null != node) {

            System.out.print(node.value);

            if (null != node.leftchildren) {
                preorderVistTreeNode(node.leftchildren);
            }
            if (null != node.rightchildre) {
                preorderVistTreeNode(node.rightchildre);
            }
        }
    }


    public static void main(String[] args) {

        TreeSearch treeSearch = new TreeSearch();
        TreeNode tree = treeSearch.getTargetTree();

        System.out.print("前序遍历:");
        treeSearch.preorderVistTreeNode(tree);
        System.out.println("");
    }
}

  • 中序遍历：左中右（左根右）

    即先中前序遍历左子树，然后再访问根结点，最后再中序遍 历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。

    在这里插入图片描述

    中序遍历：DBGEACHFI

/**
*  中序遍历
*/
public void inorderVistTreeNode(TreeNode node){
    if(null != node){
        if(null != node.leftchildren){
            inorderVistTreeNode(node.leftchildren);
        }

        System.out.print(node.value);

        if(null != node.rightchildre){
            inorderVistTreeNode(node.rightchildre);
        }
    }
}

public static void main(String[] args) {
    TreeSearch treeSearch = new TreeSearch();
    TreeNode tree= treeSearch.getTargetTree();

    System.out.print("中序遍历:");
    treeSearch.inorderVistTreeNode(tree);
    System.out.println("");
}

  • 后序遍历：左右中（左右根）

    即先后序遍历左子树，然后再后序遍历右子树，最后访问根 结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。

    在这里插入图片描述

    后序遍历：DGEBHIFCA

/**
 *  后序遍历
 */
public void postorderVistTreeNode(TreeNode node){
    if(null != node){
        if(null != node.leftchildren){
            postorderVistTreeNode(node.leftchildren);
        }
        if(null != node.rightchildre){
            postorderVistTreeNode(node.rightchildre);
        }

        System.out.print(node.value);

    }
}

public static void main(String[] args) {
    TreeSearch treeSearch = new TreeSearch();
    TreeNode tree= treeSearch.getTargetTree();

    System.out.print("后序遍历:");
    treeSearch.postorderVistTreeNode(tree);
    System.out.println("");
}

4. 经典二叉树

1、满二叉树： 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2的n-1次方，总的结点个数是2的n次方-1

在这里插入图片描述

2、完全二叉树： 叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。

在这里插入图片描述
3、二叉排序/查找/搜索树：即为BST (binary search/sort tree)。满足如下性质：
（1）若它的左子树不为空，则左子树上所有结点的值均小于它的根节点的值；
（2）若它的右子树上所有结点的值均大于它的根节点的值；
（3）它的左、右子树也分别为二叉排序/查找/搜索树。

对二叉查找树进行中序遍历，得到有序集合。便于检索。

4、平衡二叉树：（Self-balancing binary search tree，AVL）首先是二叉排序树，此外具有以下性质：
（1）它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
（2）并且左右两个子树也都是一棵平衡二叉树
（3）不要求非叶节点都有两个子结点

平衡二叉树的目的是为了减少二叉查找树的层次，提高查找速度。平衡二叉树的常用实现有红黑树、AVL、替罪羊树、Treap、伸展树等。

5、红黑树：即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，它是在 1972 年由 Rudolf Bayer 发明的。红黑树是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(log n)时间内做查找，插入和删除， 这里的 n 是树中元素的数目。

红黑树的特性：

  • 每个节点是红色或者黑色

  • 根节点是黑色

  • 每个叶子节点（NIL）是黑色。（注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点）

  • 每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（确保没有一条路径会比其他路径长出2倍）

当我们插入或删除节点时，可能会破坏已有的红黑树，使得它不满足以上5个要求，那么此时就需要进行处理，使得它继续满足以上的5个要求：

1、recolor ：将某个节点变红或变黑

2、rotation ：将红黑树某些结点分支进行旋转（左旋或右旋）

红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡。主要是用它来存储有序的数据，它的时间复杂度是O(logN)，效率非常之高。

5. 二叉树及其结点的表示

普通二叉树：

public class BinaryTree<E>{
    private TreeNode root; //二叉树的根结点
    private int total;//结点总个数
    
    private class TreeNode{
        //至少有以下几个部分
        TreeNode parent;
        TreeNode left;
        E data;
        TreeNode right;
        
        public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {
            this.parent = parent;
            this.left = left;
            this.data = data;
            this.right = right;
        }
}
}

TreeMap红黑树：

public class TreeMap<K,V> {
    private transient Entry<K,V> root;
    private transient int size = 0;
    
static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }
}

原文地址：https://blog.csdn.net/weixin_62008675/article/details/142451408

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024