数据结构——二叉树(顺序结构与链式结构)

最近在学习数据结构,我真的是长了知识,因为以前的数据结构就没学懂过,现在终于打开了知识的大门,在学的过程中每一个知识都是新奇玩意儿,直呼好家伙!话不多说,直接上内容。
数据结构——二叉树(顺序结构与链式结构)

1.二叉树的概念及结构

1.1 概念

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

二叉树的特点

  1. 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。
  2. 二叉树的子树有左右之分,其子树的次序不能颠倒。

1.2 特殊的二叉树

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

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

1.3 二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,而现实中使用中只有堆才会使用数组来存储。

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系

1.4 二叉树的性质(选择填空较多)

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

2. 二叉树的顺序结构

2.1 堆的概念及结构

现实中我们通常把(一种二叉树)使用顺序结构的数组来存储。

堆的性质:

1.堆中某个节点的值总是不大于或不小于其父节点的值;
2.堆总是一棵完全二叉树。

数据结构——二叉树(顺序结构与链式结构)
2.2 堆的实现

2.2.1 堆向下调整算法

通过从根节点开始的向下调整算法可以把它调整为一个小堆(大堆)。向下调整算法前提:左右子树必须是一个堆,才能调整。

算法思想:(假设是小根堆的调整)

1.从左右孩子中选择一个最小值
2.当前需要调整的数据与最小值进行比较:大于最小值,和最小值交换,从交换完的位置,继续执行第1步;小于等于最小值,结束调整。

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

数据结构——二叉树(顺序结构与链式结构)
代码如下:

void shiftDown(int* arr, int  n, int pos)
{
    //n为结点个数,pos为需要调整的位置
	int child = 2 * pos + 1;//左孩子
	while (child < n)
	{
		//找出左右孩子最小值
		if (child + 1 < n && arr[child] > arr[child + 1])
			++child;
		if (arr[child] < arr[pos])
		{
			swap(&arr[child], &arr[pos]);//交换
			pos = child;
			child = 2 * pos + 1;
		}
		else
			break;
	}
}

2.2.2 堆的创建

算法思想:

从倒数的第一个非叶子节点开始向下调整,一直调整到根节点,就可以调整成堆。
倒数第一个非叶子结点:(n-2) / 2

代码如下:

void createHeap(int* arr, int n)
{
	//从第一个非叶子结点开始
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; i--)
	{
		shiftDown(arr, n, i);
	}
}

2.2.3 向上调整算法

算法思想:

大堆调整:首先和父节点进行比较,如果:大于父节点,交换,更新位置,从父节点位置继续向上看;小于等于父节点,结束调整。

小堆调整:首先和父节点进行比较,如果:小于父节点,交换,更新位置,从父节点位置继续向上看;大于等于父节点,结束调整。

代码如下:

//向上调整(小堆)
void shiftUp(int* arr, int n, int pos)
{
	int parent = (pos - 1) / 2;
	while (pos > 0)
	{
		if (arr[pos] < arr[parent])
		{
			swap(&arr[pos], &arr[parent]);
			pos = parent;
			parent = (pos - 1) / 2;
		}
		else
			break;
	}
}

2.2.4 堆的插入

算法思想:

尾插一个数据,再从尾插的数据进行向上调整,直到满足堆

数据结构——二叉树(顺序结构与链式结构)
代码如下:

void heapPush(Heap* hp, HDataType val)
{
	//检查容量
	checkCapacity(hp);
	//尾插
	hp->data[hp->size++] = val;
	//向上调整
	shiftUp(hp->data, hp->size, hp->size-1);
}

2.2.5 堆的删除:删除最值

算法思想:

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。

数据结构——二叉树(顺序结构与链式结构)
代码如下:

void heapPop(Heap* hp)
{
	//判空
	if (heapEmpty(hp))
		return;
	//最大(最小)和最后一个元素交换
	swap(&hp->data[0], &hp->data[hp->size - 1]);
	//尾删
	hp->size--;
	//向下调整
	shiftDown(hp->data, hp->size, 0);
}

2.2.6 堆的全部代码实现

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

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//向下调整:logn(小堆)
void shiftDown(int* arr, int  n, int pos)
{
	int child = 2 * pos + 1;//左孩子
	while (child < n)
	{
		//找出左右孩子最小值
		if (child + 1 < n && arr[child] > arr[child + 1])
			++child;
		if (arr[child] < arr[pos])
		{
			swap(&arr[child], &arr[pos]);
			pos = child;
			child = 2 * pos + 1;
		}
		else
			break;
	}
}

//堆的创建
void createHeap(int* arr, int n)
{
	//从第一个非叶子结点开始
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; i--)
	{
		shiftDown(arr, n, i);
	}
}


//向上调整(小堆)
void shiftUp(int* arr, int n, int pos)
{
	int parent = (pos - 1) / 2;
	while (pos > 0)
	{
		if (arr[pos] < arr[parent])
		{
			swap(&arr[pos], &arr[parent]);
			pos = parent;
			parent = (pos - 1) / 2;
		}
		else
			break;
	}
}

//初始化
void InitHeap(Heap* hp)
{
	if (hp == NULL)
		return;
	hp->capacity = hp->size = 0;
	hp->data = NULL;
}

//检查容量
void checkCapacity(Heap* hp)
{
	if (hp->size == hp->capacity)
	{
		hp->capacity = hp->capacity == 0 ? 1 : 2 * hp->capacity;
		hp->data = (HDataType*)realloc(hp->data, sizeof(HDataType)*hp->capacity);
	}
}

