数据结构系列 - 树的转换

1. 树的存储结构

    通常,树的存储结构有三种,双亲表示法、孩子表示法和孩子兄弟表示法。

(1)双亲表示法

双亲表示法是利用一组连续的存储单元存储树的每个结点,并利用一个指示器表示结点的双亲结点在树中的位置。

树的双亲表示法存储表示描述如下:

 

C代码  收藏代码
  1. #define MaxSize 200
  2. typedef struct PNode        /* 双亲表示法的结点定义 */
  3. {
  4.     DataType data;
  5.     int parent;                    /*[......]

查看全文

数据结构系列 - 线索二叉树

1. 前言

n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为"线索")。
这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded   BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
注意:线索链表解决了二叉链表找左、右孩子困难的问题,出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题。

2. 二叉树线索化的定义

n个结点的二叉树,采用链式存储结构时,有n+1个空链域,利用这些空链[......]

查看全文

数据结构系列 - 二叉树遍历

1. 前言

所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。

2. 二叉树遍历的定义

    二叉树的遍历过程其实也是将二叉树的非线性序列转换成一个线性序列的过程。二叉树是一种非线性结构,通过遍历二叉树,按照某种规律对二叉树中的每个结点进行访问,且仅访问一次,得到一个顺序序列。

从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
(1)访问结点本身(N),
(2)遍历该结点的左子树(L),
(3)遍[......]

查看全文

数据结构系列 - 二叉树

1. 前言 

二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。

 

2. 二叉树的定义

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

二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。
二叉树的五种基本形态如下图所示。

图 二叉树的五种基本形态

3. 二叉树的基本操[......]

查看全文

数据结构系列 - 树

1. 前言

    树形结构是一类重要的非线性结构。树形结构是结点之间有分支,并具有层次关系的结构。它非常类似于自然界中的树。

树结构在客观世界中是大量存在的,例如家谱、行政组织机构都可用树形象地表示。

树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程。

2. 树的定义

    树(Tree)是n(n≥0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:
(1)有且仅有一个特定的称为根(Root)的结点;
(2)其余的结点可分为m(m≥0)个[......]

查看全文

1 2 3 4 10