欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言 鏈?zhǔn)蕉鏄?shù)結(jié)構(gòu)詳解原理

 更新時(shí)間：2021年11月17日 11:43:32   作者：、薛定諤的貓～  
二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈來(lái)指示元素的邏輯關(guān)系。通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址

前言

二叉樹(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++ Effective詳解

    C++ Effective詳解

    下面小編就為大家?guī)?lái)一篇C++ Effective的文章。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2021-08-08
  • C++ 隨機(jī)數(shù)與隨機(jī)種子數(shù)的實(shí)例

    C++ 隨機(jī)數(shù)與隨機(jī)種子數(shù)的實(shí)例

    這篇文章主要介紹了C++ 隨機(jī)數(shù)與隨機(jī)種子數(shù)的實(shí)例的相關(guān)資料,需要的朋友可以參考下
    2017-07-07
  • C語(yǔ)言面試C++二維數(shù)組中的查找示例

    C語(yǔ)言面試C++二維數(shù)組中的查找示例

    這篇文章主要介紹了C語(yǔ)言面試C++二維數(shù)組中的查找示例，文中給出基本能拿下面試官的操作示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助
    2021-09-09
  • C++語(yǔ)言基礎(chǔ) 命名空間

    C++語(yǔ)言基礎(chǔ) 命名空間

    一個(gè)中大型軟件往往由多名程序員共同開(kāi)發(fā)，會(huì)使用大量的變量和函數(shù)，當(dāng)有兩個(gè)人都同時(shí)定義了一個(gè)名字相同的全局變量或函數(shù)的時(shí)候，若是把他們的代碼整合在一塊編譯，此時(shí)編譯器就會(huì)提示變量或函數(shù)重復(fù)定義，C++為了解決這個(gè)問(wèn)題，便引用了命名空間(namespace)的概念
    2020-01-01
  • C++超詳細(xì)講解貪心策略的設(shè)計(jì)及解決會(huì)場(chǎng)安排問(wèn)題

    C++超詳細(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)用

    這篇文章主要介紹了設(shè)計(jì)模式中的適配器模式在C++中的運(yùn)用,通常適配器模式可以細(xì)分為類(lèi)適配器和對(duì)象適配器兩種情況,需要的朋友可以參考下
    2016-03-03
  • C++流程控制中用于跳轉(zhuǎn)的return和goto語(yǔ)句學(xué)習(xí)教程

    C++流程控制中用于跳轉(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
  • 教你用Matlab制作黃金礦工小游戲

    教你用Matlab制作黃金礦工小游戲

    黃金礦工作為經(jīng)典的單機(jī)小游戲，一直深受大家的喜愛(ài)。本文將用Matlab制作這一款經(jīng)典的游戲，文中的實(shí)現(xiàn)步驟講解詳細(xì)，感興趣的可以了解一下
    2022-03-03
  • 詳解C++14中返回類(lèi)型推導(dǎo)的使用

    詳解C++14中返回類(lèi)型推導(dǎo)的使用

    這篇文章主要為大家詳細(xì)介紹了C++14中返回類(lèi)型推導(dǎo)的使用，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-07-07
  • 使用MySQL編程實(shí)現(xiàn)C語(yǔ)言功能強(qiáng)大化步驟示例

    使用MySQL編程實(shí)現(xiàn)C語(yǔ)言功能強(qiáng)大化步驟示例

    這篇文章主要為大家介紹了使用MySQL編程實(shí)現(xiàn)C語(yǔ)言功能強(qiáng)大化步驟示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
    2023-05-05

最新評(píng)論