//堆的插入
void heapPush(Heap* hp, HDataType val)
{
	//检查容量
	checkCapacity(hp);
	//尾插
	hp->data[hp->size++] = val;
	//向上调整
	shiftUp(hp->data, hp->size, hp->size-1);
}


//堆的判空
int heapEmpty(Heap* hp)
{
	if (hp == NULL || hp->size == 0)
		return 1;
	return 0;
}

//堆的删除
void heapPop(Heap* hp)
{
	//判空
	if (heapEmpty(hp))
		return;
	//最大(最小)和最后一个元素交换
	swap(&hp->data[0], &hp->data[hp->size - 1]);
	//尾删
	hp->size--;
	//向下调整
	shiftDown(hp->data, hp->size, 0);
}

//取栈顶元素
HDataType heapTop(Heap* hp)
{
	return hp->data[0];
}

//堆的数据个数
int heapSize(Heap* hp)
{
	return hp->size;
}


//堆的销毁
void HeapDestory(Heap* hp)
{
	free(hp->data);
	hp->data = NULL; 
}

void printHeap(Heap* hp)
{
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->data[i]);
	}
	printf("\n");
}

3. 二叉树链式结构

3.1 二叉树链式结构的遍历

1.前序遍历:先访问根结点->然后是左子树->最后是右子树
2.中序遍历:先访问左子树->然后是根节点->最后是右子树
2.后序遍历:先访问左子树->然后是右子树->最后是根节点
3.层序遍历:首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

3.2 二叉树的全部实现代码

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

1.二叉树的创建,index需要传指针,这样可以真正的改变index,否则index只是局部变量,index起不到遍历数组的作用

2.二叉树节点个数:左子树+右子树+13.

3.二叉树高度:左右子树高度的最大值 + 1

4.层序遍历:用队列当容器

typedef char DataType;

//二叉树的结点
typedef struct BNode
{
	struct BNode* left;//左孩子
	struct BNode* right;//右孩子
	DataType data;
}Node;

//创建二叉链  前序
Node* BTreeCreate(DataType arr[], int* index) 
{
	if (arr[*index] == '#')
	{
		(*index)++;
		return NULL;
	}
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = arr[*index];
	(*index)++;
	node->left = BTreeCreate(arr, index);
	node->right = BTreeCreate(arr, index);
	return node;
}

//前序遍历  根-左-右
void bTreePrevOrder(Node* root)
{
	if (root == NULL)
		return;
	printf("%c ", root->data);
	bTreePrevOrder(root->left);
	bTreePrevOrder(root->right);
}


//中序遍历  左-根-右
void bTreeInOrder(Node* root)
{
	if (root)
	{
		bTreeInOrder(root->left);
		printf("%c ", root->data);
		bTreeInOrder(root->right);
	}
}


//后序遍历  左-右-根
void bTreePostOrder(Node* root)
{
	if (root)
	{
		bTreePostOrder(root->left);
		bTreePostOrder(root->right);
		printf("%c ", root->data);
	}
}


//节点个数  左子树+右子树+1
int BTreeSize(Node* root)
{
	if (root == NULL)
		return 0;
	return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}


//二叉树高度  max(左右子树的高度) + 1
int BTreeHeight(Node* root)
{
	if (root == NULL)
		return 0;
	int left = BTreeHeight(root->left);
	int right = BTreeHeight(root->right);
	return left > right ? left + 1 : right + 1;
}


//叶子节点个数 
int BTreeLeaf(Node* root)
{
	//空节点
	if (root == NULL)
		return 0;
	//叶子节点
	if (root->left == NULL && root->right == NULL)
		return 1;
	//非叶子节点
	return BTreeLeaf(root->left) + BTreeLeaf(root->right); 
}


//第K层节点个数   
int BTreeKSize(Node* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeKSize(root->left, k - 1) + BTreeKSize(root->right, k - 1);
}


//二叉树查找值为x的节点
Node* BTreeFind(Node* root, char val)
{
	if (root)
	{
		Node* node;
		if (root->data == val)
			return root;
		node = BTreeFind(root->left, val);
		if (node)
			return node;
		else
			return BTreeFind(root->right, val); 
	}
	else
		return NULL;
}



//层序遍历   用队列当作容器
void bTreeLevelOrder(Node* root)
{
	struct queue q;
	queueInit(&q);//队列初始化
	if (root)
		queuePush(&q, root);//队列入队
	while (!queueEmpty(&q))//队列判空
	{
		 Node* node = queueFront(&q);//获取队头元素
		queuePop(&q);//出队
		printf("%c ", node->data);
		if (node->left)//左孩子不为空,入队
			queuePush(&q, node->left);
		if (node->right)//右孩子不为空,入队
			queuePush(&q, node->right);
	}
}


//判断是否是完全二叉树
int isBTreeComplete(Node* root)
{
	queue q;
	queueInit(&q);
	if (root)
		queuePush(&q, root);
	while (!queueEmpty(&q))
	{
		Node* node = queueFront(&q);
		queuePop(&q);
		if (node)
		{
			queuePush(&q, node->left);
			queuePush(&q, node->right);
		}
		else
			break;
	}
	while (!queueEmpty(&q))
	{
		Node* node = queueFront(&q);
		queuePop(&q);
		if (node != NULL)
			return 0;
	}
	return 1;
}

//销毁二叉树
void BTreeDestory(Node** root)
{
	if (*root)
	{
		BTreeDestory(&((*root)->left));
		BTreeDestory(&((*root)->right));
		free(*root);
		*root = NULL;
	}
}
上一篇:python 人物对打 类


下一篇:2021-01-30