【數(shù)據(jù)結(jié)構(gòu)】---幾分鐘簡(jiǎn)單幾步學(xué)會(huì)手撕鏈?zhǔn)蕉鏄?下)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】---幾分鐘簡(jiǎn)單幾步學(xué)會(huì)手撕鏈?zhǔn)蕉鏄?下)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

前言

??個(gè)人主頁(yè)：@小沈熬夜禿頭中????
??小編介紹：歡迎來到我的亂七八糟小星球??
??專欄：數(shù)據(jù)結(jié)構(gòu)
??本章內(nèi)容：手撕鏈?zhǔn)蕉鏄?br> 送給各位??：成為更好的自己才是應(yīng)該做的事
記得評(píng)論?? +點(diǎn)贊?? +收藏?? +關(guān)注??哦~

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

??一、二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)

??1.1 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)

??代碼：

int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

??流程圖：

??1.2 二叉樹的高度

??第一種寫法(不支持)：

??代碼：

int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BTreeHeight(root->left) > BTreeHeight(root->right) ?
		BTreeHeight(root->left) + 1 : BTreeHeight(root->right) + 1;
}

??流程圖：

由圖可知，每次比較完后并沒有記錄數(shù)據(jù)而是再次調(diào)用當(dāng)樹躍高底層最大的那個(gè)函數(shù)調(diào)用的次數(shù)就越多，所以這種方法雖然對(duì)但是耗時(shí)太長(zhǎng)，而底層也就變成了所謂的天選打工人

??第二種寫法：

??代碼：

int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right );
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

??流程圖：

每次調(diào)用都記錄上數(shù)據(jù)，這樣比較完直接返回大的那個(gè)+1；

??1.3 二叉樹第K層的節(jié)點(diǎn)個(gè)數(shù)

??代碼：

int BTreeLevelKSize(BTNode* root,int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeLevelKSize(root->left, k - 1) 
		+ BTreeLevelKSize(root->right, k - 1);
}

??流程圖：

??1.4 二叉樹查找值為x的節(jié)點(diǎn)

??第一種寫法(錯(cuò)誤示范)：

??代碼：

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data  == x)
		return root;
	BTreeFind(root->left, x);
	BTreeFind(root->right, x);
}

??流程圖：

??第二種寫法(正確寫法)：

??代碼：

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data  == x)
		return root;
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BTreeFind(root->left, x);
	if (ret2)
		return ret2;
	return NULL;
}

??流程圖：

??1.5 層序遍歷

??代碼：

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)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}

??思路流程(多種嵌套)：

對(duì)于層序遍歷,可以采用隊(duì)列的思想(先進(jìn)先出)
具體核心思想：上一層出時(shí)帶下一層進(jìn)隊(duì)列所以進(jìn)入時(shí)不能存儲(chǔ)樹節(jié)點(diǎn)的值而是存儲(chǔ)樹節(jié)點(diǎn)指針

??1.6 二叉樹銷毀(采用后序)

??代碼：

void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestroy(root->left);
	BTreeDestroy(root->right);
	free(root);
}

??流程圖：

??1.7 判斷二叉樹是否是完全二叉樹

??代碼：

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)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//檢查后面的節(jié)點(diǎn)有沒有非空
	//有非空不是完全二叉樹
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)//往外拿數(shù)出現(xiàn)非空就不是完全二叉樹
		{
			return false;
			QueueDestroy(&q);
		}
	}
	return true;
	QueueDestroy(&q);
}

??思路流程：

和上述層序遍歷一樣，采用隊(duì)列思想，上一層出時(shí)帶下一層進(jìn)入，出現(xiàn)NULL時(shí)跳出然后將里面的數(shù)字往外拿，出現(xiàn)非空不是完全二叉樹>N代表空

??二、二叉樹鏈?zhǔn)浇Y(jié)構(gòu)完整代碼

//Queue.h
#pragma once
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>

typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode//每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);
//釋放
void QueueDestroy(Queue* pq);
//尾插(入隊(duì))
void QueuePush(Queue* pq, QDataType x);
//頭刪(出隊(duì))
void QueuePop(Queue* pq);
//隊(duì)頭數(shù)據(jù)
QDataType QueueFront(Queue* pq);
//隊(duì)尾數(shù)據(jù)
QDataType QueueBack(Queue* pq);
//數(shù)據(jù)個(gè)數(shù)
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);


//Queue.c
#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}


void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}


	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一個(gè)隊(duì)列
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = NULL;
		pq->ptail = NULL;
	}
	//多個(gè)隊(duì)列
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
	/*return pq->phead == NULL && pq->ptail == NULL;*/
	return pq->size == 0;
}


//Test.c
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include"Queue.h"

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("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);

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


void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

//二叉樹節(jié)點(diǎn)個(gè)數(shù) --- 遍歷計(jì)數(shù)
//int size = 0;
//void BTreeSzie(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//	BTreeSzie(root->left);
//	BTreeSzie(root->right);
//	return size;
//}

//int BTreeSzie(BTNode* root)
//{
//	static int size = 0;
//	//printf("%p,%d\n", &size,size);
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//	BTreeSzie(root->left );
//	BTreeSzie(root->right );
//	return size;
//}


int BTreeSzie(BTNode* root)
{
	return root == NULL ? 0 :
		BTreeSzie(root->left)
		+ BTreeSzie(root->right) + 1;
}

//二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BTreeLeafSize(root->left)
		+ BTreeLeafSize(root->right);
}

//二叉樹樹的高度
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

//二叉樹第k層的節(jié)點(diǎn)個(gè)數(shù)
int BTreeLevelKSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeLevelKSize(root->left, k - 1)
		+ BTreeLevelKSize(root->right, k - 1);
}

//二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	/*BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BTreeFind(root->left, x);
	if (ret2)
		return ret2;
	return NULL;*/
	//BTreeFind(root->left, x);
	//BTreeFind(root->right, x);
	//return NULL;
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	return BTreeFind(root->left, x);
}

//層序遍歷---用隊(duì)列
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)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}

void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestroy(root->left);
	BTreeDestroy(root->right);
	free(root);
}

//判斷二叉樹是否是完全二叉樹
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)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//檢查后面的節(jié)點(diǎn)有沒有非空
	//有非空不是完全二叉樹
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return false;
			QueueDestroy(&q);
		}
	}
	return true;
	QueueDestroy(&q);
}

int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	/*BTreeSzie(root);
	printf("BTreeSize:%d\n", size);
	size = 0;
	BTreeSzie(root);
	printf("BTreeSize:%d\n", size);
	size = 0;
	BTreeSzie(root);
	printf("BTreeSize:%d\n", size);*/

	printf("BTreeSize:%d\n", BTreeSzie(root));
	printf("BTreeLeafSize: % d\n", BTreeLeafSize(root));
	printf("BTreeHeight: % d\n", BTreeHeight(root));
	printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root, 3));
	printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root, 2));
	

	LevelOrder(root);

	printf("BTreeComplete: % d\n", BTreeComplete(root));
	
	BTreeDestroy(root);
	root = NULL;
	return 0;
}

??總結(jié)

??Ending,今天的鏈?zhǔn)蕉鏄?/mark>的內(nèi)容就到此結(jié)束啦~，如果后續(xù)想了解更多，就請(qǐng)關(guān)注我吧，一鍵三連哦 ~文章來源地址http://www.zghlxwxcb.cn/news/detail-479406.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】---幾分鐘簡(jiǎn)單幾步學(xué)會(huì)手撕鏈?zhǔn)蕉鏄?下)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！