你好,游客 登录 注册 搜索
背景:
阅读新闻

二叉树的概念、算法简介及树的平衡

[日期:2018-01-11] 来源:Linux社区  作者:idreamo [字体: ]

在计算机科学中,树由称为结点的元素按照层次结构的方式组织而成。层次结构最顶端的结点称为根。与根结点直接相连的结点称为根的子结点,通常子结点本身也有属于它们自己的子结点。除了根结点外,在这个层次体系中的每个结点都有唯一的父结点,也就是与其直接相连的上级结点。

一个节点拥有多少个子节点取决于树的类型,这个量值称为树的的分支因子,它决定了当插入结点时树的分支扩展的速度。

二叉树是一种相对简单但功能强大的树,其树的分支因子值为2。

二叉树的介绍

二叉树是一种将结点按照层次结构组织起来的数据结构,每个结点最多只有两个与它直接相关联的子结点。直接连接在结点下方的那个结点称为子结点,而与每个子结点直接相连的上方结点称为父结点。结点也有兄弟、子孙和祖先。一个结点的兄弟结点是它的父亲结点的其他子结点。一个结点的子孙结点是其所有分支下的结点。而结点的祖先结点则是在该结点与根结点之间路径上的所有结点。

 

 二叉树中的每一个结点都包含3部分:一个数据成员和左右两个指针。

通过这种3个成员的结构体,将每个结点的左右指针分别指向该结点的子结点,以此来构建一棵二叉树。如果某个结点没有对应的左子结点或右子结点,就将相应的指针设置为NULL。这种方法便于标识出一个分支的结束。

树的分支是一系列的结点,从根结点开始到某个叶子结点结束。

叶子结点位于树的边缘,且没有子结点。多颗树组成的集合称为森林。

树的4种周游算法

1、先序遍历

给定一颗树,按照先序遍历的方式,首先访问它的根结点,然后是左子结点,最后是右子结点。按照从左到右的方式依次遍历各个结点,以相同的方式将左子结点和右子结点当做新的子树的根。

先序遍历是按照深度优先的方式遍历结点的。

2、中序遍历

给定一颗树,按照中序遍历的方式,首先访问左子结点,然后是根结点,最后是右子结点。按照从左到右的顺序依次访问各个结点,以相同的方式将左子结点和右子结点当做新的子树的根。

3、后序遍历

给定一颗树,按照后序遍历的方式,首先访问左子结点,然后是右子结点,最后是根结点。按照从左到右的顺序依次访问各个结点,以相同的方式将左子结点和右子结点当做新的子树的根。

4、层级遍历

要用层级遍历周游一颗树,首先访问树的根,然后依次向下层处理,按照从左到右的顺序访问每层的结点。层级遍历运用了广度优先的策略。

 

 树的平衡

对于给定数量的结点,保证树的高度尽可能的短的过程叫做树的平衡。这意味着,在结点加入下一层之前必须保证本层结点满额。正式的说法是,如果满足树的所有叶子节点都在同一层上,或者所有叶子结点都在最后两层上,且倒数第二层是满的,则这颗树是平衡的。

如果一颗平衡树最后一层的所有叶子结点都在最靠左的位置上,则称这颗树是左平衡的。可以利用左平衡二叉树来帮助实现堆和优先级队列。

 

linux
相关资讯       二叉树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款