算法与数据结构(四)：树

前面说的链表、栈、队列都是线性结构，而树是一个非线性节点。

树简介

树是一种非线性结构，由一个根节点和若干个子节点构成，每一个子节点又是一颗子树

从定义上来看树的定义是一个递归的定义，树都有一个根节点，其中当根节点为空时它也是一颗特殊的树，树的示意图如下:

相关术语

• 树的度：树中各节点中最大的子节点数就是树的度，没有子节点的节点称为叶子节点
• 节点的层次：从根节点开始，根节点的子节点为1层，子节点的子节点为第二层，依次类推
• 树的深度：组成树的各节点的最大层数
• 父节点与孩子节点：若一个节点有子节点，那么这个节点称为子节点的父节点，它的子节点称为它的孩子节点
• 兄弟节点：具有相同父节点的节点互称为兄弟节点
• 节点的祖先：从根到该节点所经分支上的所有节点
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙

二叉树

对于树来说，并没有规定它能拥有几个子节点。一般常用的是节点数小于等于2的树，这种树一般称为二叉树。二叉树一般有如下几种形式

• 空二叉树, 根节点为空
• 只有一个节点的二叉树，只有根节点的二叉树
• 只有左子树的二叉树
• 只有右子树的二叉树
• 完全二叉树
• 满二叉树

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。也就是说除了最深层的非叶子节点，每层的子节点都必须有两个子节点，而且最后一层少节点只能最右边少。

满二叉树: 一颗深度为h的二叉树，它的节点如果有2^k - 1 的话，它就是一颗满二叉树。也就说满二叉树是除了叶子节点，每个节点都有两个子节点的树

完全二叉树的性质:

• $$在第k层，最多只有 2^(k -1) 个节点$$
• $$深度为k的完全二叉树，最多有 2^k - 2 个节点$$
• $$具有n个节点的完全二叉树的深度为\lfloorlog_2(n)\rfloor $$

二叉树的创建

从上面的定义来看，树是一个递归的定义，因此在创建它的时候采用的也是递归的方式。树的节点暂时定义为:

typedef struct _BTREE
{
	int nVal;
	struct _BTREE *pLeft;
	struct _BTREE *pRight;
}BTREE, *LPBTREE;

树的节点中有两个节点指针，分别指向左子树和右子树。

LPBTREE CreateBTree()
{
	int n = 0;
	scanf_s("%d", &n);

	if (0 == n)
	{
		return NULL;
	}

  //创建节点本身
	BTREE *t = (BTREE*)malloc(sizeof(BTREE));
	if (NULL == t)
	{
		return NULL;
	}

	memset(t, 0x00, sizeof(BTREE));
	t->nVal = n;
	printf("请输入%d的左子节点:", n);
  //递归调用函数来创建它的左子树
	t->pLeft = CreateBTree();

  //递归调用来创建它的右子树
	printf("请输入%d的右子节点:", n);
	t->pRight = CreateBTree();

	return t;
}

树的遍历

树的遍历一般有三种方式，先序遍历、中序遍历、后序遍历

先序遍历是先遍历根节点，在遍历它的左子树，最后遍历右子树，针对每颗子树都采用这种方式

中序遍历是先遍历左子树，再遍历根节点，最后遍历右子树，针对每颗子树都采取这种方式遍历

后续遍历是先遍历左子树，再遍历右子树，最后遍历根节点，针对每颗子树都采用这种方式遍历

假设现在有一颗二叉树如下所示

采用先序遍历得到的结果是:a、b、d、h、i、e、c、f、j、g、k

采用中序遍历得到的结果是:h、d、i、b、e、a、j、f、c、g、k

采用后续遍历得到的结果是:h、i、d、e、b、j、f、k、g、c、a

根据数的结构我们知道它的先序遍历、中序遍历、后序遍历。同样的根据先序遍历，中序遍历或者根据后序遍历中序遍历可以得到一棵树的结构从而得到它的另一种遍历方式。这里需要注意的是根据先序遍历和后序遍历是不能唯一确定一颗树的

假设现在有一棵二叉树先序遍历为a、b、d、g、h、k、e、i、c、f、j，中序遍历为:g、d、h、k、b、e、i、a、c、f、j 可以推断出它的树结构并得到后续遍历的结果。

1. 根据先序遍历a为第一个元素，可以得知a为根节点，再根据中序遍历中a的位置可以知道，g、d、h、k、b、e、i 为a的左子树，c、f、j为a的右子树。而且b c分别是左子树和右子树的根节点
2. 先来分析a的做子树，在先序遍历中，第一个元素为b，而中序遍历中b的位置可以知道g、d、h、k为左子树而e、i为右子树，而且g e分别是左子树和右子树的根节点

以此类推可以得到a的左子树的布局大致如下:

树的遍历也是一个递归的过程，将每个子节点看做一颗完整的树，再次调用遍历函数。只是根据不同的遍历方式，遍历函数调用的时机不同罢了

//先序遍历
void PreOrder(LPBTREE pRoot)
{
	if (NULL == pRoot)
	{
		return;
	}

  //先遍历根节点
	printf("%d ", pRoot->nVal);
  //遍历左子树
	PreOrder(pRoot->pLeft);
  //遍历右子树
	PreOrder(pRoot->pRight);
}

//中序遍历

void InOrder(LPBTREE pRoot)

{

if (NULL == pRoot)

{

return;

}

InOrder(pRoot->pLeft);
printf("%d ", pRoot->nVal);
InOrder(pRoot->pRight);

}

//后续遍历

void PostOrder(LPBTREE pRoot)

{

if (NULL == pRoot)

{

return;

}

PostOrder(pRoot->pLeft);
PostOrder(pRoot->pRight);
printf("%d ", pRoot->nVal);

}

##其他二叉树

在算法中，二叉树应用的最为广泛，根据不同的用途，又可以分为这么几类

• 二叉 排序 树：所有的左子树的节点都小于根节点，所有右子树的节点都大于根节点，而树的左右子树本身又是一颗二叉排序树；对于二叉排序树来说，中序遍历可以得到一个有序的集合。对于同一组有序的数值，生成的二叉排序树并不是唯一的，一般树的深度越浅，查找效率越高
• 平衡二叉树：平衡二叉树是对二叉排序树的一种改进，平衡二叉树左右子树的高度差不超过1，其平衡因子定义为其左子树与右子树高度的差值，为了保持这个状态，每当插入一个数据时都需要对整个树做大量的调整。