数据结构与算法 5.树

本文主要是介绍数据结构与算法 5.树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

树

树的基本概念
    每个节点有0个或多个子节点
    没有父节点的节点称为根节点
    每一个非根节点有且只有一个父节点
    除根节点外，每个子节点可以分为多个不相交的子树
    一棵树可以没有任何节点，称为空树，可以只有1个节点，即根节点

    节点、根节点、子节点、父节点、兄弟节点

    子树、左子树、右子树

    节点的度（degree）：子树的个数
    树的度：所有节点度中的最大值
    叶子节点（leaf）：度为0的节点

    层数（level）：根节点在第1层，根节点的子节点在第2层，以此类推

    节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数
    节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数

    树的深度：所有节点深度中的最大值
    树的高度：所有节点高度中的最大值
    树的深度等于树的高度

    有序树：树中任意节点的子节点之间有顺序关系
    无序树：树中任意节点的子节点之间没有顺序关系，也叫自由树
    森林：由m（m>=0）棵互不相交的树组成的集合

树的种类
    二叉树：每个节点最多含有两个子树的树
    完全二叉树：对于一棵二叉树，设其深度为d（d>1），除了第d层，其他各层的节点数均已达最大值，且d层所有节点从左向右紧密排列
    满二叉树：所有叶节点都在最底层的完全二叉树
    平衡二叉树（AVL树）：任何节点的两棵子树的高度差不大于1的二叉树
    排序二叉树（binary search tree）：也叫二叉查找树
    霍夫曼树：带权路径最短的二叉树，也叫最优二叉树，用于信息编码
    B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树

常见应用场景：
    xml、html等，编写解析器时
    路由协议
    mysql数据库索引
    文件系统的目录结构
    很多AI算法都是树搜索，此外机器学习中的decision tree也是树结构

这篇关于数据结构与算法 5.树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！