技术

数据结构之树

树的相关概念

树在数据结构中非常重要，应用也有很多。下面只记录一些重要的、基础性的概念。

  • 结点：树由结点构成的，有根节点、叶结点等。结点有用的子树数就是结点的度，叶结点度为0.同一个父节点的结点互为兄弟，跟人一样，就不介绍，有点弱智的感觉。
  • 树的深度： 树的根层次为1，根的子结点层次为2，依次类推。树中结点的最大层次即为树的深度或者高度。

树的存储结构和实现

在上面概念中说了树中的结点关系和人一样，树的存储就是把这些结点关系存起来。根据人的经验，从不同角度介绍某个人的方式是不一样的，介绍你亲姐：这是我姐，这是我父母的女儿……数的存储和实现也一样。

  1. 双亲表示法 |data|parent| data存储数据，parent指向结点的父节点在存储数组中的下标
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #define MAX_TREE_SIZE 100
    typedef struct PTNode{
    	int data;
    	int parent;
    } PTNode;
    typedef struct{
    	PTNode nodes[MAX_TREE_SIZE];
    	int r, n;  //分别保存根节点的位置和结点数
    } PTree;

以上只是一个最简单最基本的实现，完全可以根据自己的要求更改，比如可以在PTNode中加入堂兄结点的位置等等。

  1. 孩子表示法
  • |data|child1|child2|……
    每个结点存储自己结点的数据，以及其子结点的指针，构成多重链表。
  • |data|degree|child1|child2|……|childd|
    上面那个结构会浪费较多的空间，所有建立一个degree，但是问题是每个结点的结构不一样，运算会很麻烦，又产生下面的结构：
  • 分为两种结点结构，一个是孩子结点链表，一种是表头结点 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #define MAX_TREE_SIZE 100
    typedef struct CTNode  //孩子结点
    {
    	int child;
    	struct CTNode * next;  //指向下一个孩子结点
    } *ChildPtr；
    typedef struct  //表头结点
    {
    	int data;
    	ChildPtr firstchild;  //指向第一个孩子结点
    } CTBox;
    typedef struct
    {
    	CTBox nodes[MAX_TREE_SIZE];   //结点数组
    	int r, n;  //根的位置和结点数
    } CTree;

上面的这个结构还是有不足的，比如我有一个结点，我怎么知道这个结点的父节点呢，所以可以在上面那个表头结点中加一个父节点的信息，这个不贴代码了。

  1. 孩子兄弟表示法 |data|firstchild|righsib|
    这个结构就是结点的第一个子结点和一个右兄弟……实现如下
    1
    2
    3
    4
    5
    6
    typedef struct CSNode
    {
    	int data;
    	struct CSNode * firstchild;
    	struct CSNode * rightsib;
    } CSNode, *CSTree;

如果认真观察上面的结构，就会发现变成一个二叉树结构……二叉树可是树中最最重要的……
综上，几种树表示方法和实现就搞定了。

二叉树

正常智商都能理解到二叉树就是有最多两个叉(分支)的树，这个结构简单、极具特点，很有意义。

二叉树特点：

  • 每个结点最多两个子树
  • 左子树和右子树是有顺序的
  • 如果结点只有一个子树，也是要区分左右子树的(这个区分二叉树的形态)
    因为二叉树的特点，产生了很多特殊二叉树
  1. 斜树：所有结点只有左结点或者右结点，分别叫左右斜树
  2. 满二叉树：所有分支结点都有左右子结点，而且叶结点都在同一层
  3. 完全二叉树：除了最下面一层，都是满的，而且最下面左面连续（满二叉树就是一种特殊的完全二叉树）

二叉树的性质

  1. 在第i层最多有2^(i-1)个结点
  2. 深度为k的二叉树最多有2^k-1个结点
  3. 对于任意一个二叉树，叶结点为n0，度为2的结点数(就是有两个子结点)为n1,则有n0 = n1+1
  4. 具有n个结点的完全二叉树，深度[logn]+1,其中[logn]表示不大于logn的最大整数
  5. 一棵n结点的完全二叉树，结点按层序编号，对于结点i，
    ++ i=1，则结点i为根，无父结点；如果i>1,则父结点是[i/2]
    ++ 2i>n,则结点i不存在左孩子(是叶结点)，否则其左孩子为结点2i
    ++ 2i+1>n, 则结点i无右孩子，否则右孩子为结点2i+1

