數據結構：二叉樹的遞歸實現(C實現)

在這里插入圖片描述

個人主頁 ： 個人主頁
個人專欄 ： 《數據結構》 《C語言》

文章目錄

  • 前言
  • 一、樹的概念
  • 二、二叉樹
    • 二叉樹的概念
    • 二叉樹的性質
  • 三、二叉樹鏈式結構實現
    • 二叉樹節點定義
    • 創建二叉樹節點
    • 遍歷二叉樹
      • 先序遍歷二叉樹(BinaryTreePrevOrder)
      • 中序遍歷二叉樹(BinaryTreeInOrder)
      • 后序遍歷二叉樹(BinaryTreePostOrder)
      • 層序遍歷二叉樹(BinaryTreeLevelOrder)
    • 二叉樹節點個數(BinaryTreeSize)
    • 二叉樹第K層節點個數(BinaryTreeLevelKSize)
    • 二叉樹葉子節點個數(BinaryTreeLeafSize)
    • 二叉樹查找值為X的節點(BinaryTreeFind)
    • 判斷二叉樹是否是完全二叉樹(BinaryTreeComplete)
    • 通過前序遍歷的數組構建二叉樹
  • 四、代碼展示
    • 二叉樹代碼展示
    • 隊列代碼展示
  • 總結

前言

本篇博客主要講解二叉樹的相關操作如下：

//通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);//二叉樹的銷毀
void BinaryTreeDestroy(BTNode* root);//二叉樹節點個數
int BinaryTreeSize(BTNode* root);//二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);//二叉樹第K層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);//二叉樹查找值為X的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);//二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root);//二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);//二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);//層序遍歷
void BinaryTreeLevelOrder(BTNode* root);//判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root);//創建二叉樹的節點
BTNode* BuyBinaryTreeNode(BTDataType x);

一、樹的概念

樹是一種非線性結構，它是由n個有限節點組成的一個有層次關系的集合。

在這里插入圖片描述

  • 圖中A節點沒有前驅節點，被稱為根節點
  • 除根節點外，其余節點被分成兩個無不相交的集合T1(B,D,E,F…)，T2(C,G,H,L…)。其中每個集合T又是一顆結構與樹類似的子樹。每一顆子樹的根節點有且只有一個根節點，可以有0個或多個后繼節點
  • 因此，樹是遞歸定義的。
  • 樹的子樹不能有交集，否則就為圖。
  • 節點的度：一個節點含有的子樹的個數稱為該節點的度；如上圖A節點的度是2
  • 葉節點或終端節點：度為0的節點被稱為葉節點；如上圖：K,J,F,L,O,P為葉節點
  • 非終端節點或分支節點：度不為0的節點；如上圖：A,B,C,D,E…等節點為分支節點
  • 雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點。如上圖A節點是B,C的父節點
  • 孩子節點或子節點：若一個節點含有子樹，則子樹的根節點就是該節點的子節點。如上圖B,C是A的子節點
  • 兄弟節點：具有相同的父節點的節點互為兄弟節點。如上圖B,C互為兄弟節點
  • 樹的度：一顆樹中，最大節點的度就是該數的度。如上圖數的度為3
  • 節點的層次：從根開始定義起，根為第一層，根的子節點為第二層，依次類推。如上圖G節點的層次為3
  • 樹的高度或深度：樹中節點的最大層次。如上圖樹的深度為5
  • 堂兄弟節點：父節點在同一層的節點互為堂兄弟節點。如上圖D,G互為堂兄弟節點
  • 節點的祖先：從根到該節點所經分支上的所以節點。如上圖A是所以節點的祖先
  • 子孫節點 ：以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖所以節點是A的子孫
  • 森林：由m棵互不相交的樹的集合稱為森林

二、二叉樹

二叉樹的概念

由一個根節點加上兩顆子樹構成 。

在這里插入圖片描述

  • 二叉樹的度最大為2
  • 二叉樹是有序樹，二叉樹的子樹有左右之分，次序不能顛倒

二叉樹的性質

