[数据结构与算法] 数据结构初阶 —

//孩子兄弟表示法
typedef int DataType;
typedef struct Node
{
	DataType data;
	struct Node* firstChild; //指向第一个孩子
	struct Node* nextBrother; //指向其下一个兄弟节点
}Node;

二，二叉树

由一个根节点，加上两颗左二叉树和右二叉树组成，可以为空；
二叉树度不大于2；
二叉树子树有左右之分，次序不可颠倒，因此二叉树是有序树；

特殊二叉树

满二叉树，若每层节点数都达到最大值，如有k层，则节点总数为 $2^{k}-1$ ；
完全二叉树，如有k层，k-1层为满，最后一层从左到右为连续的二叉树；完全二叉树是效率很高的数据结构，是由满二叉树引出来的，满二叉树是特殊的完全二叉树；

二叉树的性质

若根节点为1层，则一颗非空二叉树第k层上最多 $2^{k-1}$ 个节点；
若根节点为1层，则深度为h的二叉树最多 $2^{h}$ ?- 1个节点；
若根节点为1层，则具有n个节点的满二叉树，其深度为；
任何一个二叉树，叶节点个数比度为2的节点数多1个；
对于具有n个节点的二叉树，如按从上到下、从左到右的数组顺序对所有节点从0编号，则对序号为i的节点，如下：

二叉树的存储结构?

?一般可使用两种结构存储，顺序结构或链式结构；

顺序存储

顺序存储即为数组存储，一般只适用表示完全二叉树，不完全二叉树会有空间浪费；
实际使用中，只有堆(一种二叉树)才会使用数组来存储；
物理上为数组，逻辑上是一颗二叉树；

注：这里的堆和虚拟进制地址空间中的堆是两回事，一个是数据结构，一个是管理内存的一块区域分段；

?链式存储

用链表来表示元素的逻辑关系，通常链表中每个节点有三个域组成（数据域、左右指针域）；
链式结构可分为二叉链和三叉链；

//二叉链
typedef int BTDataType;
struct BinaryTreeNode
{
	struct BinaryTreeNode* _pLeft; //指向左孩子节点
	struct BinaryTreeNode* _pReft; //指向右孩子节点
	BTDataType _data; //值域
}BinaryTreeNode;

//三叉链
typedef int BTDataType;
struct BinaryTreeNode
{
    struct BinaryTreeNode* _pParent; //指向父节点
	struct BinaryTreeNode* _pLeft; //指向左孩子节点
	struct BinaryTreeNode* _pReft; //指向右孩子节点
	BTDataType _data; //值域
}BinaryTreeNode;

三，堆

堆的概念

如有个关键码的集合K={ $k_{0}$ ， $k_{1}$ ， $k_{2}$ ，...， $k_{n-1}$ }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足? $k_{i}$ <= $k_{2*i+1}$ ?且? $k_{i}$ <= $k_{2*i+2}$ ?( $k_{i}$ >= $k_{2*i+1}$ 且? $k_{i}$ >= $k_{2*i+2}$ )，i=0、1、...，则称为小堆(大堆)；

小堆

$k_{i}$ <= $k_{2*i+1}$ ?且? $k_{i}$ <= $k_{2*i+2}$ ?，即所有节点小于等于孩子；
根节点最小，叫做最小堆或小根堆；

大堆

$k_{i}$ >= $k_{2*i+1}$ 且? $k_{i}$ >= $k_{2*i+2}$ ?，即所有节点大于等于孩子；
根节点最大，叫做最大堆或大根堆；

堆的性质

堆中某个节点的值，总是不大于或不小于其父节点的值；
根一定是最值（最大值或最小值）；
堆总是一颗完全二叉树，适合顺序结构存储；

向下调整法（数组）

将数组看做为一颗完全二叉树，可使用向下调整法创建堆；
前提条件为，此二叉树的左右子树需是一个堆，只有根节点不满足堆要求；
从根开始，与左右子节点中的最小值，比较并交换，依次类推，直到比父亲大或到叶子节点终止；
时间复杂度，O(logN)；
注，向上调整法类似；

int array[] = {27,15,19,18,28,34,65,49,25,37};

//向下调整法，小堆
void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustDown(int* arr, int n, int parent)
{
	int i = 0;
	int child = 2 * parent + 1;

	//无孩子节点或父亲小于孩子，即终止
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] < arr[child])
			child++;
		
		if (arr[parent] > arr[child])
		{
			Swap(arr + parent, arr + child);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}

