[数据结构与算法]4）数据结构之二叉树

树的基本概念：

树的逻辑结构是非线性的如图

图所示就是一棵树，它是若干结点(A、B、C等都是结点)的集合，是由若干棵互不相交的子树(如B、E、F、K、L这5个结点组成的树就是一棵子树)组成的。其中，每一棵子树又是一棵树，也是由唯一的根结点和若干棵互不相交的子树组成的。由此可知，树的定义是递归的，即在树的定义中又用到了树的定义。要注意的是，树的结点数目可以为0，当为0时，这棵树称为一棵空树，?这是一种特殊情况。

树的一些基本术语

结点:?A、B、C等都是结点，结点不仅包含数据元素，而且包含指向子树的分支。例如，A结点不仅包含数据元素A，而且包含3个指向子树的指针。
结点的度:结点拥有的子树个数或者分支的个数。例如，A结点有3棵子树，所以A结点的度为3.
树的度:树中各结点度的最大值。如例子中结点度最大为3(A、D结点)，最小为0(F、G.1.3.K、L、M结点)，所以树的度为3。

叶子结点:又叫作终端结点，指度为0的结点，如F、G、1、J、K、L、M结点都是叶子结点。
非终端结点:又叫作分支结点，指度不为0的结点，如A、B、C、D、E、H结点都是非终端结点。除了根结点之外的非终端结点，也叫作内部结点，如B、C、D、E、H结点都是内部结点。

孩子:结点的子树的根，如A结点的孩子为B、C、D.? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? 双亲:与孩子的定义对应，如B、C、D结点的双亲都是A.
兄弟:同一个双亲的孩子之间互为兄弟。如B、C、D互为兄弟，因为它们都是A结点的孩子。

祖先:从根到某结点的路径上的所有结点，都是这个结点的祖先。如K的祖先是A、B、E,因为从A到K的路径为A->B->E->K。
子孙:以某结点为根的子树中的所有结点，都是该结点的子孙。如D的子孙为H、I、J、M

层次:从根开始，根为第一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推

树的高度(或者深度):树中结点的最大层次。如图中的树共有4层，所以高度为4.

结点的深度和高度:
????????1)结点的深度是从根结点到该结点路径上的结点个数，
????????2)从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径上结点的个数即为该结点在树中的高度，如结点D的高度为3.就是从D到M的路径上结点个数。

????????3)?根结点的高度为树的高度，如结点A，其高度为4.?是从入到K(L、M)这条路径上结点的个数，也是整棵树的高度。
堂兄弟:双亲在同一层的结点互为堂兄弟。?如G和H互为堂兄弟，因为G的双亲是C.?H的双亲是D.?C和D在同一层上。注意和兄弟的概念的区分。
有序树:树中结点的子树从左到右是有次序的，不能交换，这样的树叫作有序树.

无序树:树中结点的子树没有顺序，可以任意交换，这样的树叫作无序树。
丰满树:丰满树即理想平衡树，要求除最底层外，其他层都是满的。
森林:若干棵互不相交的树的集合。图中如果把根A去掉，剩下的3棵子树互不相交，它们组成一个森林。

树的物理结构

1、顺序存储结构：双亲存储结构

2、链式存储结构：孩子存储结构、孩子兄弟存储结构

?双亲存储结构：

双亲存储结构：用一维数组即可实现，数组的下标表示树中的结点，数组内的数据表示该结点的双亲结点，其中-1表示没有双亲，该结构不适合插入删除数据因此不实用

孩子存储结构：

该结构其实就是图的邻接表存储结构。树其实是一种特殊的图，把图中的多对多关系删减为一对多关系即得到树，因此图的存储结构完全可以用来存储树

孩子兄弟存储结构（重点）

?二叉树的概念：

二叉树：将普通的树加上两个限制条件

? ? ? ? 1、每个结点最多只有两颗子树

? ? ? ? 2、子树有左右顺序之分，不能颠倒

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

完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对? 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

满二叉树：

完全二叉树

?二叉树的物理结构：

? ? ? ? 顺序存储结构：

用一个数组来存储一颗二叉树，这种存储方式最适合于完全二叉树，若存储普通二叉树则会有大量的空间被浪费

?因为用数组存储二叉树只适合完全二叉树，因此对于二叉树的物理结构用链表实现的较多

? ? ? ? 链式存储结构（与树的链式存储结构有所不同）

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

二叉树的顺序存储的实现

提示：因为二叉树用链表实现更加实用，因此顺序存储的实现有兴趣了解一些就可

这里是用双亲存储结构对完全二叉树的实现

在visual studio 2017下建立一个工程，并创建三个文件

?BinaryTree.h中

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#define MAXSIZE 2
typedef int BTreeDataType;
typedef struct BinaryTree
{
	BTreeDataType *_pBT;
	size_t _size;
	size_t _capacity;
}BTree;

