C語言 鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)詳解原理
更新時間：2021年11月17日 11:43:32 作者：、薛定諤的貓～
二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址
前言
二叉樹不同于順序表，一顆普通的二叉樹是沒有增刪改查的意義。普通的二叉樹用來存儲數(shù)據(jù)是不方便的。但是二叉樹的一些基本實現(xiàn)結(jié)構(gòu)，例如前序遍歷，中序遍歷。。。等等都是對我們學(xué)習(xí)更深層次的二叉樹打下夯實的基礎(chǔ)。
二叉樹節(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)詳解原理的文章就介紹到這了,更多相關(guān)C語言 鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Qt Design Studio創(chuàng)建工程的實現(xiàn)方法
Qt Design Studio它允許設(shè)計人員和開發(fā)人員使用通用的設(shè)計、開發(fā)、分析和調(diào)試工具在不同的開發(fā)平臺上共享一個項目，本文主要介紹了Qt Design Studio創(chuàng)建工程的實現(xiàn)方法，具有一定的參考價值，感興趣的可以了解一下2022-05-05
引用是C++引入的新語言特性，是C++常用的一個重要內(nèi)容之一。在工作中發(fā)現(xiàn)，許多人使用它僅僅是想當(dāng)然，在某些微妙的場合，很容易出錯，究其原由，大多因為沒有搞清本源。在本篇中將對引用進行詳細討論，希望對大家更好地理解和使用引用起到拋磚引玉的作用2021-06-06
這篇文章主要為大家詳細介紹了C語言實現(xiàn)三子棋游戲的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
最近工作中使用C語言，但又苦于沒有高效的字符串實現(xiàn)，字符串的拼接和裁剪都很麻煩，而且每個字符串都需要申請內(nèi)存，內(nèi)存的申請和釋放也很容易出bug，怎么高效的實現(xiàn)一個不需要處理內(nèi)存問題并且可以動態(tài)擴容進行拼接和裁剪的string呢？本文就來詳細講講2023-04-04
這篇文章主要為大家詳細介紹了C語言控制臺實現(xiàn)字符飛機大戰(zhàn)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易井字棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-04-04
這篇文章主要為大家詳細介紹了QT實現(xiàn)多文件拖拽獲取路徑的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了c/c++ 內(nèi)存對齊，有需要的朋友可以參考一下2014-01-01
這篇文章主要為大家詳細介紹了C++棧(stack)的模板類實現(xiàn)代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-06-06
這篇文章主要介紹了使用emacs編寫C語言教程,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07