学习数据结构中的树,二叉树

 
本文最后更新于

本文摘选自某本数据结构教材

在线性表的存储结构上,数组和链表定义的是顺序访问结点对象的集合,它是线性表的存储基础。在操作上,线性表结构除了头尾元素外,每个结点都只有唯一的前驱和后继。这个特点使得线性表的遍历等操作变的简单,因为从一个结点到它的后继结点只有唯一的一条路径。但是,在许多实际应用中,对象呈现出一种非线性的次序,其主要表现为结点可能有多个后继。也就是说,从这些结点到它的后继结点,存在多个选择分支。很像自然界中一棵倒长着的树。

与线性表的数据结构一样,这种树状结构类型的数据结构在客观世界中的应用是广泛存在的。从这里也可以很容易看出,线性表这种顺序结构是树状结构的一个特例。

一些树的常用术语

1 结点(Node)和边(Edge)

树的每个数据元素称为一个结点。两个结点之间如果具有一条边连接,那么称这两个结点之间存在一条边。对于树的每个结点,除了要关心结点本身包含的信息外,还要关心不同结点之间的连接状态。对于一棵具有 n 个结点的树,它有 n-1 条边。

2 结点的度(Degree)

树的一个结点拥有的子树的个数称为该结点的度(Degree),最大的结点的度称为树的度。结点的度和树的度 共同体现了树的宽度,也就是体现了结点的分支数和树的发散程度。从度的定义很容易得到,线性表是一种特殊的树状结构,它的度为 1。

3 根结点(Root)和叶子(Leaf)

树中没有前驱的结点称为根结点,它又称为开始结点。树中度为零的结点称为叶子结点,它又称为终端结点。树中度不为零的结点称为分枝结点或者称为非终端结点。除根结点外的分枝结点统称为内部结点。

4 孩子结点(Child)和双亲结点(Parents)

树中某个结点的子树的根称为该结点的孩子结点(Child)。相应地,该结点称为孩子的双亲结点(Parents)。具有同一个双亲结点的孩子结点相互称为兄弟结点(Sibling)。对于兄弟结点,从左到右,第一结点是大兄弟结点,第二个称为二兄弟结点,其他依次类推。

5 路径(path)

如果树中存在一个结点序列 k1,k2,…,kj,并且 ki是 ki+1的双亲结点(1≤i<j),那么称该结点序列是从 k1到 kj 的一条路径(path )或道路。

路径的长度指路径所经过的边(即连接两个结点的线段)的数目,它等于路径所包含的结点数减 1。从树的根结点到树中其余任何结点均存在一条唯一的路径。

6 祖先(Ancestor)和子孙(Descendant)

如果树中结点 kA到结点 kD之间存在一条路径,那么称结点 kA是结点 kD的祖先结点(Ancestor),kD是 kA的子孙结点(Descendant)。一个结点的祖先是从根结点到该结点路径上所经过的所有结点,而一个结点的子孙则是以该结点为根的子树中的所有结点。(本书约定:一个结点的祖先和子孙不包含该结点本身。)

7 结点的层数(Level)和树的高度(Height)

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

8 有序树(OrderedTree)和无序树(UnoderedTree)

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

9 森林(Forest)

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

从树的相关术语可以看出,树的逻辑特征可用树结点之间的父子关系来描述:树中任一结点都可以有零个或多个直接后继(即孩子)结点,但至多只能有一个直接前趋(即双亲)结点,这个是树与线性表的最大区别之一。

树中只有根结点无前趋,它是开始结点;叶结点无后继,它们是终端结点。一棵树只能有一个根结点,但是可以有多个叶子结点。

树结点的祖先与子孙的关系是对父子关系系的延拓,它定义了树结点之间的纵向次序。

有序树中,兄弟结点从左到右有长幼之分。规定若 k1 和 k2 是兄弟,且 k1 在 k2 的左边,则 k1 的任一子孙都在 k2 的任一子孙的左边,那么就定义了树中结点之间的横向次序。