void BTreeInit(BTree*pBT);//二叉树的初始化

static void BTreeIsAppend(BTree*pBT);//检测是否需要扩容
void BTreePushBack(BTree*pBT, BTreeDataType data);//尾插

void BTreePrint(BTree*pBT);//打印二叉树

BTreeDataType BTreeFindParent(BTree*pBT, size_t pos);//查找双亲

BTreeDataType BTreeFindLeftChild(BTree*pBT, size_t pos);//寻找左孩子

BTreeDataType BTreeFindRightChild(BTree*pBT, size_t pos);//寻找右孩子

void BTreePopBack(BTree*pBT);//尾删

void BTreeModify(BTree *pBT, size_t pos, BTreeDataType data);//修改某个结点的值

?BinaryTree.c中

#include"BinaryTree.h"

void BTreeInit(BTree*pBT)
{
	pBT->_pBT = (BTreeDataType*)malloc(sizeof(BTreeDataType)*MAXSIZE);
	assert(pBT->_pBT);
	pBT->_size = 0;
	pBT->_capacity = MAXSIZE;
}

static void BTreeIsAppend(BTree*pBT)
{
	if (pBT->_capacity == pBT->_size)
	{
		BTreeDataType *tmp= (BTreeDataType*)realloc(pBT->_pBT,sizeof(BTreeDataType)*(pBT->_capacity)*2);
		assert(tmp);
		pBT->_pBT = tmp;
		pBT->_capacity *= 2;
	}

}

void BTreePushBack(BTree*pBT,BTreeDataType data)
{
	BTreeIsAppend(pBT);
	pBT->_pBT[pBT->_size] = data;
	pBT->_size++;
}

void BTreePrint(BTree*pBT)
{
	assert(pBT->_size);
	for (size_t i = 0; i < pBT->_size; i++)
	{
		printf("%d->", pBT->_pBT[i]);
	}
	printf("\n");
}

BTreeDataType BTreeFindParent(BTree*pBT,size_t pos)
{
	assert(pBT->_size&&pos&&pos<pBT->_size);//二叉树不能为空，Pos为合法数值
	return pBT->_pBT[(pos - 1) / 2];
}

BTreeDataType BTreeFindLeftChild(BTree*pBT, size_t pos)
{
	assert(pBT->_size && pos < pBT->_size&&pos*2+1<pBT->_size);
	return pBT->_pBT[pos * 2 + 1];
}

BTreeDataType BTreeFindRightChild(BTree*pBT, size_t pos)
{
	assert(pBT->_size && pos < pBT->_size && pos * 2 + 2 < pBT->_size);
	return pBT->_pBT[pos * 2 + 2];
}

void BTreePopBack(BTree*pBT)
{
	assert(pBT->_size);
	pBT->_size--;
}

void BTreeModify(BTree *pBT, size_t pos, BTreeDataType data)
{
	assert(pBT->_size&&pos<pBT->_size&&pBT>=0);
	pBT->_pBT[pos] = data;
}

Test.c中

#include"BinaryTree.h"

void Test()
{
	BTree T;
	BTreeInit(&T);
	BTreePushBack(&T, 1);
	BTreePushBack(&T, 2);
	BTreePushBack(&T, 3);
	BTreePushBack(&T, 4);
	BTreePushBack(&T, 5);
	BTreePushBack(&T, 6);
	BTreePushBack(&T, 7);
	BTreePushBack(&T, 8);

	BTreePrint(&T);

	printf("%d\n", BTreeFindParent(&T, 2));
	printf("%d\n", BTreeFindLeftChild(&T, 2));
	printf("%d\n",BTreeFindRightChild(&T, 2));

	BTreePopBack(&T);

	BTreeModify(&T, 2, 9);
	BTreePrint(&T);
}
int main()
{
	Test();
	return 0;
}

运行结果

?二叉树的链式存储的实现（重点）

开盘菜：

????????二叉树的遍历
??????? 二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，?每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一?个线性队列上，进而便于遍历。
??????? 由二叉树的递归定义可知，遍历一棵二又树便要决定对根结点N、左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序(NLR)、?中序(LNR)和后序(LRN)三种遍历算法，其中“序”指的是根结点在何时被访问。
1.先序遍历
????????先序遍历(PreOrder)的操作过程如下。
????????若二叉树为空，则什么也不做:否则，
????????1)访问根结点:
????????2)先序遍历左子树:
????????3)先序遍历右子树。
2，中序遍历
????????中序遍历(mnOrder)的操作过程如下，
????????指二义树为空，则什么也不做否则，
????????1)中序遍历左子树1
????????2)访间根结点:
????????3)中序遍历右子树。
3.后序遍历
????????后序遍历(PostOrder)?的操作过程如下。
????????若二又树为空，则什么也不做:否则，
????????1)后序遍历左子树:
????????2)后序遍历右子树:
????????3)访问根结点。