若規定根節點的層數是1，則一個非空二叉樹的第K層最多有2^(k - 1)個節點

若規定根節點的層數是1，則深度為h的二叉樹的最大節點數是2^h - 1

對于任何一顆二叉樹，如果度為0的節點為N0，度為2的節點為N2，那么N0 = N2 + 1 (數學歸納)

若規定根節點的層數是1，具有N個節點的滿二叉樹的深度為log(n + 1)[以2為底]

對于具有n個節點的完全二叉樹，如果按照從上至下從左到右的數組順序對所以節點從0開始編號(也就是堆的結構)，則對序號為K的節點有：
若k>0,k節點的父節點的序號：(k - 1) / 2;
如果k是0(根節點)，則無父節點
若2k+1<n，左孩子序號 2k+1，右孩子序號2k+2 如果2k+1> n則無左孩子 2*k+2>n則無右孩子

三、二叉樹鏈式結構實現

二叉樹節點定義

節點需要一個數據域，一個指向左孩子節點的指針，一個指向右孩子節點的指針。
在這里插入圖片描述

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

創建二叉樹節點

我們只需要傳遞二叉樹節點的數據即可，動態開辟出的節點空間用返回值的方式接受。
malloc出一塊節點空間，將函數參數給data，使left 和 right 指向NULL，返回該空間的地址

在這里插入圖片描述

//創建二叉樹的節點
BTNode* BuyBinaryTreeNode(BTDataType x)
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc:");exit(-1);}root->data = x;root->left = root->right = NULL;return root;
}

為了方便我們理解，這里我們先手動創建一個二叉樹來進行講解相關操作，最后在來講解先序創建二叉樹。

void test()
{BTNode* a = BuyBinaryTreeNode('A');BTNode* b = BuyBinaryTreeNode('B');BTNode* c = BuyBinaryTreeNode('C');BTNode* d = BuyBinaryTreeNode('D');BTNode* e = BuyBinaryTreeNode('E');BTNode* f = BuyBinaryTreeNode('F');BTNode* g = BuyBinaryTreeNode('G');BTNode* h = BuyBinaryTreeNode('H');a->left = b;b->left = d;b->right = e;e->right = h;a->right = c;c->left = f;c->right = g;
}

創建的二叉樹就是下圖所示：
在這里插入圖片描述

遍歷二叉樹

遍歷二叉樹有多種方式：

  • 先序遍歷 ：根節點 -> 左子樹 -> 右子樹
  • 中序遍歷 ：左子樹-> 根節點 -> 右子樹
  • 后序遍歷 ：左子樹 -> 右子樹 -> 根節點
  • 層序遍歷 ： 從左到右從上到下，依次遍歷二叉樹節點

先序遍歷二叉樹(BinaryTreePrevOrder)

對于下圖中的二叉樹，其先序遍歷結果為：ABD##E#H##CF##G##( ’ # ’ 表示NULL )
在這里插入圖片描述
那么是如何遍歷的？我們需要按照根，左，右的順序遞歸二叉樹即可。
在這里插入圖片描述

//二叉樹前序遍歷   根節點 左子樹  右子樹
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}//根節點printf("%c ", root->data);//左子樹BinaryTreePrevOrder(root->left);//右子樹BinaryTreePrevOrder(root->right);
}

這份代碼是如何展開的？
在這里插入圖片描述

中序遍歷二叉樹(BinaryTreeInOrder)

中序遍歷與先序遍歷類似，只有將根節點的訪問與左子樹遞歸交換執行順序即可
對于下圖中的二叉樹，其中序遍歷結果為：#D#B#E#H#A#F#C#G# ( ’ # ’ 表示NULL )
在這里插入圖片描述
在這里插入圖片描述

//二叉樹中序遍歷		左子樹  根  右子樹
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}//左子樹BinaryTreeInOrder(root->left);//根printf("%c ", root->data);//右子樹BinaryTreeInOrder(root->right);
}

后序遍歷二叉樹(BinaryTreePostOrder)

