二叉树_C_内存溢出

一、树的概念

1.树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图： A 的为 6 叶节点或终端节点：度为 0 的节点称为叶节点；如上图： B 、 C 、 H 、 I... 等节点为叶节点非终端节点或分支节点：度不为 0 的节点；如上图： D 、 E 、 F 、 G... 等节点为分支节点双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图： A 是 B 的父节点孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图： B 是 A 的孩子节点兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图： B 、 C 是兄弟节点树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为 6 节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；树的高度或深度：树中节点的最大层次；如上图：树的高度为 4 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图： H 、 I 互为兄弟节点节点的祖先：从根到该节点所经分支上的所有节点；如上图： A 是所有节点的祖先子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是 A 的子孙森林：由 m （ m>0 ）棵互不相交的树的集合称为森林；

2.树的表示

//孩子兄弟表示法
typedef int DataType;

struct TreeNode
{
	struct TreeNode* firstChild;//第一个孩子结点
	struct TreeNode* pNextBrother;//指向其下一个兄弟结点
	DataType data;//结点中的数据域
};

二、二叉树概念即结构 1.概念

一棵二叉树是结点的一个有限集合，该集合 : 1. 或者为空 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成特点： 1.二叉树不存在度大于 2 的结点 2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

2.两种特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 K ，且结点总数是 2^k-1，则它就是满二叉树。 2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

3.二叉树的性质

1. 若规定根节点的层数为 1 ，则一棵非空二叉树的第 i 层上最多有2^(i-1)个结点. 2. 若规定根节点的层数为 1 ，则深度为 h 的二叉树的最大结点数是2^h -1. 3. 对任何一棵二叉树 , 如果度为 0 其叶结点个数为n , 度为 2 的分支结点个数为m , 则有 n＝m ＋ 1. 4. 若规定根节点的层数为 1 ，具有 n 个结点的满二叉树的深度，h=㏒₂(n+1). 5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为i 的结点有： 1. 若 i>0 ， i 位置节点的双亲序号： (i-1)/2 ； i=0 ， i 为根节点编号，无双亲节点 2. 若 2i+1 ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子 3. 若 2i+2 ，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子

4.二叉树的存储结构 1. 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

在数组中，有父子间下标计算公式关系式：

1. leftchild = parent*2+1

2. rightchild = parent*2+2

3. parent = (child-1) / 2 (奇数偶数余2结果相同，所以(左右孩子-1) / 2结果都相同)

2. 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；

三、二叉树的顺序结构及实现 1.堆的概念及结构

堆的性质： 1. 堆中某个节点的值总是不大于或不小于其父节点的值； 2. 堆总是一棵完全二叉树。大堆：树中都大于或等于孩子小堆：树中都小于或等于孩子

2.堆的实现 1.堆的代码实现

Heap.h

#pragma once
#include 
#include 
#include 
#include 

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;

//初始化
void HeapInit(HP* php);
//销毁
void HeapDestroy(HP* php);
//打印数据
void HeapPrint(HP* php);
//插入x以后，保持它依旧是(大/小)堆
void HeapPush(HP* php,HPDataType x);
//删除堆顶的数据，(最大\最小)
void HeapPop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//堆大小
size_t HeapSize(HP* php);
//堆顶
HPDataType HeapTop(HP* php);

Heap.c

#include "Heap.h"

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void HeapPrint(HP* php)
{
	assert(php);
	size_t i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d", php->a[i]);
	}
	printf("\n");
}