树的表示方法

  • 直观表示法
  • 嵌套集合表示法
  • 凹入表示法
  • 广义表表示法
  • 形式化表示法

树的抽象数据类型

抽象数据类型(Abstract Data Type, ADT)是计算机科学中具有类似行为的特定类别的数据结构的数学模型;或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是间接定义的,通过其上的可执行的操作以及这些操作的效果的数学约束(与可能的代价)。

树的抽象数据类型包含了三个方面,它们分别是数据对象 D、数据关系 R 和基本操作P。

ADT Tree
{
  数据对象 DD 是具有相同特性的数据元素所构成的结点集合。
  数据关系 R:结点之间的父子关系描述
  基本操作 P:树的基本操作所构成的集合
    构造和插入类:
    删除类:
    查找和修改类:
}

数据对象 D:它包含了具有相同特性的数据元素所构成的结点集合。每个结点的信息包括两个领域,一个是描述数据元素信息域,另外一个指示结点之间关系的指向域。根据结点的存储方式是数组还是链式,指向域可以包含记录下标的整型变量或者指针变量。

数据关系 R:它主要描述结点之间的父子关系,通过对结点之间的父子关系描述,可以完整的描述整个树的结构。其具体如下:

若 D=φ,则 R=φ,称 Tree 为空树; 若 D≠φ,则: 1)在 D 中存在唯一的称为根的数据元素 root。 2)当 n>1 时,除根结点 root 外的所有其他结点可分为 m (m>0)个互不相交的有限子集 T1,T2,…, Tm,其中,每一棵子树本身又是一棵符合本定义的树,称为根root 的子树。

基本操作 P:它主要描述了树的基本操作。根据其涉及的功能特点,这些基本操作可以分为构造和插入操作、删除操作以及查找和修改操作这三个方面。

构造和插入操作包括树的构造,结点的构造和插入,分支的插入等操作;删除操作包括了结点的删除,分支的删除,树的删除等方面的操作;查询操作包括了结点的查找和访问。

树的存储结构

1 顺序存储

顺序存储是利用数组这种顺序存储的内存空间来存储树中的每一个结点,根据数组的产生方式,可以分为静态数组和动态数组。

typedef int datatype;
typedef struct node
{
  datatype data; /* 结点的数据信息 */
  int parent; /* 双亲结点的数组下标 */
}Pnode;

2 链式存储法

链式存储是采用类似链表这种结构来存储树的结点。每个结点中都包含了一个指针域,指针域包含了若干个指针,每个指针指向了该结点的孩子结点或者兄弟结点。。链式存储法根据结点的指针指向的信息,可以进一步分为孩子表示法和孩子-兄弟表示法。

在树的孩子表示法中,每一个结点都包含了一个指针域,指针域的指针指向该结点的孩子结点。指针个数设计方法:一种是固定指针数量,另外一种是非固定指针数量。固定指针数量法是根据树的度来确定每个结点的指针域所包含指针的数量。非固定指针数量法是树中每个结点包含的指针数量是根据本结点的度来设置。

孩子-兄弟链表表示法,表示比较规范,不仅适用于多叉树的存储,也适用于森林的存储。结点结构是:一个 数据域和两个指针,一个指针指向它的最左边的孩子结点,另一指针指向它左边的第一个兄弟结点。

3 数组链式存储法

双亲孩子表示法是在双亲表示法的基础上,通过保存每个结点的所有孩子结点的地址信息来实现。具体实现可以把每一个结点的所有孩子的地址信息保存在一个单链表中。然后在每个存储结点中,增加一个单链表的头结点指针。

typedef int datatype;
typedef struct Snode /* 兄弟结点单链表的结点描述 */
{
  datatype data; /* 结点的数据信息 */
  struct Snode *next; /* 指向兄弟结点的指针 */
}Siblingnode;
typedef struct node
{
  datatype data; /* 结点的数据信息 */
  int parent; /* 双亲结点的数组下标 */
	Siblingnode *head; /* 指向孩子结点单链表的头结点 */
}PCnode;