后序遍歷，就是再次調整根節點的訪問順序，將根節點的訪問順序調整到左子樹遞歸與右子樹遞歸后即可。

對于下圖中的二叉樹，其中序遍歷結果為：##D###HEB##F##GCA ( ’ # ’ 表示NULL )
在這里插入圖片描述
在這里插入圖片描述

//二叉樹后序遍歷  左子樹 右子樹 根
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}//左子樹BinaryTreePostOrder(root->left);//右子樹BinaryTreePostOrder(root->right);//根printf("%c ", root->data);
}

層序遍歷二叉樹(BinaryTreeLevelOrder)

要實現二叉樹的層序遍歷，我們需要借助隊列。
我們將根節點先入隊列，之后我們每次出隊頭數據時，將該隊頭數據指向的左子節點 與 右子節點分別入隊列，如果左子節點 或 右子節點 為NULL就不入隊列，重復上述過程直到隊列為空

在這里插入圖片描述

//層序遍歷  借助隊列  出隊頭數據時，將其左子節點 與 右子節點依次入隊列
void BinaryTreeLevelOrder(BTNode* root)
{Quene q;QueneInit(&q);//入根節點QuenePush(&q, root);//隊列為空，代表二叉樹中元素也遍歷完成while (!QueneEmpty(&q)){QDataType val = QueneFront(&q);printf("%c ", val->data);//入數據  該節點的左節點 與 右節點if (val->left != NULL)QuenePush(&q, val->left);if (val->right != NULL)QuenePush(&q, val->right);//出隊頭數據QuenePop(&q);}QueneDestrory(&q);
}

二叉樹節點個數(BinaryTreeSize)

我們使用遞歸的思路來看待二叉樹節點個數的接口。
子問題：根節點的左子樹的節點個數 與 根節點的右子樹的節點個數
結束條件：空節點返回
所以求二叉樹節點個數的問題可以轉換為求根節點左子樹節點數 + 根節點右子樹節點數 +根節點的節點總數

//二叉樹節點個數   根節點的左子樹與右子樹的節點個數和  
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}//        左子樹節點數                 右子樹節點數               根節點return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

對于下面二叉樹的遞歸展開圖：
在這里插入圖片描述
在這里插入圖片描述

二叉樹第K層節點個數(BinaryTreeLevelKSize)

函數聲明：

int BinaryTreeLevelKSize(BTNode* root, int k);

子問題：根節點左子樹第K-1層節點個數 與 根節點右子樹第K-1層節點個數
結束條件：訪問到空節點 或 找到所求層數(k == 1)

也就是說，求二叉樹第K層節點數的問題轉換為求根節點左子樹第K-1層節點數 與 根節點右子樹第K-1層節點數之和。

//二叉樹第K層節點個數       左子樹的第k-1層節點數 + 右子樹的第k-1層節點數     不同棧幀的k互不影響
int BinaryTreeLevelKSize(BTNode* root, int k)
{//如果 k 超過數的深度if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

對于下面二叉樹，求第3層節點數的遞歸展開圖。
在這里插入圖片描述
在這里插入圖片描述

二叉樹葉子節點個數(BinaryTreeLeafSize)

函數聲明：

int BinaryTreeLeafSize(BTNode* root);

子問題：根節點左子樹葉子結點 與 根節點右子樹葉子結點
結束條件：訪問到空節點 或 訪問到葉子結點

原問題轉換成根節點左子樹葉子結點個數 + 根節點右子樹葉子結點個數。


//二叉樹葉子節點個數   左子樹的葉子節點 + 右子樹的葉子結點
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);
}

對于下面二叉樹，求其葉子結點的個樹的遞歸展開圖
在這里插入圖片描述
在這里插入圖片描述

二叉樹查找值為X的節點(BinaryTreeFind)

先序遍歷查找節點，如果是該節點，直接返回該節點地址。如果不是該節點，繼續查找該節點的左子樹，如果左子樹也沒找到，查找右子樹。

