C語(yǔ)言 鏈?zhǔn)蕉鏄?shù)結(jié)構(gòu)詳解原理
前言
二叉樹(shù)不同于順序表,一顆普通的二叉樹(shù)是沒(méi)有增刪改查的意義。普通的二叉樹(shù)用來(lái)存儲(chǔ)數(shù)據(jù)是不方便的。但是二叉樹(shù)的一些基本實(shí)現(xiàn)結(jié)構(gòu),例如前序遍歷,中序遍歷。。。等等都是對(duì)我們學(xué)習(xí)更深層次的二叉樹(shù)打下夯實(shí)的基礎(chǔ)。
二叉樹(shù)節(jié)點(diǎn)聲明
typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
二叉樹(shù)的遍歷
二叉樹(shù)的遍歷,是學(xué)習(xí)二叉樹(shù)結(jié)構(gòu)的重要部分。二叉樹(shù)的遍歷主要分為三種:1.前序遍歷 2.中序遍歷 3.后序遍歷。首先我們要知道一顆二叉樹(shù)分為根,左子樹(shù),右子樹(shù)。而三種遍歷方式也是圍繞著根來(lái)實(shí)現(xiàn)的。
構(gòu)建二叉樹(shù)
我們按上圖來(lái)構(gòu)建一顆二叉樹(shù)
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.前序遍歷
前序遍歷的順序?yàn)?根 左子樹(shù) 右子樹(shù) 顧名思義就是先訪問(wèn)根節(jié)點(diǎn)再訪問(wèn)左節(jié)點(diǎn)最后訪問(wèn)右節(jié)點(diǎn)。
按照前序遍歷,則上圖的遍歷順序?yàn)椋篈 B D NULL NULL NULL C E NULL NULL F NULL NULL
// 二叉樹(shù)前序遍歷 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) //等于NULL就直接返回 { printf("NULL "); return; } printf("%c ", root->data);// 打印節(jié)點(diǎn) BinaryTreePrevOrder(root->left);//遞歸到左子樹(shù) BinaryTreePrevOrder(root->right);//遞歸到右子樹(shù) }
2.中序遍歷
中序遍歷的順序?yàn)?左子樹(shù) 根 右 顧名思義就是先訪問(wèn)左節(jié)點(diǎn)再訪問(wèn)根節(jié)點(diǎn)最后訪問(wèn)右節(jié)點(diǎn)。
按照中序遍歷,則上圖的遍歷順序?yàn)椋篘ULL D NULL B NULL A NULL E NULL C NULL F NULL
// 二叉樹(shù)中序遍歷 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) //等于NULL就直接返回 { printf("NULL "); return; } BinaryTreePrevOrder(root->left);//遞歸到左子樹(shù) printf("%c ", root->data);//打印節(jié)點(diǎn) BinaryTreePrevOrder(root->right);//遞歸到右子樹(shù) }
3.后序遍歷
后序遍歷的順序?yàn)?左子樹(shù) 右子樹(shù) 根 顧名思義就是先訪問(wèn)左節(jié)點(diǎn),再訪問(wèn)右節(jié)點(diǎn),最后訪問(wèn)根。
按照后序遍歷,則上圖的遍歷順序?yàn)椋篘ULL NULL D NULL B NULL NULL E NULL NULL F C A
// 二叉樹(shù)后序遍歷 void BinaryTreePostOrder(BTNode* root) { if (root == NULL)//等于NULL直接返回 { printf("NULL "); return; } BinaryTreePostOrder(root->left);//遞歸到左子樹(shù) BinaryTreePostOrder(root->right);//遞歸到右子樹(shù) printf("%c ", root->data);//打印節(jié)點(diǎn) }
二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù)
求二叉樹(shù)節(jié)點(diǎn)的個(gè)數(shù)與上述遍歷類(lèi)似,都是通過(guò)遞歸函數(shù)來(lái)實(shí)現(xiàn)。一顆二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)主要以三個(gè)部分構(gòu)成:根節(jié)點(diǎn)+左子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。知道這個(gè)公式我們就可以實(shí)現(xiàn)代碼
// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeSize(BTNode* root) { if (root == NULL)//如果為空返回零 { return 0; } return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; }
二叉樹(shù)葉子節(jié)點(diǎn)的個(gè)數(shù)
葉子節(jié)點(diǎn)的左右子樹(shù)都為空,知道這個(gè),我們只需稍微改動(dòng)上述代碼即可
// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(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); }
二叉樹(shù)第K層節(jié)點(diǎn)個(gè)數(shù)
如果指定一顆二叉樹(shù),求它第K層節(jié)點(diǎn)個(gè)數(shù),也可以采用遞歸的思想,當(dāng)給定的K為零的時(shí)候此時(shí)就是求根節(jié)點(diǎn)的個(gè)數(shù),顯而易見(jiàn)就是返回1;而K不為零時(shí),我們可以求root左右子樹(shù)K-1層的節(jié)點(diǎn)數(shù)之和。
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(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); }
二叉樹(shù)的高度/深度
二叉樹(shù)的高度就是指二叉樹(shù)節(jié)點(diǎn)層次的最大值,也就是左右子樹(shù)最大高度+1.
//二叉樹(shù)深度/高度 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; }
二叉樹(shù)查找值為x的節(jié)點(diǎn)
// 二叉樹(shù)查找值為x的節(jié)點(diǎn) BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) //根為空,直接返回NULL { return NULL; } if (root->data == x)//找到了 直接返回節(jié)點(diǎn) { return root; } BTNode* leftRet = BinaryTreeFind(root->left, x); if (leftRet) { return leftRet; //如果再左子樹(shù)找到,直接返回,無(wú)需遞歸到右子樹(shù) } BTNode* rightRet = BinaryTreeFind(root->right, x); if (rightRet) { return rightRet; } return NULL; //如果都沒(méi)找到,就直接返回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); // 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeSize(BTNode* root); // 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLeafSize(BTNode* root); // 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉樹(shù)查找值為x的節(jié)點(diǎn) BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉樹(shù)前序遍歷 void BinaryTreePrevOrder(BTNode* root); // 二叉樹(shù)中序遍歷 void BinaryTreeInOrder(BTNode* root); // 二叉樹(shù)后序遍歷 void BinaryTreePostOrder(BTNode* root); //二叉樹(shù)深度/高度 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; } // 二叉樹(shù)前序遍歷 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return ; } printf("%c ", root->data); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); } // 二叉樹(shù)中序遍歷 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return ; } BinaryTreePrevOrder(root->left); printf("%c ", root->data); BinaryTreePrevOrder(root->right); } // 二叉樹(shù)后序遍歷 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return ; } BinaryTreePostOrder(root->left); BinaryTreePostOrder(root->right); printf("%c ", root->data); } // 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù) int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } // 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(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); } // 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(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); } // 二叉樹(shù)查找值為x的節(jié)點(diǎn) 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; } // 二叉樹(shù)銷(xiāo)毀 void BinaryTreeDestory(BTNode** root) { if (*root) { BinaryTreeDestory(&(*root)->left); BinaryTreeDestory(&(*root)->right); free(*root); *root = NULL; } } //二叉樹(shù)深度/高度 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語(yǔ)言 鏈?zhǔn)蕉鏄?shù)結(jié)構(gòu)詳解原理的文章就介紹到這了,更多相關(guān)C語(yǔ)言 鏈?zhǔn)蕉鏄?shù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++ 隨機(jī)數(shù)與隨機(jī)種子數(shù)的實(shí)例
這篇文章主要介紹了C++ 隨機(jī)數(shù)與隨機(jī)種子數(shù)的實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-07-07C++超詳細(xì)講解貪心策略的設(shè)計(jì)及解決會(huì)場(chǎng)安排問(wèn)題
為了更好的應(yīng)對(duì)《算法設(shè)計(jì)與分析》這門(mén)課程,我把書(shū)上以及老師講過(guò)的案例都詳細(xì)的做一個(gè)重現(xiàn)及解剖,讓你熟記每一個(gè)潛在的考點(diǎn),希望能給大家?guī)椭?/div> 2022-05-05深入解析設(shè)計(jì)模式中的適配器模式在C++中的運(yùn)用
這篇文章主要介紹了設(shè)計(jì)模式中的適配器模式在C++中的運(yùn)用,通常適配器模式可以細(xì)分為類(lèi)適配器和對(duì)象適配器兩種情況,需要的朋友可以參考下2016-03-03C++流程控制中用于跳轉(zhuǎn)的return和goto語(yǔ)句學(xué)習(xí)教程
這篇文章主要介紹了C++流程控制中用于跳轉(zhuǎn)的return和goto語(yǔ)句學(xué)習(xí)教程,是C++入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2016-01-01使用MySQL編程實(shí)現(xiàn)C語(yǔ)言功能強(qiáng)大化步驟示例
這篇文章主要為大家介紹了使用MySQL編程實(shí)現(xiàn)C語(yǔ)言功能強(qiáng)大化步驟示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-05-05最新評(píng)論