【数据结构】——-树和二叉树(一)

前端之家收集整理的这篇文章主要介绍了【数据结构】——-树和二叉树(一)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

树,

本文紧介绍树。

一、什么是树?

首先,树也是一种数据结构,但是和之前介绍的线性表、栈、队列等线性结构不同,树 是一种非 线性结构


二、树的基本操作

1)初始化:

2)为指定节点添加字节点。

3)判断树是否为空。

4)返回根节点。

5)返回指定节点的父节点。

6)返回指定节点的所有子节点。

7)返回指定节点的第i个子节点。

8)返回该树的深度

9)返回指定节点的位置。


(1)求根:求树的根节点

(2)求双亲:

(3)求孩子:

(4)建树:

(5)剪枝:

(6)遍历:


三、树的相关术语

结点的度:

叶子:

树的度:

结点的层次:

树的高度:

有序树:

无序树:


(1) 结点的度(Degree)
 树中的一个结点拥有的子树数称为该结点的度(Degree)。
 一棵树的度是指该树中结点的最大度数。
 度为零的结点称为叶子(Leaf)或终端结点。
 度不为零的结点称分支结点或非终端结点。
 除根结点之外的分支结点统称为内部结点。
 根结点又称为开始结点。


(2) 孩子(Child)和双亲(Parents)
 树中某个结点的子树之根称为该结点的孩子(Child)或儿子,相应地,该结点称为孩子的双亲(Parents)或父亲。
 同一个双亲的孩子称为兄弟(Sibling)。


(3)祖先(Ancestor)和子孙(Descendant)
①路径(path)
 若树中存在一个结点序列k1,k2,…,ki,使得ki是ki+1的双亲(1≤i<j),则称该结点序列是从kl到kj的一条路径(Path)或道路。
 路径的长度指路径所经过的边(即连接两个结点的线段)的数目,等于j-1。
注意:
 若一个结点序列是路径,则在树的树形图表示中,该结点序列"自上而下"地通过路径上的每条边。
 从树的根结点到树中其余结点均存在一条惟一的路径。


②祖先(Ancestor)和子孙(Descendant)
 若树中结点k到ks存在一条路径,则称k是ks的祖先(Ancestor),ks是k的子孙(Descendant)。
 一个结点的祖先是从根结点到该结点路径上所经过的所有结点,而一个结点的子孙则是以该结点为根的子树中的所有结点。
约定:
 结点k的祖先和子孙不包含结点k本身。


(4)结点的层数(Level)和树的高度(Height)
 结点的层数(Level)从根起算:
根的层数为1
其余结点的层数等于其双亲结点的层数加1。
 双亲在同一层的结点互为堂兄弟。
 树中结点的最大层数称为树的高度(Height)或深度(Depth)。
注意,
 很多文献中将树根的层数定义为0。


(5)有序树(OrderedTree)和无序树(UnoderedTree)
 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换),则称该树为有序树(OrderedTree);否则称为无序树(UnoderedTree)。
注意:
 若不特别指明,一般讨论的树都是有序树。


(6)森林(Forest)
 森林(Forest)是m(m≥0)棵互不相交的树的集合。
 树和森林的概念相近。删去一棵树的根,就得到一个森林;反之,加上一个结点作树根,森林就变为一棵树。


5.树形结构的逻辑特征
 树形结构的逻辑特征可用树中结点之间的父子关系来描述:
(1) 树中任一结点都可以有零个或多个直接后继(即孩子)结点,但至多只能有一个直接前趋(即双亲)结点。
(2) 树中只有根结点无前趋,它是开始结点;叶结点无后继,它们是终端结点。
(3) 祖先与子孙的关系是对父子关系的延拓,它定义了树中结点之间的纵向次序。
(4) 有序树中,同一组兄弟结点从左到右有长幼之分。
对这一关系加以延拓,规定若k1和k2是兄弟,且k1在k2的左边,则kl的任一子孙都在k2的任一子孙的左边,那么就定义了树中结点之间的横向次序。


总结:从上看下来,感觉好像没多大用处。感兴趣的小伙伴可以继续研究研究哈。

下篇再继续介绍二叉树,唉,说到它头又大了。

原文链接:https://www.f2er.com/datastructure/382315.html

猜你在找的数据结构相关文章