//二叉樹查找值為X的節點   前序遍歷查找  
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;//根if (root->data == x)return root;//左子樹BTNode* leftNode = BinaryTreeFind(root->left, x);if (leftNode != NULL)return leftNode;//右子樹BTNode* rightNode = BinaryTreeFind(root->right, x);if (rightNode != NULL)return rightNode;return NULL;
}

對于下面二叉樹，查找 ’ C '的遞歸展開圖
在這里插入圖片描述
在這里插入圖片描述

判斷二叉樹是否是完全二叉樹(BinaryTreeComplete)

完全二叉樹也就是堆，當其層序遍歷時，其中有效數據(不包含NULL)是連續的。
只需要借助隊列，來層序遍歷二叉樹(如果某個節點左子節點或右子節點是NULL也入隊列)。當隊列首數據是NULL時，判斷其后數據是否全是NULL，如果其后數據全是NULL，返回true，如果其后元素有一個不是NULL，返回false。


//完全二叉樹的節點是連續的，層序遍歷二叉樹，如果遇到NULL，檢查棧中后續元素是否都為NULL
bool BinaryTreeComplete(BTNode* root)
{Quene q;QueneInit(&q);QuenePush(&q, root);while (!QueneEmpty(&q)){BTNode* node = QueneFront(&q);QuenePop(&q);if (node != NULL){QuenePush(&q, node->left);QuenePush(&q, node->right);}else{break;}}while (!QueneEmpty(&q)){BTNode* node = QueneFront(&q);QuenePop(&q);if (node != NULL){QueneDestrory(&q);return false;}}QueneDestrory(&q);return true;
}

通過前序遍歷的數組構建二叉樹

在先序遍歷的數組中，我們以’ # '代表NULL。
函數聲明：其中a是先序遍歷的數組，n是節點數，pi是現在節點的個數

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);

子問題：構建左子樹與右子樹
結束條件：遇到先序遍歷數組的’ # '或節點數大于n
創建根節點，再遍歷左子樹和右子樹，使根節點指向左子樹與右子樹。

//通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi >= n  || a[*pi] == '#'){(*pi)++;return NULL;}BTNode* newnode = BuyBinaryTreeNode(a[*pi]);(*pi)++;//左子節點BTNode* leftnode = BinaryTreeCreate(a, n, pi);newnode->left = leftnode;//右子節點BTNode* rightnode = BinaryTreeCreate(a, n, pi);newnode->right = rightnode;return newnode;
}

四、代碼展示

二叉樹代碼展示

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);//二叉樹的銷毀
void BinaryTreeDestroy(BTNode* root);//二叉樹節點個數
int BinaryTreeSize(BTNode* root);//二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);//二叉樹第K層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);//二叉樹查找值為X的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);//二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root);//二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);//二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);//層序遍歷
void BinaryTreeLevelOrder(BTNode* root);//判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root);//創建二叉樹的節點
BTNode* BuyBinaryTreeNode(BTDataType x);