4.层序遍历

?????????设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

难点：二叉树的层次遍历是个难点，层次遍历需借助队列的实现，利用队列的先进先出的特性将二叉树进行层次遍历

见图：

?二叉树的实现在层次遍历以及判断是否为完全二叉树的函数实现上较为困难，请耐心理解

?

?其中Queue.h与Queue.c为队列的实现

BinaryTree.hZ中：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"Queue.h"
typedef char BinaryTreeDataType;
typedef struct BinaryTree//用左右孩子指针建立二叉树的结构
{
	BinaryTreeDataType _data;//数据域
	struct BinaryTree *_leftchild;//左指针域
	struct BinaryTree *_rightchild;//右指针域
}BTree;

BTree* BinaryTreeNodeCreat(BinaryTreeDataType data);//新建结点
//打印结点
void BinaryTreePrint(BTree* Node);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTree* Proot);
// 二叉树中序遍历
void BinaryTreeInOrder(BTree* Proot);
// 二叉树后序遍历
void BinaryTreePostOrder(BTree* Proot);

// 二叉树节点个数
int BinaryTreeSize(BTree* Proot);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTree* Proot);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTree* Proot, int k);
// 二叉树查找值为x的节点
BTree* BinaryTreeFind(BTree* Proot, BinaryTreeDataType x);

// 层序遍历
void BinaryTreeLevelOrder(BTree* Proot);

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTree* Proot);
// 二叉树销毁
void BinaryTreeDestory(BTree** PProot);

?BinaryTree.c中

建议：涉及队列的层次遍历可以先看队列的实现

#include"BinaryTree.h"


BTree* BinaryTreeNodeCreat(BinaryTreeDataType data)
{
	BTree*Node=(BTree*)malloc(sizeof(BTree));
	Node->_data = data;
	Node->_leftchild = NULL;
	Node->_rightchild = NULL;
	return Node;
}
void BinaryTreePrint(BTree* Node)
{
	if (Node == NULL)
		printf("%d\n", -1);
	else
	{
		printf("%c\n", Node->_data);

	}
}
// 二叉树前序遍历
void BinaryTreePrevOrder(BTree* Proot)
{
	if (Proot == NULL)
	{
		printf("NULL ");
		return;
	}
		
	printf("%c ", Proot->_data);
	BinaryTreePrevOrder(Proot->_leftchild);
	BinaryTreePrevOrder(Proot->_rightchild);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTree* Proot)
{
	if (Proot == NULL)
	{
		printf("NULL ");
		return;
	}

	BinaryTreePrevOrder(Proot->_leftchild);
	printf("%c ", Proot->_data);
	BinaryTreePrevOrder(Proot->_rightchild);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTree* Proot)
{
	if (Proot == NULL)
	{
		printf("NULL ");
		return;
	}

	BinaryTreePrevOrder(Proot->_leftchild);
	BinaryTreePrevOrder(Proot->_rightchild);
	printf("%c ", Proot->_data);
}

// 二叉树节点个数
int BinaryTreeSize(BTree* Proot)
{
	return Proot == NULL ? 0 : (BinaryTreeSize(Proot->_leftchild)+BinaryTreeSize(Proot->_rightchild )+1);
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTree* Proot)
{
	if (Proot == NULL)
	{
		return 0;
	}

	if (Proot->_leftchild == NULL && Proot->_rightchild == NULL)
		return 1;

	return BinaryTreeLeafSize(Proot->_leftchild)+ BinaryTreeLeafSize(Proot->_rightchild);
	
	
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTree* Proot, int k)
{
	if (Proot == NULL)
		return 0;
	if (1 == k)
		return 1;
	return BinaryTreeLevelKSize(Proot->_leftchild, k - 1) 
		 + BinaryTreeLevelKSize(Proot->_rightchild, k - 1);
}


// 二叉树查找值为x的节点
BTree* BinaryTreeFind(BTree* Proot, BinaryTreeDataType x)
{
	if (Proot == NULL)
		return NULL;
	if (Proot->_data == x)
		return Proot;
	BTree* LeftTmp=BinaryTreeFind(Proot->_leftchild, x);
	if (LeftTmp)
		return LeftTmp;
	BTree* RightTmp=BinaryTreeFind(Proot->_rightchild, x);
	if (RightTmp)
		return RightTmp;
	if (LeftTmp == NULL && RightTmp == NULL)
	{
		return NULL;
	}
}

