数据结构之“树”(c语言实现)-创新互联
树可以用几种方式定义,其中一种自然的方法是递归方法
创新互联2013年至今,是专业互联网技术服务公司,拥有项目成都网站设计、成都网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元安塞做网站,已为上家服务,为安塞各地企业和个人服务,联系电话:028-86922220一棵树是一些节点的集合,有些节点具有特殊的叫法(如“根”),这个集合可以是空集,若非空,则一棵树则是根与数个或零个的非空的子树的集合
树是由一条条有向的边所连接
1.2树的基本特征1.2.1树的基础相关概念
根(root):树的开始节点
如果树拥有子树,则子树同样拥有自己的根,如上图二叉树中始根有两个子树,两个子树拥有对应自己的根
儿子(child) : 每一棵子树的根叫做根(root)的儿子(真是令人眼前一黑的神级翻译)
父亲(parent):根(root)是每一棵对应此根的子树的根的父亲
树叶(leaf):没有儿子的节点叫做树叶
兄弟(sibling):具有相同父亲的节点叫做兄弟
同样的可以明确祖父(grandparent)与孙子(grandchild)的关系
1.2.2树的一般结构
一棵树由N个节点与N-1条边组成,一般的,其中位于头部的节点是树的根,每条边都将他的节点连接到他的父亲,去除树的根外,每一个节点都有他的父亲,去除树叶,每一个节点都有他的儿子
1.2.3树的结构关系概念
路径(path):从节点n1到nk的一个序列,此序列使得对于从n1到nk的的每一个节点都顺序是下一节点的父亲,
路径的长(length):该路径上的边的条数
深度(depth):对于任意节点,从根到节点的的唯一路径的长,根的深度为0
高度(height):对于任意节点,从节点到一片树叶的最长路径的长,所有树叶的高度都为0
关系补充:
如果存在从n1到n2的一条路径,则n1是n2的一位祖先(ancestor),而n2是n1的一位后裔(descendant)
对于n1!=n2的情况,那么n1是n2的一位真祖先(ancestor),而n2是n1的一位真后裔(descendant), (类比于集合的基础知识)
2树的实现 2.1如何实现一个树?使用c语言为例,很自然的可以想到利用结构体来创建一个“树”数据结构
但是问题是我们事先不知道各个节点的儿子数,它可以变化很大,因此我们无法直接区建立根与子树的联系,否则对于空间是一种浪费
于是可以这样解决:将每个节点的所有儿子放在树节点的链表中,如下例
typedof struct TreeNode *PtrToNode
struct TreeNode
{
ElementType Element;
PtrToNode FirstChild;
PtrToNode NextSibling
}
以下面的树为例(画的比较抽象,抱歉)
利用上述方法,可得
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前题目:数据结构之“树”(c语言实现)-创新互联
网站URL:http://myzitong.com/article/hcopc.html