//向上调整法
void AdjustUp(int* arr, int child)
{
	int parent = (child - 1) / 2;

	//大堆
	//根节点或父亲大于孩子，即终止
	while (child > 0)
	{
		if (arr[parent] < arr[child])
		{
			Swap(arr + parent, arr + child);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

堆的创建（建堆）

?即对数据如数组（可看为完全二叉树），将其构建为堆；
方法为，从倒数第一个非叶子节点的子树开始调整，直到根节点为止；
即每次调整时，使用向下调整法；
建堆时间复杂度，O(N)，下面有证明；

int arr[] = {1,5,3,8,7,6};

//建堆-向下调整法
void Heap(int* arr, int n)
{
	int i = (n - 1 - 1) / 2; //最后节点的父节点
	for (i; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
}

//建堆-向上调整法
void Heap(int* arr, int n)
{
	int i = 1; 
	for (i; i < n; i++)
	{
		AdjustUp(arr, i);
	}
}

建堆时间复杂度

堆排序??

升序，建大堆（将最大的数换到最后，在将剩下的数向下调整下，选出次大数，依次类推）；
降序，建小堆（将最小的数换到最后，在将剩下的数向下调整下，选出次小数，依次类推）；
整体的时间复杂度，O(N*logN)；
如升序建小堆(或降序建大堆)的话，选出最值后，需在继续建堆(O(N))，效率较低，还不如直接遍历，建堆的价值未体现；

//建堆排序
void HeapSort(int* arr, int n)
{
	//建堆 - O(N)
	int i = (n - 1 - 1) / 2; //最后节点的父节点
	for (i; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

	//排序 - O(N*log(N))
	int end = n - 1;
	while (end)
	{
		Swap(arr, arr + end);
		AdjustDown(arr, end, 0);
		end--;
	}
}

堆的实现?

//堆
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* data;
	int size;
	int capacity;
}Heap;

//初始化
void HeapInit(Heap* php, HPDataType* arr, int n);

//释放销毁
void HeapDestroy(Heap* php);

//插入数据并保持堆
void HeapPush(Heap* php, HPDataType* x);

//删除堆顶数据并保持堆
void HeapPop(Heap* php);

//返回堆顶数据
HPDataType HeapTOP(Heap* php);

//返回堆节点个数
int HeapSize(Heap* php);

//判断释放为空
bool HeapEmpty(Heap* php);

注：完整接口实现代码路径https://gitee.com/napoleoncode/start-code/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/06_Heap

TOP-K问题

直接排序，O(N*log(N))；
建个N个数的堆，并取出前K个数，O(N+K*log(N))；
建个K个数的小堆，然后将剩下的数依次与堆顶比较，大即入堆，最后此堆即为最大的K个数，O(N*log(K))；(如N非常大内存不够，前两种方法即适用了)；
注，通常K远小于N；

//TOP-K
void TOPK(int* arr, int n, int k)
{
	Heap hp;
	//建堆
	HeapInit(&hp, arr, k);

	int i = k;
	for (i; i < n; i++)
	{
		//替换
		if (HeapTop(&hp) > arr[i])
		{
			HeapPop(&hp);
			HeapPush(&hp, arr[i]);
		}
	}

	HeapPrint(&hp);
	HeapDestroy(&hp);
}

四，二叉树链式结构

普通二叉树的增删查改，意义不大；
普通二叉树+搜索树规则，增删查改才有价值；

//二叉树链式结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

//创建节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("BuyNode");
		exit(-1);
	}
	node->_data = x;
	node->_left = node->_right = NULL;
	return node;
}

//自定义二叉树
BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	nodeA->_left = nodeB;
	nodeA->_right = nodeC;
	nodeB->_left = nodeD;
	nodeC->_left = nodeE;
	nodeC->_right = nodeF;
	return nodeA;
}

二叉树的遍历（四种）

前序遍历，根? $\rightarrow$ ?左子树? $\rightarrow$ ?右子树；
中序遍历，左子树? $\rightarrow$ ?根? $\rightarrow$ ?右子树；
后序遍历，左子树? $\rightarrow$ ?右子树? $\rightarrow$ ?根；
层序遍历，一层一层遍历；

注：深度优先遍历（前序、中序、后序），广度优先遍历（层序）；

1，前序遍历

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
		return;
	printf("%c ", root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}

2，中序遍历

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
		return;
	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}

3，后序遍历

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
		return;
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%c ", root->_data);
}

4，层序遍历

//层序遍历-利用队列
//一个节点出列，入列其子节点
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
    QueueNode* phead;
    QueueNode* ptail;   
}

void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if(root)
        QueuePush(&q, root);
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%c ", front->val);
        if(front->left)
            QueuePush(&q, front->left);
        if(front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");
    QueueDestroy(&q);
}

二叉树接口

//求二叉树节点个数-递归
//方法一，全局变量或static
int size = 0; 
void BinaryTreeSize(BTNode* root)
{
	if (root)
		size++;
	else
		return;
	BinaryTreeSize(root->_left);
	BinaryTreeSize(root->_right);
}

//方法二，局部变量-传址
void BinaryTreeSize(BTNode* root, int* psize)
{
	if (root)
		(*psize)++;
	else
		return;
	BinaryTreeSize(root->_left, psize);
	BinaryTreeSize(root->_right, psize);
}

//方法三，返回值
int BinaryTreeSize(BTNode* root)
{
	if (root)
		return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
	else
		return 0;
}

//求二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->_left == NULL && root->_right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

//求二叉树第k层节点个数
//当前树第K层节点个数 = 其左子树的第K-1层节点个数 + 其右子树的第K-1层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

//求二叉树深度
//当前树深度 = max(左子树深度， 右子树深度) + 1；
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BinaryTreeDepth(root->_left);
	int rightDepth = BinaryTreeDepth(root->_right);
	return leftDepth > rightDepth ? (1 + leftDepth) : (1 + rightDepth);
}

//二叉树查找值为x的节点
//先当前节点查找，没有，在去左子树查找，没有，在取右子树查找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;

	BTNode* retLeft = BinaryTreeFind(root->_left, x);
	if (retLeft)
		return retLeft;

	BTNode* retRight = BinaryTreeFind(root->_right, x);
	if (retRight)
		return retRight;

	return NULL;
}

//二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{
    if(root==NULL)
        return;
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
    free(root);
}

//判断二叉树是否是完全二叉树
//利用层序，空也入列，完全二叉树非空是连续的
bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if(root)
        QueuePush(&q, root);
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if(front == NULL)
            break;
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if(front)
        {
            QueueDestroy(&q);
            return false; 
        }
    }
    QueueDestroy(&q);
    return true;
}