长春设计网站,网站备案名称填写规则,黑彩网站建设,建站工具箱数据结构之树#xff0c;介绍篇
树的基本定义
介绍#xff1a;树#xff08;tree#xff09;是计算机中非常重要的数据结构#xff0c;它的外形看起来像一颗倒挂着的的树#xff0c;使用树这种结构可以描述生活中很多的事物#xff0c;如族谱#xff0c;单位的组织架…数据结构之树介绍篇
树的基本定义
介绍树tree是计算机中非常重要的数据结构它的外形看起来像一颗倒挂着的的树使用树这种结构可以描述生活中很多的事物如族谱单位的组织架构xmlhtml的中属性的关系文件目录路由协议某些数据库的索引机器学习中的决策树等定义树是由nn1个有限结点(node)组成的一个具有层次关系的集合某些结点之前存在特定的关系用连线相连连线称作边(edge)边的上端的结点称为父结点下面的端点称为子结点
树的特点
每个结点有0个或多个子结点没有父结点的结点称为根结点一个父结点可能有多个子结点每个结点及其后代结点也可以看做一棵树称为当前结点父结点的一颗子树
树的相关术语
结点的度一个结点含有的子树的棵数叶结点度为0的结点称为叶结点也叫做终端结点分支结点度不为0的结点称为分支结点或叫做非终端结点结点的层次根结点层次为1它的直接后继层次为2以此类推结点的层序编号将一棵树的结点按照从上往下同层次从左往右的顺序依次使用自然数按顺序编号获得的值树的度树中所有结点最大的度可能是根结点的度也可能不是如某颗子树存在更多个颗树树的高度或深度树中结点的最大层次结点的深度是指对应结点到根结点路径长度(经过的层次)森林没有相互直接连接或间接连接关系的树的集合可称之为森林。将一棵树的根结点及其边移除得到所有其子树组成的集合可称为森林孩子(子)结点一个结点的直接后继结点称之为该结点的孩子(子)结点双亲(父)结点一个结点的直接前驱结点称之为该结点的双亲(父)结点兄弟结点双亲结点相同的结点互为兄弟结点子孙以某节点为根的子树中任一节点都称为该节点的子孙。
树的常见/常用种类
二叉树Binary tree区别于B-tree每个节点最多含有两个子树的树称为二叉树完全二叉树Complete Binary tree除了最后一层的结点树有可能没有达到饱和外其他所有层都已经是饱和值此外其最后一层的结点会尽量从左往右生成满二叉树Full Binary tree满二叉树是完全二叉树的一种特殊情况平衡二叉树AVL tree取名于其两个发明者 Adelson-Velsky和Landis当且仅当任何节点的两棵子树的高度差不大于1的二叉树二叉查找树英语Binary Search TreeBST是一种内存中特殊的数据结构它允许对存储在其结点的数据进行增删改查或者用作动态的数据集合或是通过key查找对应value的查找表霍夫曼树用于信息编码带权路径最短的二叉树称为哈夫曼树或最优二叉树B树一种对读写操作进行优化的自平衡的二叉查找树能够保持数据有序拥有多余两个子树。
其中一部分我们会在后续详细介绍
二叉树的性质
性质1: 在二叉树的第i层上至多有2^(i-1)个结点i0性质2: 深度为k的二叉树至多有2^k - 1个结点k0性质3: 对于任意一棵二叉树如果其叶结点数为N0而度数为2的结点总数为N2则N0N21;性质4:具有n个结点的完全二叉树的深度必为 log2(n1)性质5:对完全二叉树若从上至下、从左至右编号则编号为i 的结点其左孩子编号必为2i其右孩子编号必为2i1其双亲的编号必为i/2i1 时为根,除外
