数据结构第五章 树 |
第五章 树
1.基本概念
定义
非空有限的节点集合
递归定义
树根、子树
非递归定义
父节点、子节点、叶节点、路径
相关术语
度(或次数)
叶节点、分支节点
结点的层数(根节点为0)
边、路径、路径长度
子孙节点、祖先结点
深度(从根出发)、高度(从叶出发)、树的高度
森林
有序树和无序树(默认有序)
有根树和有序树(本章默认有根)
比较
线性结构
一个前驱、一个后继
树结构
一个前驱、多个后继
表示方法
集合嵌套
凹入
广义表
树形
基本操作
判空、求根
求父亲、求儿子、求兄弟
建树、求树的深度
树的遍历
2.二叉树
基本概念
定义
递归定义
五种形态
可为空,子节点有序,是平行于树的概念
性质
层数为i的结点至多个
高度为k的二叉树至少k+1个结点,至多 个结点
叶节点数等于度为2的节点数+1
满二叉树、完全二叉树
层次顺序编号相同
父节点、左孩子、右孩子的编号特点
结点完全二叉树的高度是
存储
顺序存储
定义
按层次顺序
存储空间地址连续
结点编号反映逻辑关系
完全二叉树:按层次顺序编号
非完全二叉树:添加虚节点
链接存储
节点结构
数据域、左指针、右指针
数据域、左指针、右指针、父指针
操作
查父节点
Father(t,p.q)
查找某个符合条件的结点
Find(t,item.q)
删除给定子树
DST(t), Del(p)
操作
遍历
分类
前序(先根)遍历
Preorder(t)
中序(中根)遍历
Inorder(t)
NIO(t)
后序(后根)遍历
Postorder(t)
NPO(t)
逆波兰表达式
层次遍历
LevelOrder(t)
前序、后序、层次遍历中任意一个和中序遍历均可确定一棵二叉树
创建(CreateBinTree)
需要在先根序列中加入空指针标识符作为输入
复制(CopyTree)
计算结点个数、高度等