二叉树

树是一种非线性的数据结构, 它是由n个有限结点组成一个具有层次关系的集合.

每个结点有0个或多个子节点

没有父节点的节点称为根节点

每一个非根节点有且只有一个父节点

子树是不相交的

一棵n个节点的树有n-1条边

树的表示

// 孩子兄弟表示法

typedef int DataType;
struct Node{
	struct Node* _firstChild;		// 第一个孩子节点
	struct Node* _pNextBrother;		// 指向其下一个兄弟节点
	DataType _data;					// 节点的数据
};

二叉树

二叉树是节点的一个有限集合, 该集合或者为空, 或者有一个根节点加上两棵别称为左子树和右子树的二叉树组成

每个节点最多有两棵子树, 即二叉树不存在度大于2的节点

二叉树的子树有左右之分, 子树的次序不能颠倒

特殊的二叉树

  • 满二叉树: 一个二叉树, 如果每一层的节点数都达到最大值, 则这个二叉树就是满二叉树. 也就是, 如果一个二叉树的层数为k, 且节点总数是(2^k)-1, 则它就是满二叉树
  • 完全二叉树: 对于深度为k, 有n个节点的二叉树, 当且仅当其每一个节点都与深度为k的满二叉树编号从1至n的节点一一对应时称为完全二叉树. 满二叉树就是一种特殊的完全二叉树

二叉树的存储结构

顺序存储

顺序结构存储就是使用数组来存储, 一般使用数组只适合表示完全二叉树, 因为不是完全二叉树会有空间的浪费

二叉树顺序存储在物理上是一个数组, 在逻辑上是一棵二叉树

链式存储

用链表来表示一棵二叉树, 即用链来指示元素之间的逻辑关系

二叉树顺序结构及实现

堆通常是一个可以被看做一棵完全二叉树的数组对象

堆中某个节点的值总是不大于或不小于其父节点的值

堆总是一棵完全二叉树

堆的实现

// Heap.h

#pragma once
typedef int HPDataType;
typedef int(*PCOM)(HPDataType, HPDataType);
int Less(HPDataType left, HPDataType right);
int Greater(HPDataType left, HPDataType right);

typedef struct Heap {
	HPDataType* _array;
	int _capacity;
	int _size;
	PCOM Compare;
}Heap;

void InitHeap(Heap* hp, HPDataType* array, int size, PCOM compare);
void InitEmptyHeap(Heap* hp, int capacity, PCOM compare);
void InsertHeap(Heap* hp, HPDataType data);
void EraseHeap(Heap* hp);
int HeapSize(Heap* hp);
int HeapEmpty(Heap* hp);
HPDataType HeapTop(Heap* hp);
void DestoryHeap(Heap* hp);
void HeapSort(int* array, int size);
// Heap.c

#include "Heap.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void Swap(HPDataType* pLeft, HPDataType* pRight) {
	HPDataType temp = *pLeft;
	*pLeft = *pRight;
	*pRight = temp;
}