#include "BinaryTree.h"
#include "quene.h"//創建二叉樹的節點
BTNode* BuyBinaryTreeNode(BTDataType x)
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc:");exit(-1);}root->data = x;root->left = root->right = NULL;return root;
}//二叉樹前序遍歷   根節點 左子樹  右子樹
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}//根節點printf("%c ", root->data);//左子樹BinaryTreePrevOrder(root->left);//右子樹BinaryTreePrevOrder(root->right);
}//二叉樹中序遍歷		左子樹  根  右子樹
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}//左子樹BinaryTreeInOrder(root->left);//根printf("%c ", root->data);//右子樹BinaryTreeInOrder(root->right);
}//二叉樹后序遍歷  左子樹 右子樹 根
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}//左子樹BinaryTreePostOrder(root->left);//右子樹BinaryTreePostOrder(root->right);//根printf("%c ", root->data);
}//二叉樹的銷毀  后序遍歷二叉樹 
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL){return;}//左子樹BinaryTreeDestroy(root->left);//右子樹BinaryTreeDestroy(root->right);//根free(root);
}//二叉樹節點個數   根節點的左子樹與右子樹的節點個數和  
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}//        左子樹節點數                 右子樹節點數               根節點return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}//二叉樹葉子節點個數   左子樹的葉子節點 + 右子樹的葉子結點
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層節點個數       左子樹的第k層節點數 + 右子樹的第k層節點數     不同棧幀的k互不影響
int BinaryTreeLevelKSize(BTNode* root, int k)
{//如果 k 超過數的深度if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}//二叉樹查找值為X的節點   前序遍歷查找  
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;//根if (root->data == x)return root;//左子樹BTNode* leftNode = BinaryTreeFind(root->left, x);if (leftNode != NULL)return leftNode;//右子樹BTNode* rightNode = BinaryTreeFind(root->right, x);if (rightNode != NULL)return rightNode;return NULL;
}//層序遍歷  借助隊列  出隊頭數據時，將其左子節點 與 右子節點依次入隊列
void BinaryTreeLevelOrder(BTNode* root)
{Quene q;QueneInit(&q);//入根節點QuenePush(&q, root);//隊列為空，代表二叉樹中元素也遍歷完成while (!QueneEmpty(&q)){QDataType val = QueneFront(&q);printf("%c ", val->data);//入數據  該節點的左節點 與 右節點if (val->left != NULL)QuenePush(&q, val->left);if (val->right != NULL)QuenePush(&q, val->right);//出隊頭數據QuenePop(&q);}QueneDestrory(&q);
}//判斷二叉樹是否是完全二叉樹    層序遍歷二叉樹//bool BinaryTreeComplete(BTNode* root)
//{
//	Quene q;
//	QueneInit(&q);
//
//	//如果某個節點的右節點為空，那么之后遍歷的節點的左/右節點也應該為空
//	bool flag = false;
//
//	QuenePush(&q, root);
//	while (!QueneEmpty(&q))
//	{
//		QDataType val = QueneFront(&q);
//
//		if (val->left == NULL && val->right != NULL)
//			return false;
//
//		if (flag == true && (val->left != NULL || val->right != NULL))
//			return false;
//
//		if (val->left != NULL)
//			QuenePush(&q, val->left);
//
//		if (val->right != NULL)
//			QuenePush(&q, val->right);
//		else
//			flag = true;
//
//		QuenePop(&q);
//	}
//
//	return true;
//}//完全二叉樹的節點是連續的，層序遍歷二叉樹，如果遇到NULL，檢查棧中后續元素是否都為NULL
bool BinaryTreeComplete(BTNode* root)
{Quene q;QueneInit(&q);QuenePush(&q, root);while (!QueneEmpty(&q)){BTNode* node = QueneFront(&q);QuenePop(&q);if (node != NULL){QuenePush(&q, node->left);QuenePush(&q, node->right);}else{break;}}while (!QueneEmpty(&q)){BTNode* node = QueneFront(&q);QuenePop(&q);if (node != NULL){QueneDestrory(&q);return false;}}QueneDestrory(&q);return true;
}//通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (*pi >= n  || a[*pi] == '#'){(*pi)++;return NULL;}BTNode* newnode = BuyBinaryTreeNode(a[*pi]);(*pi)++;//左子節點BTNode* leftnode = BinaryTreeCreate(a, n, pi);newnode->left = leftnode;//右子節點BTNode* rightnode = BinaryTreeCreate(a, n, pi);newnode->right = rightnode;return newnode;
}

隊列代碼展示

#include "BinaryTree.h"
#include <assert.h>//隊列 節點結構--樹節點
typedef struct QueneNode
{struct BinaryTreeNode* data;struct QueneNode* next;
}QueneNode;typedef struct BinaryTreeNode* QDataType;//隊列 結構
typedef struct Quene
{QueneNode* head;QueneNode* tail;int size;
}Quene;//初始化隊列
void QueneInit(Quene* q);//隊尾入隊列
void QuenePush(Quene* q, QDataType x);//隊頭出數據
void QuenePop(Quene* q);//獲取隊列頭部元素
QDataType QueneFront(Quene* q);//獲取隊列隊尾元素
QDataType QueneBack(Quene* q);//獲取隊列中有效元素個數
int QueneSize(Quene* q);//檢查隊列是否為空，如果為空返回ture，如果非空返回false
bool QueneEmpty(Quene* q);//銷毀隊列
void QueneDestrory(Quene* q);