二叉树

树的形态有很多种,在实际的使用过程种,需要对树的形态进一步地进行约束和简化,以便于设计和操作。二叉树是树形结构的一个重要类型,,许多实际问题抽象出来的数据结构往往是二叉树的形式。特别是根据树的孩子-兄弟表示法,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。

二叉树(Binary Tree)的定义

二叉树是一个具有 n(n≥0)个结点的有限集合。它或者是空集(n=0),这时称二叉树是一棵空树;或者由一棵根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

二叉树与无序树不同。

二叉树与度数为 2 的有序树不同。

二叉树的两种特殊形态

满二叉树(Full Binary Tree)

如果一棵二叉树的所有叶子结点都在同一层上,并且所有的非叶子结点的度都为 2,那么称这棵二叉树为满二叉树。

       a
     /    \
    b      c
  /  \    /  \
 d    e  f    g

深度为 k 的满二叉树具有 2^k-1 个节点。

完全二叉树(Complete Binary Tree)

一棵具有 n 个结点的二叉树,如果它的结构与一棵满二叉树的前 n 个结点的结构相同,那么称这棵二叉树为完全二叉树。

       a                     a
     /    \                /   \ 
   b       c     <==>     b      c
  /  \                  /  \    /  \
 d    e                d   e   f    g
  
  完全二叉树     <==>     满二叉树

二叉树的性质

  1. 二叉树第 i 层上的结点数目最多为 (i≥1)。

  2. 深度为 k 的二叉树至多有 个结点(k≥1)。

  3. 设满二叉树的深度为 k,那么满二叉树的结点数量为

  4. 具有 n 个结点的完全二叉树的深度 k 为 ([ ]为取整符号)。

  5. 在任意一棵二叉树中,若叶子结点的个数为 ,度为 1 的结点数为 ,度为 2 的结点数为 ,则

  6. 对具有 n 个结点的完全二叉树,以深度方向为序对所有结点进行编号 (1≤i≤n),也就是结点的编号顺序为:深度方向是从上到下,每一层的结点是从左到右。那么,对于编号为 i (i≥1) 结点:

(1) 当 i=1 时,该结点为根,它无双亲结点;
(2) 当 i>1 时,该结点的双亲结点编号为 i/2 ( /为整除 );
(3) 若 ,它有编号为 的左孩子结点,否则没有左孩子;
(4) 若 ,则它有编号为 的右孩子结点,否则没有右孩子。

二叉树的抽象数据类型

二叉树的抽象数据类型包含了三个方面,它们分别是数据对象 D、数据关系 R 和基本操作 P。

ADT Binary Tree
{
  数据对象 DD 是具有相同特性的数据元素所构成的结点集合
  数据关系 R:结点之间的父子关系描述
  基本操作 P:树的基本操作所构成的集合
    构造和插入类:
    删除类:
    查找和修改类:
}

二叉树的存储结构

1 顺序存储

适用与满二叉树,完全二叉树,按照从上到下,从左到右的顺序进行标号。结构既简单又节省存储空间。(本书中,结点的序号从 1 开始,而数组的下标从 0 开始)

2 链式存储法

二叉树的链式存储结构常见的有二叉链结构和三叉链结构。

二叉链结构的每个结点由数据域和指针域组成,数据域用于保存结点的数据信息,指针域包含了两个结点指针。其中,一个指针指向左孩子所在结点的存储地址,这种指针称为左指针;另一个指针指向右孩子所在结点的存储地址,这个指针称为右指针,结点的存储的结构为:Lchild | data | Rchild

typedef int datatype;
typedef struct node
{
  int data;				/* 数据域 */
  struct node *lchild;	/* lchild 是左子树根结点指针 */
  struct node *rchild;	/* rchild 是右子树根结点指针 */
}Bnode;