void AdjustDown(HPDataType* array, int size, int parent, PCOM Compare) {
	int child = parent * 2 + 1;
	while (child < size) {
		if (child + 1 < size && Compare(array[child + 1], array[child])) {
			child += 1;
		}
		if (Compare(array[child], array[parent])) {
			Swap(&array[child], &array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			return;
		}
	}
}

void AdjustUp(HPDataType* array, int size, int child, PCOM Compare) {
	int parent = (child - 1) / 2;
	while (child) {
		if (Compare(array[child], array[parent])) {
			Swap(&array[child], &array[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			return;
		}
	}
}

void CheckCapacity(Heap* hp) {
	assert(hp);
	if (hp->_size == hp->_capacity) {
		int newCapacity = hp->_capacity * 2;
		HPDataType* pTemp = (HPDataType*)malloc(sizeof(HPDataType) * newCapacity);
		if (pTemp == NULL) {
			assert(0);
			return;
		}
		for (int i = 0; i < hp->_size; ++i) {
			pTemp[i] = hp->_array[i];
		}
		free(hp->_array);
		hp->_array = pTemp;
		hp->_capacity = newCapacity;
	}
}

int Less(HPDataType left, HPDataType right) {
	return left < right;
}

int Greater(HPDataType left, HPDataType right) {
	return left > right;
}

void InitHeap(Heap* hp, HPDataType* array, int size, PCOM compare) {
	assert(hp);
	hp->_array = (HPDataType*)malloc(sizeof(HPDataType) * size);
	if (hp->_array == NULL) {
		assert(0);
		return;
	}
	hp->_capacity = size;
	for (int i = 0; i < size; ++i) {
		hp->_array[i] = array[i];
	}
	hp->_size = size;
	hp->Compare = compare;
	int root = ((size - 2) >> 1);
	for (; root >= 0; --root) {
		AdjustDown(hp->_array, size, root, hp->Compare);
	}
}

void InitEmptyHeap(Heap* hp, int capacity, PCOM compare) {
	assert(0);
	hp->_array = (HPDataType*)malloc(sizeof(HPDataType) * capacity);
	if (hp->_array == NULL) {
		assert(0);
		return;
	}
	hp->_capacity = capacity;
	hp->_size = 0;
	hp->Compare = compare;
}

void InsertHeap(Heap* hp, HPDataType data) {
	CheckCapacity(hp);
	hp->_array[hp->_size] = data;
	hp->_size++;
	AdjustDown(hp->_array, hp->_size, hp->_size - 1, hp->Compare);

}

void EraseHeap(Heap* hp) {
	if (HeapEmpty(hp)) {
		return;
	}
	Swap(&hp->_array[0], &hp->_array[hp->_size - 1]);
	hp->_size -= 1;
	AdjustDown(hp->_array, hp->_size, 0, hp->Compare);
}

int HeapSize(Heap* hp) {
	assert(hp);
	return hp->_size;
}

int HeapEmpty(Heap* hp) {
	assert(0);
	return hp->_size == 0;
}

HPDataType HeapTop(Heap* hp) {
	assert(hp);
	return hp->_array[0];
}

void DestoryHeap(Heap* hp) {
	assert(hp);
	if (hp->_array) {
		free(hp->_array);
		hp->_capacity = 0;
		hp->_size = 0;
	}
}

void HeapAdjust(int* array, int size, int parent) {
	int child = parent * 2 + 1;
	while (child < size) {
		if (child + 1 < size && array[child + 1] > array[child]) {
			child += 1;
		}
		if (array[child] > array[parent]) {
			Swap(&array[child], &array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			return;
		}
	}
}

void HeapSort(int* array, int size) {
	int root = ((size - 2) >> 1);
	for (; root >= 0; --root) {
		HeapAdjust(array, size, root);
		int end = size - 1;
		while (end) {
			Swap(&array[0], &array[end]);
			HeapAdjust(array, end, 0);
			end--;
		}
	}
}

二叉树链式结构及实现

二叉树链式结构的遍历

  • 前序遍历: 访问根节点的操作发生在遍历其左右子树之前

    根--->根的左子树--->根的右子树

  • 中序遍历: 访问根节点的操作发生在其左右子树之中

    根的左子树--->根--->根的右子树

  • 后序遍历: 访问根节点的操作发生在遍历其左右子树之后

    根的左子树--->根的右子树--->根

  • 层序遍历: 设根节点所在层数为1, 层序遍历就是从所在二叉树的根节点出发, 首先访问第一层的树根节点, 然后从左到右访问第二层上的节点, 接着是第三层的节点, 以此类推. 自上而下, 从左到右逐层访问树的节点
// 二叉树的实现
// BinTree.h

#pragma once
// 孩子表示法
typedef char BTDataType;
typedef struct BTNode {
	struct BTNode* _pLeft;
	struct BTNode* _pRight;
	BTDataType _data;
}BTNode;
// 二叉树的创建
BTNode* CreateBinTree(BTDataType* array, int size, BTDataType invalid);


void PreOrder(BTNode* pRoot);
void InOrder(BTNode* pRoot);
void PostOrder(BTNode* pRoot);
void LevelOrder(BTNode* pRoot);
int GetBinTreeSize(BTNode* pRoot);
int GetKLevelNodeCount(BTNode* pRoot, int k);
int GetLeafCount(BTNode* pRoot);
BTNode* BinaryTreeFind(BTNode* pRoot, BTDataType x);
void MirrorNor(BTNode* pRoot);
void Mirror(BTNode* pRoot);
void DestoryBinTree(BTNode** pRoot);
// BinTree.c

#include "BinTree.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "Queue.h"

BTNode* BuyBinTreeNode(BTDataType data) {
	BTNode* pNewNode = (BTNode*)malloc(sizeof(BTNode));
	if (NULL == pNewNode) {
		assert(0);
		return NULL;
	}
	pNewNode->_data = data;
	pNewNode->_pLeft = NULL;
	pNewNode->_pRight = NULL;
	return pNewNode;
}

BTNode* _CreateBinTree(BTDataType* array, int size, int* index, BTDataType invalid) {
	BTNode* pRoot = NULL;
	if (*index < size && invalid != array[*index]) {
		// 根节点
		pRoot = BuyBinTreeNode(array[*index]);
		// 根的左子树
		++(*index);
		pRoot->_pLeft = _CreateBinTree(array, size, index, invalid);
		// 根的右子树
		++(*index);
		pRoot->_pRight = _CreateBinTree(array, size, index, invalid);
	}
	return pRoot;
}

void PreOrder(BTNode* pRoot) {
	if (pRoot) {
		printf("%c ", pRoot->_data);
		PreOrder(pRoot->_pLeft);
		PreOrder(pRoot->_pRight);
	}
}

void InOrder(BTNode* pRoot) {
	if (pRoot) {
		InOrder(pRoot->_pLeft);
		printf("%c ", pRoot->_data);
		InOrder(pRoot->_pRight);
	}
}

void PostOrder(BTNode* pRoot) {
	if (pRoot) {
		PostOrder(pRoot->_pLeft);
		PostOrder(pRoot->_pRight);
		printf("%c ", pRoot->_data);
	}
}

void LevelOrder(BTNode* pRoot) {
	Queue q;
	if (NULL == pRoot) {
		return;
	}
	QueueInit(&q);
	QueuePush(&q, pRoot);
	while (!QueueEmpty(&q)) {
		BTNode* pCur = QueueFront(&q);
		printf("%c ", pCur->_data);
		if (pCur->_pLeft) {
			QueuePush(&q, pCur->_pLeft);
		}

		if (pCur->_pRight) {
			QueuePush(&q, pCur->_pRight);
		}
		QueuePop(&q);
	}
	QueueDestory(&q);
	printf("\n");
}

int GetBinTreeSize(BTNode* pRoot) {
	if (NULL == pRoot) {
		return 0;
	}
	return GetBinTreeSize(pRoot->_pLeft) + GetBinTreeSize(pRoot->_pRight) + 1;
}

void Swap(BTNode** pLeft, BTNode** pRight) {
	BTNode* pTemp = *pLeft;
	*pLeft = *pRight;
	*pRight = pTemp;
}

void MirrorNor(BTNode* pRoot) {
	Queue q;
	if (NULL == pRoot) {
		return;
	}
	QueueInit(&q);
	QueuePush(&q, pRoot);
	while (!QueueEmpty(&q)) {
		BTNode* pCur = QueueFront(&q);
		Swap(&pCur->_pLeft, &pCur->_pRight);
		if (pCur->_pLeft) {
			QueuePush(&q, pCur->_pLeft);
		}
		if (pCur->_pRight) {
			QueuePush(&q, pCur->_pRight);
		}
		QueuePop(&q);
	}
	QueueDestory(&q);
}

void Mirror(BTNode* pRoot) {
	if (pRoot) {
		Swap(&pRoot->_pLeft, &pRoot->_pRight);
		Mirror(pRoot->_pLeft);
		Mirror(pRoot->_pRight);
	}
}

BTNode* CreateBinTree(BTDataType* array, int size, BTDataType invalid) {
	int index = 0;
	return _CreateBinTree(array, size, &index, invalid);
}

int GetLeafCount(BTNode* pRoot) {
	if (NULL == pRoot) {
		return 0;
	}
	if (NULL == pRoot->_pLeft && NULL == pRoot->_pRight) {
		return 1;
	}
	return GetLeafCount(pRoot->_pLeft) + GetLeafCount(pRoot->_pRight);
}

int GetKLevelNodeCount(BTNode* pRoot, int k) {
	if (NULL == pRoot) {
		return 0;
	}
	if (NULL == pRoot->_pLeft && NULL == pRoot->_pRight) {
		return 1;
	}
	return GetKLevelNodeCount(pRoot->_pLeft, k - 1) + GetKLevelNodeCount(pRoot->_pRight, k - 1);
}

BTNode* BinaryTreeFind(BTNode* pRoot, BTDataType x) {
	BTNode* pRet = NULL;
	if (NULL == pRoot) {
		return NULL;
	}
	if (x == pRoot->_data) {
		return pRoot;
	}
	if (pRet = BinaryTreeFind(pRoot->_pLeft, x)) {
		return pRet;
	}
	return BinaryTreeFind(pRoot->_pRight, x);
}

void DestoryBinTree(BTNode** pRoot) {
	assert(pRoot);
	if (*pRoot) {
		DestoryBinTree(&(*pRoot)->_pLeft);
		DestoryBinTree(&(*pRoot)->_pRight);
		free(*pRoot);
		*pRoot = NULL;
	}
}

 


我们的征途是星辰大海!