溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

C語言鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)原理是什么

發(fā)布時間：2021-11-17 14:23:49 來源：億速云 閱讀：120 作者：iii 欄目：開發(fā)技術(shù)

這篇文章主要介紹“C語言鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)原理是什么”，在日常操作中，相信很多人在C語言鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)原理是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C語言鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)原理是什么”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

二叉樹節(jié)點聲明

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

二叉樹的遍歷

二叉樹的遍歷，是學(xué)習(xí)二叉樹結(jié)構(gòu)的重要部分。二叉樹的遍歷主要分為三種：1.前序遍歷 2.中序遍歷 3.后序遍歷。首先我們要知道一顆二叉樹分為根，左子樹，右子樹。而三種遍歷方式也是圍繞著根來實現(xiàn)的。

構(gòu)建二叉樹

我們按上圖來構(gòu)建一顆二叉樹

BTNode* CreatTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTDataType));
	node->data = x;
	node->right = NULL;
	node->left = NULL;
	return node;
} 
int main()
{
   	BTNode* A = CreatTreeNode('A');
	BTNode* B = CreatTreeNode('B');
	BTNode* C = CreatTreeNode('C');
	BTNode* D = CreatTreeNode('D');
	BTNode* E = CreatTreeNode('E');
	BTNode* F = CreatTreeNode('F');
	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
 
}

1.前序遍歷

前序遍歷的順序為 根 左子樹 右子樹 顧名思義就是先訪問根節(jié)點再訪問左節(jié)點最后訪問右節(jié)點。

按照前序遍歷，則上圖的遍歷順序為：A B D NULL NULL NULL C E NULL NULL F NULL NULL

// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL) //等于NULL就直接返回
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);// 打印節(jié)點
	BinaryTreePrevOrder(root->left);//遞歸到左子樹
	BinaryTreePrevOrder(root->right);//遞歸到右子樹
}

2.中序遍歷

中序遍歷的順序為 左子樹 根 右 顧名思義就是先訪問左節(jié)點再訪問根節(jié)點最后訪問右節(jié)點。

按照中序遍歷，則上圖的遍歷順序為：NULL D NULL B NULL A NULL E NULL C NULL F NULL

// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL) //等于NULL就直接返回
	{
		printf("NULL ");
		return;
	}
	BinaryTreePrevOrder(root->left);//遞歸到左子樹
	printf("%c ", root->data);//打印節(jié)點
	BinaryTreePrevOrder(root->right);//遞歸到右子樹
}

3.后序遍歷

后序遍歷的順序為 左子樹 右子樹 根 顧名思義就是先訪問左節(jié)點，再訪問右節(jié)點，最后訪問根。

按照后序遍歷，則上圖的遍歷順序為：NULL NULL D NULL B NULL NULL E NULL NULL F C A

// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)//等于NULL直接返回
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);//遞歸到左子樹
	BinaryTreePostOrder(root->right);//遞歸到右子樹
	printf("%c ", root->data);//打印節(jié)點
	
}

二叉樹節(jié)點的個數(shù)

求二叉樹節(jié)點的個數(shù)與上述遍歷類似，都是通過遞歸函數(shù)來實現(xiàn)。一顆二叉樹的節(jié)點個數(shù)主要以三個部分構(gòu)成：根節(jié)點+左子樹的節(jié)點個數(shù)+右子樹的節(jié)點個數(shù)。知道這個公式我們就可以實現(xiàn)代碼

// 二叉樹節(jié)點個數(shù)
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)//如果為空返回零
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

二叉樹葉子節(jié)點的個數(shù)

葉子節(jié)點的左右子樹都為空，知道這個，我們只需稍微改動上述代碼即可

// 二叉樹葉子節(jié)點個數(shù)
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層節(jié)點個數(shù)

如果指定一顆二叉樹，求它第K層節(jié)點個數(shù)，也可以采用遞歸的思想，當(dāng)給定的K為零的時候此時就是求根節(jié)點的個數(shù)，顯而易見就是返回1；而K不為零時，我們可以求root左右子樹K-1層的節(jié)點數(shù)之和。

// 二叉樹第k層節(jié)點個數(shù)
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);
}

二叉樹的高度/深度

二叉樹的高度就是指二叉樹節(jié)點層次的最大值，也就是左右子樹最大高度+1.

//二叉樹深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
 
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

二叉樹查找值為x的節(jié)點

// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)  //根為空，直接返回NULL
	{
		return NULL;
	}
	if (root->data == x)//找到了 直接返回節(jié)點
	{
		return root;
	}
	BTNode* leftRet = BinaryTreeFind(root->left, x); 
	if (leftRet)
	{
		return leftRet; //如果再左子樹找到，直接返回，無需遞歸到右子樹
 
	}
	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet)
	{
		return rightRet; 
 
	}
 
	return NULL;  //如果都沒找到，就直接返回NULL
 
}

整體代碼

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef char BTDataType;
 
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
  
BTNode* CreatTreeNode(BTDataType x);
// 二叉樹節(jié)點個數(shù)
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節(jié)點個數(shù)
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);
//二叉樹深度/高度
int BinaryTreeDepth(BTNode* root);
  
#include"BinarryTree.h"
 
BTNode* CreatTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTDataType));
	assert(node);
	node->data = x;
	node->right = NULL;
	node->left = NULL;
	return node;
}
 
// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return ;
	}
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
 
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return ;
	}
	BinaryTreePrevOrder(root->left);
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->right);
}
 
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return ;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
 
}
  
// 二叉樹節(jié)點個數(shù)
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
 
// 二叉樹葉子節(jié)點個數(shù)
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層節(jié)點個數(shù)
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);
}
 
 
// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftRet = BinaryTreeFind(root->left, x);
	if (leftRet)
	{
		return leftRet;
 
	}
	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet)
	{
		return rightRet;
 
	}
 
	return NULL;
 
}
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root)
{
	if (*root)
	{
		BinaryTreeDestory(&(*root)->left);
		BinaryTreeDestory(&(*root)->right);
		free(*root);
		*root = NULL;
	}
}
 
//二叉樹深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
 
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
  
#include"BinarryTree.h"
  
int main()
{
	BTNode* A = CreatTreeNode('A');
	BTNode* B = CreatTreeNode('B');
	BTNode* C = CreatTreeNode('C');
	BTNode* D = CreatTreeNode('D');
	BTNode* E = CreatTreeNode('E');
	BTNode* F = CreatTreeNode('F');
	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
 
	return 0;
}

到此，關(guān)于“C語言鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)原理是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手