一篇文章讲透数据结构之树and二叉树

一.树

1.1树的定义

树是一种非线性的数据结构，它是有n个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根在上，叶在下的。

在树中有一个特殊的结点，称为根结点，根结点没有前驱结点

除根结点外，其余的结点被分成了M个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱结点，但可以有0个或多个后继结点。因此：树是递归定义的。

注意：树的结点之间是不可以有交集的，有交集的话就不是树了，至于是什么我们后期再说。

如下图：以A为根节点的就不是树，以D为结点的才是树。

  

1.2树的基本概念

1. 结点的度：一个结点含有的子树的个数称为该结点的度
2. 叶子结点：度为0的结点称为叶子结点
3. 分支结点：度不为0的结点
4. 双亲结点/父结点：若一个结点包含子节点，则这个结点称为其子结点的父节点
5. 孩子结点/子节点：一个结点含有的子树的根结点称为该结点的子节点
6. 兄弟结点：具有相同父节点的结点互称为兄弟结点
7. 树的度：一棵树中，度最大的结点的度称为树的度
8. 结点的层次：定义根为第一层，根的子节点为第二层，依次类推即可
9. 树的高度或深度：树中结点的最大层次
10. 堂兄弟结点：双亲在同一层的结点互为堂兄弟结点
11. 结点的祖先：从根到该结点所经分支上的所有结点。
12. 子孙：以某结点为根的子树的任一结点都称为该结点的子孙。
13. 森林：由m棵互不相交的树组成的集合称为森林。

1.3树的表示方法

我们在这里学习三种树的表示方法，分别为双亲表示法、树的孩子表示法、左孩子右兄弟表示法。

我们将用这三种方法来表示这一棵树：

1.3.1父节点表示法（双亲表示法）

树的父节点表示法，是利用顺序表来完成的，怎么做呢？

首先，我们创建顺序表结构体来存储结点的内容以及父节点的下标。我们将这个结构体称为结点结构体。

然后，我们创建树的结构体，其中一个是结点结构体数组，一个是数组内元素个数。

由此，我们可以写出如下代码：

//双亲表示法
//顺序表的方式存储
//顺序表存储结点的数据和双亲结点的下标
typedef int DataType;
typedef struct Node
{
	DataType data;//数据域
	int parent;//双亲结点下标
}Node;
//树-->结点组成的数组
typedef struct Tree
{
	Node NodeArr[10];//保存结点的数组，也可以动态申请
	int size;//结点个数
};

在这里需要我们大家注意的是：由于根节点没有前驱结点，我们将其的父节点特别记为-1. 

下面我们来表示一下这棵树。

1.3.2树的孩子表示法

树的孩子表示法是通过顺序表和链表结合的形式表示的

它的原理是：

• 先定义一个单链表结构体表示一个父节点的所有孩子结点的下标，一个孩子指向另外一个孩子
• 然后用一个顺序表结构体存储当前结点的数值以及这个结点的第一个孩子结点的下标
• 最后定义一个树结构体

那么，我们就可以写出如下代码：

typedef int DataType;
//链表
struct ListNode
{
	int child;//当前孩子结点下标
	struct Listnode* next;//下一个孩子
};
//顺序表
struct Node
{
	DataType data;//结点的数据
	ListNode* FirstChild;//第一个孩子
};
struct Tree
{
	Node NodeArr[10];
	int size;
};

现在我们画图来理解一下这个方法

• 绿色的是全部的链表结构体（每个单链表之间没有关系）
• 绿色的每一块是一个单链表
• 紫色中的每一块是一个顺序表
• 由于图的篇幅有限，将一个树分开画了，紫色的其实是一个整体
• 紫色每一块的右下角是元素的个数

 

这个方法的缺点就是：我们要在顺序表中插入或者删除数据需要移动大量的数据。 

1.3.3左孩子右兄弟表示法

这个是最常用的表示树的的方法，即定义两个指针，让左指针指向最左边的子节点，右指针指向兄弟节点。

如果没有节点，则都指向空。

typedef int DataType;
struct Node
{
	struct Node* leftChild;//孩子结点
	struct Node* rightBrother;//指向下一个兄弟结点
	DataType Data;//数据域
};

我们下面具体画一下图： 

1.4树的实际应用

在linux环境下目录结构就是有一颗树构成。

而在Windows环境下，目录许多内容并不交叉，所以是由森林构成。

二.二叉树

2.1二叉树的定义

一棵二叉树是结点的一个有限集合，该集合：

1.或者为空

2.由一个根节点加上两棵别称（别名/外号）为：左子树、右子树的二叉树组成

从上图可以看出

• 二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，次序不能颠倒， 因此二叉树是有序树

我们可以将一棵二叉树拆分开来，我们会发现任何一棵二叉树都是由以下几种情况复合而来的：

下面给大家看一张现实生活中存在的二叉树： 

2.2特殊的二叉树

• 满二叉树：

一个二叉树，如果每一层的节点数都达到了最大值，那么这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1，则它就是满二叉树。

• 完全二叉树：

