树: 是一种递归定义的数据结构。树( Tree )是树结构的简称,它是一种重要的非线性数据结构。树或者是一个空树,即不含有任何的结点(元素),或者是一个非空树,即至少含有一个结点。
根: 在一棵非空树中,它有且仅有一个节点。
子树: 在一棵非空树中,除根外其余所有结点分属于 m 个( m ≥ 0 )不相交的集合。每个集合又构成一棵树,称为根结点的 子树。
树的递归定义:
树 (Tree) 是 n(n≥0) 个结点的有限集 T , T 为空时称为空树,否则它满足如下两个条件:
(1) 有且仅有一个特定的称为根 (Root) 的结点;
(2) 其余的结点可分为 m(m≥0) 个互不相交的子集 Tl , T2 , … , Tm ,其中每个子集本身又是一棵树,并称其为根的子树 (Subree) 。
注意:树的递归定义刻画了树的固有特性:一棵非空树是由若干棵子树构成的,而子树又可由若干棵更小的子树构成。
树的表示: 树形图表示是树结构的主要表示方法。其他还有广义表、集合图、凹入图三种表示形式。
线性结构和树型结构之间的区别:
线性结构
|
树型结构
|
第一个数据元素(无前驱)
最后一个数据元素(无后继)
其它数据元素
(一个前驱、一个后继)
|
根结点(无前驱)
多个叶子结点(无后继)
其它数据元素
(一个前驱、多个后继)
|
结点 (node) :表示树中的元素,包括数据项及若干指向其子树的分支。
结点的度 (degree) :树中的一个结点拥有的子树数称为该结点的度 (Degree) 。
叶子 (leaf) :度为 0 的结点。
孩子 (child) :结点子树的根称为该结点的孩子。
双亲 (parents) :孩子结点的上层结点叫该结点的。
兄弟 (sibling) :同一双亲的孩子。
树的度 :一棵树中最大的结点度数。
结点的层次 (level) :从根结点算起,根为第一层,它的孩子为第二层……。
深度 (depth) :树中结点的最大层次数。
有序树: 子树的位置自左向右有次序关系的称为有序树,顺序决定了大小,孩子的次序不能改变。
无序树: 子树的位置自左向右无次序关系的称为无序树。
森林 (Forest) 是 m(m≥0) 棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根,就得到一个森林;反之,加上一个结点作树根,森林就变为一棵树。
路径 :若树中存在一个结点序列 k1 , k2 , … , ki ,使得 ki 是 ki+1 的双亲 (1≤i<j) ,则称该结点序列是从 k1 到 kj 的一条路径 (Path) 或道路。
路径的长度: 指路径所经过的边 ( 即连接两个结点的线段 ) 的数目,等于 j-1 。
祖先: 若树中结点 k 到 ks 存在一条路径,则称 k 是 ks 的 祖先 (Ancestor) , ks 是 k 的 子孙 (Descendant) 。结点 k 的祖先和子孙不包含结点 k 本身。
结点的层数: (Level) 从根起算:根的层数为 1 ,其余结点的层数等于其双亲结点的层数加 1 。双亲在同一层的结点互为堂兄弟。树中结点的最大层数称为树的高度 (Height) 或深度 (Depth) 。很多文献中将树根的层数定义为 0 。
树形结构的逻辑特征:
树形结构的逻辑特征可用树中结点之间的父子关系来描述:
( 1 ) 树中任一结点都可以有零个或多个直接后继 ( 即孩子 ) 结点,但至多只能有一个直接前趋 ( 即双亲 ) 结点。
( 2 ) 树中只有根结点无前趋,它是开始结点;叶结点无后继,它们是终端结点。
( 3 ) 祖先与子孙的关系是对父子关系的延拓,它定义了树中结点之间的纵向次序。
( 4 ) 有序树中,同一组兄弟结点从左到右有长幼之分。
对这一关系加以延拓,规定若 k1 和 k2 是兄弟,且 k1 在 k2 的左边,则 k1 的任一子孙都在 k2 的任一子孙的左边,那么就定义了树中结点之间的横向次序。
二叉树 :指数的度为 2 的有序树。是最简单的一种树结构,在计算机领域有着广泛的应用。
二叉树的递归定义: 二叉树或者是一棵 空树 ,或者是一棵由一个 根结 点和两棵互不相交的分别称根的 左子树 和 右子树 所组成的 非空树 ,左子树和右子树又同样都是一棵二叉树。
二叉树中,每个结点的左子树的根结点被称为该结点的 左孩子 ( left child ) , 右子树的根结点被称为 右孩子 ( left child )。
满二叉树: 深度为 K 且含有 2K -1 个结点的二叉树,当树中的每一层都满时成为漫二叉树。
完全二叉树: 在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者在最右边缺少连续若干个结点,则称此树为完全二叉树。
二叉树的抽象数据类型:
ADT BinaryTree is
Data:
// 数据存储结构定义,可采用顺序结构或链接结构
Operation :
void InitBTree(BTreeType& BT); // 初始化
void CreateBTree (BTreeType& BT,char* a);
// 根据广义表创建二叉树
bool BTreeEmpty (BTreeType& BT); // 判断是否为空树
void TraverseBTree (BTreeType& BT); // 遍历
int BTreeDepth (BTreeType& BT); // 求深度
void PrintBTree (BTreeType& BT); // 输出
void CleanBTree (BTreeType& BT); // 清空树中的结点
end BinaryTree
二叉树的存储结构:
1 、顺序存储结构
#define MAX_TREE_SIZE 100 // 二叉数的最大结点数
Typedef {
ElemType SqBiTree[MAX_TREE_SIZE ];//0 号单元存储根结点
}
SqBiTree bt;
2 、链接存储结构
二叉链表 采用独立结点,通常采用的方法是:在每个结点中设置三个域:值域、左指针域和右指针域,其结点结构如 图 5-1 所示:
图 5-1
结点类型描述如下:
Struct BTreeNode
{ ElemType data;
BTreeNode * left;
BTreeNode * right;
};
二叉树的遍历: 二叉树的遍历是二叉树中最重要的运算,顺着某一条搜索路径循序访问二叉树中的结点。使得每个结点均被访问一次,而且仅被访问一次。这样一个过程称之为“遍历”,其中 “ 访问 ” 的含义可以很广,如输出结点的信息 。
|
相关推荐
【数据结构:树和二叉树】 树是一种非线性的数据结构,它的基本概念和术语在计算机科学中至关重要,尤其在算法设计和数据组织中扮演着核心角色。树的定义基于递归,一棵非空树包含一个根节点,以及一组互不相交的...
此外,满二叉树和完全二叉树有特殊的数组表示方法,可以节省空间并优化某些操作。 课件中还涉及到了二叉树的实现,包括创建、插入、删除等基本操作。例如,二叉搜索树(Binary Search Tree)是一种特殊的二叉树,...
### 数据结构之树和二叉树实验报告知识点详解 #### 实验目的 1. **掌握二叉树的结构特征**: - 了解二叉树的基本定义:每个节点最多有两个子节点的树形结构。 - 理解二叉树的特性,如满二叉树、完全二叉树等概念...
在计算机科学领域,树和二叉树是两种重要的数据结构,它们在许多应用中发挥着核心作用,如文件系统、数据库索引、编译器设计等。本篇将深入探讨这些概念及其相关的算法。 首先,我们要理解“树”这一概念。树是一种...
本文将详细介绍树的类型定义、二叉树的存储结构和遍历、线索二叉树、树和森林的表示方法和遍历、哈夫曼树和哈夫曼编码等知识点。 树的类型定义 树是一种数据结构,由一组节点和边组成。每个节点都有一个值和零个或...
树和二叉树-层序遍历二叉树 在计算机科学中,树和二叉树是很重要的数据结构概念。我们可以使用链表来存储二叉树,并使用层序遍历算法来遍历它。层序遍历二叉树的算法可以分为三步:首先,建立二叉树的链表存储结构...
### 东北大学数据结构实验3:树和二叉树 #### 实验背景 本次实验是针对东北大学计算机专业本科生的数据结构课程中的一项实践任务。实验的主要目的是帮助学生深入理解和掌握树形数据结构中的两种基本类型——树...
此外,满二叉树和完全二叉树作为二叉树的特殊形态,也进行了详细阐述。满二叉树是深度为k且恰好有2^k-1个节点的二叉树;完全二叉树则是一种接近满二叉树的结构,其中叶子节点只能出现在最深的两层,且对于任意节点,...
C++作为编程语言,提供了实现这些数据结构和算法的手段,可以利用类和对象来表示树和二叉树的节点,通过指针或引用来表示节点间的连接。理解并熟练掌握树和二叉树的概念、性质以及操作方法,对于解决复杂的算法问题...
在数据结构的学习中,树和二叉树是两个至关重要的概念。它们被广泛应用于计算机科学的各个领域,如操作系统、数据库、编译器设计、图形学等。本实验旨在帮助初学者深入理解树与二叉树的基本概念,通过编写代码来实现...
树和二叉树习题 树是一种特殊的数据结构,它可以用来描述树形结构的数据关系。二叉树是一种特殊的树,每个结点的度最大为 2。下面是关于树和二叉树的习题和答案: 一、选择题 1. 由于二叉树中每个结点的度最大为 ...
树和二叉树 树是一种非常重要的非线性数据结构,广泛应用于描述家族关系或行政组织机构。树由n (n≥0) 个结点的有限集组成,其中有一棵非空树,有且仅有唯一的根(root)结点,除根结点外其余结点可分为m (m>0) 个...
"树和二叉树" 树和二叉树是计算机科学中的一类重要的数据结构,它们广泛应用于编译程序、数据库系统、算法分析等领域。 树的定义和基本概念: 树是 n(n>=0) 个结点的有限集 T,T 为空时称为空树,否则它满足两个...
C++(数据结构):树和二叉树 C++(数据结构):树和二叉树 C++(数据结构):树和二叉树 C++(数据结构):树和二叉树 C++(数据结构):树和二叉树 C++(数据结构):树和二叉树 C++(数据结构):树和二叉树 C++(数据结构):树...
"二叉树面试题 树和二叉树总结" 本资源摘要信息涵盖了树和二叉树的面试题总结,包括选择题和解释。涵盖的知识点包括树和二叉树的定义、性质、操作和应用等。 一、树和二叉树的定义 树是一种数据结构,由一个根...
数据结构完整实验报告 实验3:树和二叉树的应用-哈夫曼编码设计
【树和二叉树的转换】是一个数据结构领域的重要主题,涉及到树形数据结构与二叉树之间的相互转化。在实际应用中,由于二叉树的特性使得它们在某些操作上更加简便,如搜索、排序等,因此有时需要将树转换为二叉树以便...