void SWAP(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void AdjustUp(HPDataType* a,size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])//大堆则将符号改为 >
		{
			SWAP(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php,HPDataType x)
{
	assert(php);
	//小堆
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a ,sizeof(HPDataType)*newCapacity);
		if (tmp == NULL)
		{
			printf("ralloc fail\n");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	//向上调整，控制保持是一个小堆
	AdjustUp(php->a ,php->size -1);

}

void AdjustDown(HPDataType* a, size_t size,size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		//找出左右孩子中最小的那个
		if (child + 1 < size && a[child + 1] > a[child])//child+1是防止右孩子是NULL，访问失败
		{
			child++;
		}

		//如果孩子小于父亲，则交换，并继续往下调整
		if (a[child] < a[parent])//大堆则将符号改为 >
		{
			SWAP(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//小堆
	SWAP(&php->a[php->size - 1], &php->a[0]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

size_t HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

2.堆的调整算法

1.向上调整（如上代码实现中的HeapPush）

代码实现：

void AdjustUp(HPDataType* a,size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			SWAP(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

2. 向下调整（如上代码实现中的HeapPop）

代码实现：

void AdjustDown(HPDataType* a, size_t size,size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		//找出左右孩子中最小的那个
		if (child + 1 < size && a[child + 1] > a[child])//child+1是防止右孩子是NULL，访问失败
		{
			child++;
		}

		//跟父亲比较，如果孩子小于父亲，则交换
		if (a[child] < a[parent])
		{
			SWAP(&a[child], &a[parent]);
            //在从交换的孩子位置继续向下调整
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

3.堆的应用 1.堆排序

堆排序分两步：

1.建堆（升序：建大堆，降序：建小堆）

2.利用堆删除思想来进行排序

例：给数组a对里元素排序，遍历一遍复杂度：O(N²)

void HeapSort(int* a, int size)
{
	HP hp;
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < size; i++)
	{
		HeapPush(&hp, a[i]);//升序
	}

	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}

	HeapDestroy(&hp);
}

时间复杂度：O(N*㏒N) , 空间复杂度：O(N)

优化后(利用堆删除思想)：时间复杂度：O(N*㏒N) , 空间复杂度：O(1)

1.1 建堆 (建堆时间复杂度：O(N))

一、向下调整法建堆

	for (i = (size-1-1)/2; i >= 0; i--)//size-1是最后一个结点的位置
	{
		AdjustDown(a, size, i);
	}
	//parent = ( child - 1 )/2

二、向上调整法建堆

for (i = 1; i < size; i++)
	{
		AdjustUp(a, i);
	}

1.2 利用堆删除思想来进行排序

对上面例题优化后：时间复杂度：O(N*㏒N) , 空间复杂度：O(1)

升序：建大堆，降序：建小堆

void HeapSort(int* a, int size)
{
	int i = 0;
	//向上调整 -- 建堆
	//for (i = 1; i < size; i++)
	//{
	//	AdjustUp(a, i);
	//}

	//向下调整 -- 建堆
	for (i = (size-1-1)/2; i >=0; i--)
	{
		AdjustDown(a, size,i);
	}

	size_t end = size-1;
	while (end > 0)
	{
		SWAP(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		end--;
	}
}

2.TOP-K问题

TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决

思路：用前K个数建立一个K个数的小堆，然后剩下的N-K个依次遍历，如果比堆顶的数据大，就替换它进堆，最后堆里面的K个数就是最大的K个

void PrintTopK(int* a,int size, int k)
{
	//1.建堆 -- 用前a中前k个元素建堆
	int* kminHeap = (int*)malloc(sizeof(int) * k);
	assert(kminHeap);

	int i = 0;
	for (i = 0; i < k; i++)
	{
		kminHeap[i] = a[i];
	}

	//建小堆 
	for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, size, i);
	}

	//2. 将剩余n-k个元素依次与堆顶元素进行交换，满足条件则替换
	for (i = k; i < size; i++)
	{
		if (kminHeap[0] < a[i])
		{
			kminHeap[0] = a[i];
			AdjustDown(kminHeap, k, 0);
		}
	}
}

总结：

用数据集合中前K个元素来建堆

求前 k 个最大的元素，则建小堆求前 k 个最小的元素，则建大堆

四、二叉树链式结构的实现 1.链式二叉树结构说明

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

二叉树是：
1. 空树 2. 非空：根节点，根节点的左子树、根节点的右子树组成的

2.二叉树的遍历

手动创建这样一棵树

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	BTDataType* left;
	BTDataType* right;
}BTNode;

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

BTNode* CreateBinaryTree()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

int main()
{
	BTNode* tree = CreateBinaryTree();

	return 0;
}

2.1 前序遍历(先根遍历)顺序: 根、左子树、右子树

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}

	printf("%d", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

int main()
{
	BTNode* tree = CreateBinaryTree();
	PrevOrder(tree);
	return 0;
}

打印出结果：

2.2 中序遍历(中根遍历)顺序：左子树，根节点，右子树

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

int main()
{
	BTNode* tree = CreateBinaryTree();
	InOrder(tree);
	return 0;
}

打印出结果：

2.3 后序遍历(后根遍历)顺序：左子树，右子树，根节点

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

int main()
{
	BTNode* tree = CreateBinaryTree();
	PostOrder(tree);
	return 0;
}

打印出结果：

2.4 层序遍历

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

void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);

    if (root)
    {
        QueuePush(&q, root);//把地址当元素存进栈
    }

    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        printf("%d ", front->data);
        if (front->left != NULL)
            QueuePush(&q, front->left);

        if (front->right != NULL)
            QueuePush(&q, front->right);
    }

    QueueDestroy(&q);
}

思路：

1.先把根入队列，借助队列，先进先出的性质

2.上一层节点出的时候，带下一层节点进去

总结：

深度优先遍历(DFS)：前序、中序、后序

广度优先遍历(BFS)：层序

3.节点个数及高度 3.1 二叉树节点个数

//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

3.2 二叉树叶子节点个数

//二叉树叶子节点个数
int BinaryLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return BinaryLeafSize(root->left) + BinaryLeafSize(root->right);
}

思想：

1.分治

2.遍历加计数

3.3 二叉树第k层的节点个数

//二叉树第k层节点个数
int BinaryLevelSize(BTNode* root,int k)
{
	assert(k >= 1);//第k层的节点个数，要求k >= 1

	if (root == NULL)
		return 0;
	
	if (k == 1)
		return 1;

	return BinaryLevelSize(root->left, k - 1) + BinaryLevelSize(root->right, k - 1);
    //k可以想成计数的，k--到1时即到了目标层
}

思想：

1.空树，返回0

2.非空，且k == 1，返回1

3.非空，且k>1,转换成左子树k-1层节点个数+右子树k-1层节点个数

3.4 二叉树的高度

//二叉树的高度
int BTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftDepth = BTreeDepth(root->left);
	int rightDepth = BTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

思想：

分治：左子树高度和右子树高度相比较(因为二叉树高度算最大的)，大的那个+1(+1是因为每颗树再分成左右小子树，根节点没算)

3.5 二叉树查找值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1 != NULL)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);
		if (ret2 != NULL)
			return ret2;

		return NULL;
}

4. 二叉树的创建与销毁 1. 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 ('#' 为NULL)

BTNode* BinaryTreeCreate(char* a,int* pi)
{
    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = a[(*pi)++];
    
    root->left = BinaryTreeCreate(a,pi);
    root->right = BinaryTreeCreate(a,pi);
    
    return root;
}

2. 二叉树销毁

void BTreeDestroy(BTNode* root)
{
    if (root == NULL)
        return;

    BTreeDestroy(root->left);
    BTreeDestroy(root->right);
    free(root);
}

3. 判断是否为完全二叉树

bool BTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);

    if (root)
    {
        QueuePush(&q, root);
    }

    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL)//碰到NULL则跳出
            break;

        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }

    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        //如果NULL后面出到非NULL，那么说明不是完全二叉树
        if (front != NULL)
            return false;
    }

    return true;
}