完全二叉树是一种效率很高的数据结构。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到n的结点都可以一一对应时，则可称之为完全二叉树。也就是说：满二叉树是一种特殊的完全二叉树。（文字表述蛮抽象的，其实就是倒数第二层满，最后一层的叶子结点要从左往右放）

2.3二叉树的相关性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 n0＝n2＋1

4.若规定根结点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1)

5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对
于序号为i的结点有：

1. 若i>0，i位置结点的双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

结论3的推导过程：

 其余结论的推导过程可参考：堆的实现 

2.4二叉树的存储

二叉树一般使用两种结构存储，一种顺序结构，一种链式结构。

2.4.1顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树。

因为不是完全二叉树会有空间的浪费。

而现实中使用中只有堆才会使用数组来存储，关于堆的实现可以参考上面的链接。

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

如下图，左边是完全二叉树，不会有空间浪费；

右边是不完全二叉树，有空间浪费。

2.4.2链式存储 

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

如下图所示：

最左边是存储结构，中间是二叉树实例，右边是逻辑结构图。

在这里我们采用链式结构来存储二叉树：

2.5二叉树的遍历

二叉树的遍历方式有四种：前序遍历、中序遍历、后序遍历、层序遍历

二叉树的前、中、后序遍历都可以通过递归和用栈模拟递归实现，这里我们学习这两种方法.

大家可以先研究代码，理解困难的话可以根据视频学习：

视频1：

视频2：

2.5.1前序遍历

前序遍历：先遍历根节点，再依次遍历左子树，右子树。而遍历左子树，又要先遍历根节点，再依次遍历左子树，右子树…...直到遍历完整棵树。

递归实现 

void PreOrder1(BTree* root)
{
	assert(root);
	if (!root)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

 非递归实现

typedef BTree* STDataType;
void PreOrder2(BTree* root)
{
	//开辟一个栈
	Stack s;
	StackInit(&s);
	BTree* p = root;
	while (p || !IsEmpty(&s))
	{
		if (p != NULL)
		{
			printf("%d ", p->data);
			StackPush(&s, p);
			p = p->left;
		}
		else
		{
             p = StackTop(&s);		    
             StackPop(&s);
			p = p->right;
		}
	}
}

2.5.2中序遍历

先遍历左子树，再依次遍历根节点，右子树。而遍历左子树，又要先遍历左子树，再依次遍历根节点，右子树…直至遍历完整棵树。

递归实现

void Inorder1(BTree*root)
{
    if (root == NULL)
    {
        return;
    }
    PreOrder(root->left);//左子树
    printf("%d ", root->data);//根节点
    PreOrder(root->right);//右子树
}

非递归实现 

  typedef BTree* STDataType;
  void Inorder2(BTree* root)
  {
	  Stack s;
	  InitStack(&s);
	  BTree* p = root;
	  while (p || !IsEmpty(&s))  
	  {
		  if (p != NULL)//入栈
		  {
			  StackPush(&s, p);
			  p = p->left;
		  }
		  else
		  {
			  p = StackTop(&s);
			  StackPop(&s);	  
			  printf("%d ", p->data);
			  p = p->right;
		  }
	  }
  }

2.5.3后序遍历

后序遍历：先遍历左子树，再依次遍历右子树，根节点。而遍历左子树，又要先遍历左子树，再依次遍历右子树，根节点…直至遍历完整棵树。

递归实现

void Postorder1(BTree*root)
{
    if (root == NULL)
    {
        return;
    }
    PreOrder(root->left);//左子树
    PreOrder(root->right);//右子树
    printf("%d ", root->data);//根节点
}

 非递归实现

void Postorder2(BTree* root)
{
	Stack s;
	InitStack(&s);
	BTree* p = root;// p为遍历指针
	BTree* v = root;// v标记已访问节点
	while (p || !IsEmpty(&s))  // 栈不为空或p不为空时循环
	{
		while(p != NULL)//入栈
		{
			StackPush(&s, p);
			p = p->left;
		}
		p = StackTop(&s);
		if (p->right && p->right != v)//存在右子树，且没有被访问
		{
			p = p->right;//访问
		}
		else//没有右子树或者右子树已被访问
		{
			printf("%d ", p->data);
			v = p;//记录当前访问的节点
			p = NULL;//防止重复访问左子树
			StackPop(&s);// 栈顶元素出栈
		}
	}
}

2.5.4层序遍历

层序遍历，就是一层一层的遍历。

这里我们借助队列来实现。

void leverOrder(BTree* root, Queue* pq)
{
	if (root == NULL)//为空直接返回
	{
		return;
	}
	QueuePush(pq, root);//插入第一个节点
	while (!QueueEmpty(pq))//队列不为空
	{
		BTree* p = QueueFront(pq);
		printf("%d ", p->data);
		QueuePop(pq);
		if (p->left != NULL)//带入左孩子
		{
			QueuePush(pq, p->left);
		}
		if (p->right != NULL)//带入右孩子
		{
			QueuePush(pq, p->right);
		}
	}
}