#include "quene.h"//初始化隊列
void QueneInit(Quene* q)
{assert(q);q->head = q->tail = NULL;q->size = 0;
}//隊尾入隊列
void QuenePush(Quene* q, QDataType x)
{assert(q);QueneNode* newnode = (QueneNode*)malloc(sizeof(QueneNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->next = NULL;newnode->data = x;//隊列為空if (QueneEmpty(q) == true){q->head = q->tail = newnode;}else//隊列不為空{q->tail->next = newnode;q->tail = newnode;}q->size++;
}//隊頭出數據
void QuenePop(Quene* q)
{assert(q);//隊列為空assert(QueneEmpty(q) != true);//隊列只有一個元素if (q->head->next == NULL){free(q->head);q->head = q->tail = NULL;}else//隊列中有多個元素{QueneNode* next = q->head->next;free(q->head);q->head = next;}q->size--;
}//獲取隊列頭部元素
QDataType QueneFront(Quene* q)
{assert(q);return q->head->data;
}//獲取隊列隊尾元素
QDataType QueneBack(Quene* q)
{assert(q);return q->tail->data;
}//獲取隊列中有效元素個數
int QueneSize(Quene* q)
{assert(q);return q->size;
}//檢查隊列是否為空，如果為空返回ture，如果非空返回false
bool QueneEmpty(Quene* q)
{assert(q);return q->size == 0;
}//銷毀隊列
void QueneDestrory(Quene* q)
{assert(q);QueneNode* cur = q->head;while (cur){QueneNode* next = cur->next;free(cur);cur = next;}}

總結

以上就是我對于二叉樹的理解！！！
在這里插入圖片描述

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/41715.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/41715.shtml
英文地址，請注明出處：http://en.pswp.cn/news/41715.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Air780EG —— 合宙4G定位解決方案

Air780EG —— 合宙4G定位解決方案

定位模式&#xff1a; 外部單片機控制模式(常見于AT固件客戶)&#xff1a; 開機 -> 搜星 -> 定位成功 -> 上報 -> 關機 780E自行控制模式(常見于二次開發客戶&#xff0c;AT用戶也可以使用): 開機 -> 搜星 -> 定位成功 -> 模塊休眠&#xff0c;關閉GP…
閱讀更多...
億發創新中醫藥信息化解決方案，自動化煎煮＋調劑，打造智能中藥房

億發創新中醫藥信息化解決方案，自動化煎煮＋調劑，打造智能中藥房

傳統中醫藥行業逐步復興&#xff0c;同時互聯網科技和人工智能等信息科技助力中醫藥行業逐步實現數字化轉型。利用互聯網、物聯網、大數據等科技&#xff0c;實現現代科學與傳統中醫藥的結合&#xff0c;提供智能配方顆粒調配系統、中藥自動化調劑系統、中藥煎配智能管理系統、…
閱讀更多...
【從零學習python 】40.python魔法方法(一)

【從零學習python 】40.python魔法方法(一)

文章目錄 魔法方法1. __init__ 方法2. __del__ 方法3. __str__ 方法4. __repr__ 方法5. __call__ 方法進階案例 魔法方法 Python 里有一種方法&#xff0c;叫做魔法方法。Python 的類里提供的&#xff0c;兩個下劃線開始&#xff0c;兩個下劃線結束的方法&#xff0c;就是魔法…
閱讀更多...
如何切換goland之中的版本號（升級go 到1.20）

如何切換goland之中的版本號（升級go 到1.20）

go 安裝/版本切換_go 切換版本_云滿筆記的博客-CSDN博客 用brew就行&#xff1a; echo export PATH"/opt/homebrew/opt/go1.20/bin:$PATH" >> ~/.zshrc
閱讀更多...
[國產MCU]-BL602開發實例-OLED-SSD1306驅動與U8g2移植

[國產MCU]-BL602開發實例-OLED-SSD1306驅動與U8g2移植

OLED-SSD1306驅動與U8g2移植 文章目錄 OLED-SSD1306驅動與U8g2移植1、OLED介紹2、SSD1306介紹2、U8g2介紹3、U8g2移植3.1 定義U8g2圖形庫的移植函數3.2 移植函數實現3.3 移植函數調用4、驅動測試本文將詳細介紹如何在BL602中移植U8g2圖形庫，并通過U8g2庫驅動OLED SSD1306顯示屏…
閱讀更多...
Linux6.40 Kubernetes 配置資源管理

Linux6.40 Kubernetes 配置資源管理

文章目錄 計算機系統5G云計算第三章 LINUX Kubernetes 配置資源管理一、Secret1.Secret 四種類型1&#xff09;kubernetes.io/service-account-token2&#xff09;Opaque3&#xff09;kubernetes.io/dockerconfigjson4&#xff09;kubernetes.io/tls 2.Pod 需要先引用才能使用某…
閱讀更多...
React入門 jsx學習筆記

React入門 jsx學習筆記

一、JSX介紹 概念&#xff1a;JSX是 JavaScript XML&#xff08;HTML&#xff09;的縮寫&#xff0c;表示在 JS 代碼中書寫 HTML 結構 作用&#xff1a;在React中創建HTML結構&#xff08;頁面UI結構&#xff09; 優勢&#xff1a; 采用類似于HTML的語法&#xff0c;降低學…
閱讀更多...
因果推斷（四）斷點回歸（RD）

因果推斷（四）斷點回歸（RD）

因果推斷&#xff08;四&#xff09;斷點回歸&#xff08;RD&#xff09; 在傳統的因果推斷方法中&#xff0c;有一種方法可以控制觀察到的混雜因素和未觀察到的混雜因素&#xff0c;這就是斷點回歸&#xff0c;因為它只需要觀察干預兩側的數據&#xff0c;是否存在明顯的斷點…
閱讀更多...
【C++入門到精通】C++入門 —— list (STL)

【C++入門到精通】C++入門 —— list (STL)

閱讀導航 前言一、list簡介1.概念2.特點 二、list的使用1.list的構造2.常見的操作?std::list類型的增、刪、查、改 三、list與vector的對比溫馨提示 前言 文章綁定了VS平臺下std::list的源碼&#xff0c;大家可以下載了解一下&#x1f60d; 前面我們講了C語言的基礎知識&…
閱讀更多...
C語言實例_獲取文件MD5值

C語言實例_獲取文件MD5值

一、MD5介紹 MD5&#xff08;Message Digest Algorithm 5&#xff09;是一種常用的哈希函數算法。將任意長度的數據作為輸入&#xff0c;并生成一個唯一的、固定長度&#xff08;通常是128位&#xff09;的哈希值&#xff0c;稱為MD5值。MD5算法以其高度可靠性和廣泛應用而聞名…
閱讀更多...
全球磁強計市場價值約為16.2億美元，預測期內將以超過5.21%的增長率增長

全球磁強計市場價值約為16.2億美元，預測期內將以超過5.21%的增長率增長

磁強計是一種用于測量磁場強度和方向的儀器。它可以檢測和測量地球磁場、物體的磁性、地下礦藏、磁性材料等。磁強計在地球科學、物理學、地質學、勘探、礦業等領域具有廣泛的應用。 根據阿譜爾&#xff08;APO&#xff09;的統計及預測&#xff0c;2022年全球磁強計市場價值約…
閱讀更多...
跳跳！(c++題解)

跳跳！(c++題解)

題目描述 你是一只小跳蛙&#xff0c;你特別擅長在各種地方跳來跳去。 這一天&#xff0c;你和朋友小 F 一起出去玩耍的時候&#xff0c;遇到了一堆高矮不同的石頭&#xff0c;其中第 ii 塊的石頭高度為 hi?&#xff0c;地面的高度是 h0?0。你估計著&#xff0c;從第 ii 塊…
閱讀更多...
ts與vue

ts與vue

ts與Vue 如果你已經學習了typeScript,但不知道如何在vue項目中使用&#xff0c;那么這篇文章將會很適合你。參考千峰教育 kerwin視頻 1.會自動推導&#xff0c;隱士推導。提示 類型系統。 獨立模塊。 isolatedModules選項&#xff1a;是否配置為獨立的模塊。 減少報錯 let …
閱讀更多...
dispatcherServlet在tomcat啟動時如何被加載(1)

dispatcherServlet在tomcat啟動時如何被加載(1)

目錄 在springboot工程中, 如何添加一個servlet呢? 方法1 : 使用WebServlet注解 方法2 : 使用ServletRegistrationBean進行注冊 springmvc 采用的就是方式2和springboot集成的, 看一下源碼 springboot 字段裝配里面有這個類, 看一下源碼 90行, 創建了一個DispatcherServlet對象…
閱讀更多...
深入探究Socks5代理與IP代理在網絡安全與爬蟲中的應用

深入探究Socks5代理與IP代理在網絡安全與爬蟲中的應用

1. Socks5代理&#xff1a;打開網絡隧道的多功能工具 Socks5代理是一種流行的代理協議&#xff0c;它在傳輸層為數據包提供了隧道。相較于之前的版本&#xff0c;Socks5不僅支持TCP連接&#xff0c;還可以處理UDP流量&#xff0c;使其在需要實時數據傳輸的應用中表現出色。在網…
閱讀更多...
Zabbix配置通用的TCP/IP:port監控項

Zabbix配置通用的TCP/IP:port監控項

我們經常的用接口&#xff0c;比如說FTP、HTTP、DNS、數據庫接口&#xff0c;都可以用IP:PORT方式探測其是否存活&#xff0c;那么我們去繁就簡&#xff0c;就簡單監控一下IP&#xff1a;PORT吧&#xff01; 1、新建主機&#xff1a; 填入主機名稱、群組、Agent就是127.0.0.1…
閱讀更多...
解決Adobe Flash Player已被屏蔽

解決Adobe Flash Player已被屏蔽

問題&#xff1a;該插件不支持 原因&#xff1a;現在瀏覽器默認禁用flash 博主當前使用的是谷歌瀏覽器Chrome 2個主要方法都已經失效 搜索一圈后&#xff0c;之前博客給出的2個主要方法都已經失效。 1、flash.cn 下載本地播放器 2、在chrome中打開flash的禁用開關 2023年解…
閱讀更多...
LangChain源碼逐行解密之系統（二）

LangChain源碼逐行解密之系統（二）

LangChain源碼逐行解密之系統 20.2 serapi.py源碼逐行剖析 我們可以看一下Google查詢的例子，在LangChain中有多種實現的方式。 如圖20-5所示，在utilities的serpapi.py代碼文件中實現了SerpAPIWrapper。 圖20- 5 utilities的serpapi.py的SerpAPIWrapper 在langchain目錄的se…
閱讀更多...
@pyrallis.wrap()

@pyrallis.wrap()

pyrallis.wrap import pyrallis pyrallis.wrap() 這個pyrallis.wrap()是什么 pyrallis.wrap() 是一個 Python 裝飾器&#xff08;Decorator&#xff09;&#xff0c;用于將函數或方法包裝在 Pyrallis 框架提供的性能分析器中。裝飾器是 Python 中的一種特殊語法&#xff0c;允許…
閱讀更多...
如何避免爬蟲IP被屏蔽

如何避免爬蟲IP被屏蔽

各位爬友們好&#xff0c;作為一名專業的爬蟲代理提供者&#xff0c;我要和大家分享一些避免爬蟲IP被屏蔽的實用技巧。你知道嗎&#xff0c;當我們爬取數據的時候&#xff0c;很容易被目標網站識別出來并封禁我們的IP地址&#xff0c;導致無法繼續爬取數據。這個問題困擾了很多…
閱讀更多...
最新文章

Copyright @ 2022~2023