C語言 鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)詳解原理
更新時(shí)間：2021年11月17日 11:43:32 作者：、薛定諤的貓～
二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址
前言
二叉樹不同于順序表，一顆普通的二叉樹是沒有增刪改查的意義。普通的二叉樹用來存儲(chǔ)數(shù)據(jù)是不方便的。但是二叉樹的一些基本實(shí)現(xiàn)結(jié)構(gòu)，例如前序遍歷，中序遍歷。。。等等都是對(duì)我們學(xué)習(xí)更深層次的二叉樹打下夯實(shí)的基礎(chǔ)。
二叉樹節(jié)點(diǎn)聲明
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
二叉樹的遍歷
二叉樹的遍歷，是學(xué)習(xí)二叉樹結(jié)構(gòu)的重要部分。二叉樹的遍歷主要分為三種：1.前序遍歷 2.中序遍歷 3.后序遍歷。首先我們要知道一顆二叉樹分為根，左子樹，右子樹。而三種遍歷方式也是圍繞著根來實(shí)現(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.前序遍歷
前序遍歷的順序?yàn)?根 左子樹 右子樹 顧名思義就是先訪問根節(jié)點(diǎn)再訪問左節(jié)點(diǎn)最后訪問右節(jié)點(diǎn)。
按照前序遍歷，則上圖的遍歷順序?yàn)椋篈 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é)點(diǎn)
BinaryTreePrevOrder(root->left);//遞歸到左子樹
BinaryTreePrevOrder(root->right);//遞歸到右子樹
}
2.中序遍歷
中序遍歷的順序?yàn)?左子樹 根 右 顧名思義就是先訪問左節(jié)點(diǎn)再訪問根節(jié)點(diǎn)最后訪問右節(jié)點(diǎn)。
按照中序遍歷，則上圖的遍歷順序?yàn)椋篘ULL 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é)點(diǎn)
BinaryTreePrevOrder(root->right);//遞歸到右子樹
}
3.后序遍歷
后序遍歷的順序?yàn)?左子樹 右子樹 根 顧名思義就是先訪問左節(jié)點(diǎn)，再訪問右節(jié)點(diǎn)，最后訪問根。
按照后序遍歷，則上圖的遍歷順序?yàn)椋篘ULL 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é)點(diǎn)
}
二叉樹節(jié)點(diǎn)的個(gè)數(shù)
求二叉樹節(jié)點(diǎn)的個(gè)數(shù)與上述遍歷類似，都是通過遞歸函數(shù)來實(shí)現(xiàn)。一顆二叉樹的節(jié)點(diǎn)個(gè)數(shù)主要以三個(gè)部分構(gòu)成：根節(jié)點(diǎn)+左子樹的節(jié)點(diǎn)個(gè)數(shù)+右子樹的節(jié)點(diǎn)個(gè)數(shù)。知道這個(gè)公式我們就可以實(shí)現(xiàn)代碼
// 二叉樹節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)//如果為空返回零
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
二叉樹葉子節(jié)點(diǎn)的個(gè)數(shù)
葉子節(jié)點(diǎn)的左右子樹都為空，知道這個(gè)，我們只需稍微改動(dòng)上述代碼即可
// 二叉樹葉子節(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);
}
二叉樹第K層節(jié)點(diǎn)個(gè)數(shù)
如果指定一顆二叉樹，求它第K層節(jié)點(diǎn)個(gè)數(shù)，也可以采用遞歸的思想，當(dāng)給定的K為零的時(shí)候此時(shí)就是求根節(jié)點(diǎn)的個(gè)數(shù)，顯而易見就是返回1；而K不為零時(shí)，我們可以求root左右子樹K-1層的節(jié)點(diǎn)數(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);
}
二叉樹的高度/深度
二叉樹的高度就是指二叉樹節(jié)點(diǎn)層次的最大值，也就是左右子樹最大高度+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é)點(diǎn)
// 二叉樹查找值為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; //如果再左子樹找到，直接返回，無需遞歸到右子樹
}
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é)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節(jié)點(diǎn)
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é)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉樹葉子節(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);
}
// 二叉樹第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);
}
// 二叉樹查找值為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;
}
// 二叉樹銷毀
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)詳解原理的文章就介紹到這了,更多相關(guān)C語言 鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Qt Design Studio創(chuàng)建工程的實(shí)現(xiàn)方法
Qt Design Studio它允許設(shè)計(jì)人員和開發(fā)人員使用通用的設(shè)計(jì)、開發(fā)、分析和調(diào)試工具在不同的開發(fā)平臺(tái)上共享一個(gè)項(xiàng)目，本文主要介紹了Qt Design Studio創(chuàng)建工程的實(shí)現(xiàn)方法，具有一定的參考價(jià)值，感興趣的可以了解一下2022-05-05
引用是C++引入的新語言特性，是C++常用的一個(gè)重要內(nèi)容之一。在工作中發(fā)現(xiàn)，許多人使用它僅僅是想當(dāng)然，在某些微妙的場(chǎng)合，很容易出錯(cuò)，究其原由，大多因?yàn)闆]有搞清本源。在本篇中將對(duì)引用進(jìn)行詳細(xì)討論，希望對(duì)大家更好地理解和使用引用起到拋磚引玉的作用2021-06-06
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)三子棋游戲的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
C語言實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容的string
最近工作中使用C語言，但又苦于沒有高效的字符串實(shí)現(xiàn)，字符串的拼接和裁剪都很麻煩，而且每個(gè)字符串都需要申請(qǐng)內(nèi)存，內(nèi)存的申請(qǐng)和釋放也很容易出bug，怎么高效的實(shí)現(xiàn)一個(gè)不需要處理內(nèi)存問題并且可以動(dòng)態(tài)擴(kuò)容進(jìn)行拼接和裁剪的string呢？本文就來詳細(xì)講講2023-04-04
C語言控制臺(tái)實(shí)現(xiàn)字符飛機(jī)大戰(zhàn)
這篇文章主要為大家詳細(xì)介紹了C語言控制臺(tái)實(shí)現(xiàn)字符飛機(jī)大戰(zhàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡(jiǎn)易井字棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-04-04
這篇文章主要為大家詳細(xì)介紹了QT實(shí)現(xiàn)多文件拖拽獲取路徑的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了c/c++ 內(nèi)存對(duì)齊，有需要的朋友可以參考一下2014-01-01
C++棧(stack)的模板類實(shí)現(xiàn)代碼
這篇文章主要為大家詳細(xì)介紹了C++棧(stack)的模板類實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-06-06
這篇文章主要介紹了使用emacs編寫C語言教程,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07