三叉链结构是二叉树的另外一种链式存储方式,三叉链的结点和二叉链的结点相比,多了一个指向双亲结点的指针:Lchild | data | Rchild | parent

typedef char datatype;
typedef struct Tnode
{
  datatype data;		/* 数据域 */
  struct Tnode *lchild;	/* lchild 左子树根结点指针 */
  struct Tnode *rchild;	/* 右子树根结点指针 */
  struct Tnode *parent;	/* 是双亲指针域 */
} Bnode;

二叉树的二叉链存储结构的实现及应用

在二叉链存储结构下,下面给出了二叉树的结点定义、树的初始化操作、左结点的插入操作、右结点的插入操作、左子树的删除操作、右子树的删除操作的 C 语言过程函数。

(略)

二叉树的遍历

遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中,常常需要按一定顺序对二叉树中的每个结点逐个进行访问,查找具有某一特点的结点。通过一次完整的二叉树遍历,可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说,遍历操作使非线性结构线性化。

1 先根遍历

void PreOrder(Bnode *root)
{
  if (root == NULL) return;	/*递归调用的结束条件*/
  Visite(root ->data);		/*访问结点的数据域*/
  PreOrder(root ->lchild);	/*先序递归遍历 root 的左子树*/
  PreOrder(root ->rchild);	/*先序递归遍历 root 的右子树*/
}

         1
      /     \
    2         5
   /        /   \
  3        6     7
   \
     4

2 中根遍历

void PreOrder(Bnode *root)
{
  if (root == NULL) return;	/*递归调用的结束条件*/
  PreOrder(root ->lchild);	/*先序递归遍历 root 的左子树*/
  Visite(root ->data);		/*访问结点的数据域*/
  PreOrder(root ->rchild);	/*先序递归遍历 root 的右子树*/
}

         4
      /     \
    3         6
  /         /   \
 1        5       7
  \
    2

3 后根遍历

void PostOrder(Bnode *root)
{
  if (root == NULL) return;				/* 递归调用的结束条件 */
  PostOrder InOrder (root ->lchild);	/* 先序递归遍历 root 的左子树 */
  PostOrder InOrder (root ->rchild);	/* 先序递归遍历 root 的右子树 */
  Visite(root ->data);				/* 访问结点的数据域 */
}

         7
      /     \
    3         6
  /         /    \
 2         4      5
  \
    1

线索二叉树

。由于二叉树中存在大量的空闲指针,因此我们可以把二叉树的空闲指针用来保存二叉树结点的某种遍历序列关系,这就是我们下面要讨论的线索二叉树。

leftThread | lChild | data | rChild | rightThread

1) 左标志 ltag:当 ltag=0 时,lchild 指针是指向该结点的左孩子。当 ltag=1 时,lchild 指向该结点的遍历顺序的前驱结点。称 lchild 为左线索(leftThread)。 2) 右标志 rtag:当 rtag=0 时,rchild 指针指向该结点的右孩子结点。当 rtag=1 时,rchild 指向该结点的遍历顺序的后继结点。称 rchild 为右线索(rightThread`)。

二叉树、树和森林

树、森林到二叉树的转换是一个常见问题。对于一般树,树中孩子的次序并不重要,只要保证双亲与孩子的关系正确即可。但在二叉树中,左、右孩子的次序是严格区分的。

树和二叉树的转换

(1)加线:各兄弟结点之间用虚线相连。可理解为每个结点的兄弟指针指向它的一个兄弟。

(2)抹线:对每个结点仅保留它与其最左一个孩子的连线,抹去该结点与其他孩子之间的连线。可理解为每个结点仅有一个孩子指针,让它指向自己的长子。

(3)旋转:把虚线改为实线,并且从水平方向向下旋转 45°,成右斜下方向。原树中实线成左斜下方向。这样树的形状呈现为一棵二叉树。