二叉树的存储与实现

之前有说过树的存储和实现，有很多方法，二叉树也可以使用之前的那些方法。不过由于二叉树比较特别，所以有更加方便简单的实现。

  1. 顺序存储结构
  • 如果是完全二叉树，按照层次依次对结点编号，那么直接按照标号依次顺序存储即可，很简单.
  • 当然如果不是完全二叉树，也按照完全二叉树编号，在不存在的结点设置为’null’什么的都行，然后依次顺序存储。这样一棵斜树就会出现极度浪费空间的情况，这也是顺序存储的一个局限。
  1. 二叉链表
    上面谈到顺序存储的局限，我们就是用链表来实现二叉树，结构很简单|lchild|data|rchild|。data存储结点数据，两边分布存储其左右孩子结点指针。结构定义如下：
    1
    2
    3
    4
    5
    6
    typedef struct BiNode
    {
    	int data;
    	struct BiNode * lchild;
    	struct BiNode * rchild;
    } BiNode, * BiTree;

以上就可以很好完成二叉树的实现，如果要添加结点或者删除结点都非常简单，也可以增加指向父结点的指针……都可以，根据自己的需求改一改就OK了。

二叉树的遍历

如果一棵树中，需要找寻需要的内容，那么久需要二叉树的遍历。遍历是非常重要的内容。
定义： 从根节点出发，按照某种次序访问所有二叉树结点，使每个结点被访问有且仅有一次。

二叉树遍历方法

前序遍历

如果二叉树为空，返回空；否则先访问根节点，再前序遍历左子树，再前序遍历右子树(很明显这是一个递归过程)。

1
2
3
4
5
6
7
8
void PreOrder(BiTree T)  //BiTree 结构在前面阐述过
{
	if(T == NULL)
		return;
	printf("%c",T->data);
	PreOrder(T->lchild);
	PreOrder(T->rchild);
}

中序遍历

如果二叉树为空，返回空；否则从根节点开始（不是访问根节点），中序遍历根结点的左子树，然后访问根节点，最后中序遍历根结点的右子树。

1
2
3
4
5
6
7
8
void InOrder(BiTree T)  
{
	if(T == NULL)
		return;
	InOrder(T->lchild);
	printf("%c",T->data);
	InOrder(T->rchild);
}

后序遍历

如果二叉树为空，返回空；否则从左到右、先叶结点再父结点遍历访问左右子树，在访问根节点。

1
2
3
4
5
6
7
8
void PostOrder(BiTree T)
{
	if(T == NULL)
		return;
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		printf("%c",T->data);
}

层序遍历

如果二叉树为空，返回空；否则从树的第一层开始，从上到下逐层遍历，同一层，从左到右顺序访问。
由于之前的树结构不太适合这个，所以就没有实现代码了，了解就行啦。

二叉树的建立

前面说了二叉树的存储和实现，以及遍历方式。但是怎么利用相应的结构建立一棵二叉树呢？
使用前序遍历的方式进行递归创建，空树就用‘#’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void createBiTree(BiTree * T)
{
	int ch;
	scanf("%c",&ch);
	if(ch == '#')
		*T = NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiNode));
		if(!*T)
			return;
		(*T)->data = ch;
		createBiTree(&(*T)->lchild);
		createBiTree(&(*T)->rchild);
	}
}

二叉树的线索化

当我们建立好二叉树后，我们会发现一些查找和搜索工作都不方便，而且建立的二叉树很多空间其实都是没有利用，所以我们把这些‘#’空间换成这些结点的前驱或者后继。

树其实还有很多内容，但是我水平有限，只能分享一些基础的知识。有时间会继续分享关于树的其他知识点。