// 层序遍历
void BinaryTreeLevelOrder(BTree* Proot)
{
	if (Proot == NULL)
	{
		printf("NULL ");
		return;
	}
	Queue Q;
	QueueInit(&Q);
	QueuePush(&Q, Proot);
	while (!QueueEmpty(&Q))
	{
		QDataType front = QueueFront(&Q);
		if (front==NULL)
			printf("NULL ");
		else
		{
			printf("%c ", front->_data);
			QueuePush(&Q, front->_leftchild);
			QueuePush(&Q, front->_rightchild);
		}
		QueuePop(&Q);	
	}
	QueueDestroy(&Q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTree* Proot)
{
	if (Proot == NULL)
	{
		return false;
	}
	Queue Q;
	QueueInit(&Q);
	QueuePush(&Q, Proot);
	while (!QueueEmpty(&Q))
	{
		QDataType front = QueueFront(&Q);
		QueuePop(&Q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&Q, front->_leftchild);
		QueuePush(&Q, front->_rightchild);
	}
	while (!QueueEmpty(&Q))
	{
		QDataType front = QueueFront(&Q);
		QueuePop(&Q);
		if (front != NULL)
			return false;
	}
	return true;
}
// 二叉树销毁
void BinaryTreeDestory(BTree** PProot)
{
	if (*PProot == NULL)
		return;
	
	BinaryTreeDestory(&((*PProot)->_leftchild));
	BinaryTreeDestory(&((*PProot)->_rightchild));
	free(*PProot);
	*PProot = NULL;
}

?Test.c中

#include"BinaryTree.h"

void Test()
{
	BTree*A = BinaryTreeNodeCreat('A');
	BTree*B = BinaryTreeNodeCreat('B');
	BTree*C = BinaryTreeNodeCreat('C');
	BTree*D = BinaryTreeNodeCreat('D');
	BTree*E = BinaryTreeNodeCreat('E');
	BTree*F = BinaryTreeNodeCreat('F');
	BTree*H = BinaryTreeNodeCreat('H');
	BTree*J = BinaryTreeNodeCreat('J');
	BTree*K = BinaryTreeNodeCreat('K');

	A->_leftchild = B;
	A->_rightchild = C;
	B->_leftchild = D;
	D->_rightchild = E;
	E->_leftchild = F;
	C->_leftchild = H;
	C->_rightchild = J;
	H->_leftchild = K;

	BinaryTreePrint(A);

	
	BinaryTreePrevOrder(A);//前序遍历
	printf("前序遍历\n");
	BinaryTreeInOrder(A);//中序遍历
	printf("中序遍历\n");
	BinaryTreePostOrder(A);//后序遍历
	printf("后序遍历\n");
	printf("\n");

	printf("一共有%d个节点\n", BinaryTreeSize(A));
	printf("一共有%d个叶子节点\n", BinaryTreeLeafSize(A));
	int k = 1;
	while (k<6)
	{
		printf("第%d层一共有%d个节点\n", k, BinaryTreeLevelKSize(A, k));
		k++;
	}
	
	printf("查找值为H的节点：");
	BinaryTreePrint(BinaryTreeFind(A, 'H'));
	printf("查找值为U的节点：");
	BinaryTreePrint(BinaryTreeFind(A, 'U'));
	
	BinaryTreeLevelOrder(A);//层次遍历
	printf("层次遍历\n");

	printf("判断是否为完全二叉树: %d", BinaryTreeComplete(A));

	BinaryTreeDestory(&A);
	
}

int main()
{
	Test();
	return 0;
}

Queue.h中?

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>	
#include<stdbool.h>


//前置声明,声明外部的自定义类型不需要extern
struct BinaryTree;
typedef struct BinaryTree* QDataType;

//typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode*next;
	QDataType data;
}QueueNode;

typedef struct Queue
{
	QueueNode*head;
	QueueNode*tail;
}Queue;

void QueueInit(Queue*pq);
void QueueDestroy(Queue*pq);

void QueuePush(Queue*pq, QDataType X);
void QueuePop(Queue*pq);
QDataType QueueFront(Queue*pq);
QDataType QueueBack(Queue*pq);
bool QueueEmpty(Queue*pq);
int QueueSize(Queue*pq);

?Queue.c中

#include"Queue.h"

void QueueInit(Queue*pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestroy(Queue*pq)
{
	assert(pq);
	QueueNode*cur = pq->head;
	while (cur)
	{
		QueueNode*next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue*pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

}
void QueuePop(Queue*pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode*next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}



}
QDataType QueueFront(Queue*pq)//访问队头的数据
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;

}
QDataType QueueBack(Queue*pq)//访问队尾的数据
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;

}
bool QueueEmpty(Queue*pq)
{
	assert(pq);
	return pq->head == NULL;
}
int QueueSize(Queue*pq)
{
	assert(pq);
	int size = 0;
	QueueNode*cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

?

?