树
树定义
专业定义:
1、有且只有一个称为根的节点
2、有若干个互不相交的子树,这些子树本身也是一棵树
通俗定义:
1、树是由节点和边组成
2、每个节点只有一个父节点但可以有多个子节点
3、但有一个节点例外,该节点没有根节点,此节点称为根节点
专业术语
节点 父节点 子节点
子孙 堂兄弟
深度:
从根节点到最底层节点的层数称之为深度
根节点是第一层
叶子节点;(叶子就不能劈叉了)
没有子节点的节点
非终端节点:
实际就是非叶子节点。
根节点既可以是叶子也可以是非叶子节点
度:
子节点的个数称为度。(一棵树看最大的)
树分类:
一般树
任意一个节点的子节点的个数都不受限制
二叉树(有序树)
任意一个节点的子节点的个数最多两个,且子节点
的位置不可更改。
分类:
一般二叉树
满二叉树
在不增加树的层数的前提下。无法再多
添加一个节点的二叉树就是满二叉树。
完全二叉树
如果只是删除了满二叉树最底层最右边的
连续若干个节点,这样形成的二叉树就是
完全二叉树。
森林
n个互不相交的树的集合
一般的二叉树要以数组的方式存储,要先转化成完全二叉树,因为如果你
只存有效节点(无论先序,中序,后序),则无法知道这个树的组成方式
是什么样子的。
树的存储(都是转化成二叉树来存储)
二叉树的存储
连续存储【完全二叉树】
优点:
查找某个节点的父节点和子节点(也包括判断有咩有)速度很快
缺点:
耗用内存空间过大
链式存储
一般树的存储
双亲表示法
求父节点方便
孩子表示法
求子节点方便
双亲孩子表示法
求父节点和子节点都很方便
二叉树表示法
把一个普通树转化成二叉树来存储
具体转换方法:
设法保证任意一个节点的
左指针域指向它的第一个孩子
有指针域指向它的下一个兄弟
只要能满足此条件,就可以把一个普通树转化成二叉树
一个普通树转化成的二叉树一定没有右子树
森林的存储
先把森林转化为二叉树,再存储二叉树,具体方式为:根节点
之间可以当成是兄弟来看待
二叉树操作
遍历
先序遍历【先访问根节点】
先访问根节点
再先序访问左子树
再先序访问右子树
中序遍历【中间访问根节点】
中序遍历左子树
再访问根节点
再中序遍历右子树
后序遍历【最后访问根节点】
先后序遍历左子树
再后序遍历右子树
再访问根节点
已知两种遍历序列求原始二叉树
通过先序和中序 或者 中序和后续我们可以
还原出原始的二叉树
但是通过先序和后续是无法还原出原始的二叉树的
换种说法:
只有通过先序和中序, 或通过中序和后序
我们才可以唯一的确定一个二叉树
应用
树是数据库中数据组织的一种重要形式(例如图书馆
的图书分类一层一层往下分。)
操作系统子父进程的关系本身就是一棵树
面向对象语言中类的继承关系本身就是一棵树
赫夫曼树(树的一个特例)
相关推荐
NOIP普及讲座树基础知识.ppt
介绍B-树,B+树等概念,特性,以及B-树与B+的区别
NOIP普及讲座5-树的基础知识(PASCAL).pdf
php基础知识树形图php基础知识树形图php基础知识树形图php基础知识树形图
树的基础知识.pptx
unity3D行为树基础知识讲解以及样例插件
基础知识总结图,回忆树枝图
果树生产基础知识 PPT课件.pptx
果树生产基础知识PPT学习教案.pptx
目 录 基础知识 产品知识(各类产品特有的技术、参数) 销售知识 高级技术培训(针对产品专员、维修人员、工程师) 服务器基础知识培训全文共74页,当前为第1页。 基础知识部分 硬件(名词解释、分类等) 软件(操作...
语文知识树学习语文的基础知识PPT学习教案.pptx
建筑设计基础知识 一、设计任务书编制基本知识 设计任务书是业主对工程项目设计提出的要求,是工程设计的主要依据。进行可行性研究的工程项目,可以用批准的可行性研究报告代替设计任务书。设计任务书一般应包括...
国计算机等级考试二级C,VB等等不同语言笔试部分的公共基础知识考试内容是一样的笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找,对此部分进行重点学习。 详细重点学习知识点: 1....
硬件工程师基础知识 目的:基于实际经验与实际项目详细理解并掌握成为合格的硬件工程师的最基本知识。
二叉树的所有树,但是没有红黑二叉树.二叉树 链表 队列 搜索二叉树 线索二叉树 哈夫曼树 线段树
在分析已有知识表示方法优缺点的基础上,提出一种高效的知识表达模型——概念知识树。概念知识树模型不仅结构性好、表达能力强,而且在应用中具有良好的适应性和延展性,现主要应用于信息检索和自然语言理解领域。以...
《嵌入式软件工程-基础知识、方法和应用》 书 上部分