之前寫了好多篇文章關于數(shù)據(jù)結構的，既然講到了數(shù)據(jù)結構，那么就必須要說一下樹，樹這個數(shù)據(jù)結構使用范圍非常廣，應用前景廣闊。

關聯(lián)文章：

五分鐘搞懂什么是紅黑樹（全程圖解）

Linux 內核紅黑樹分析

這篇文章主要是講解最簡單的一個樹的構成，并用代碼實現(xiàn)。

聲明節(jié)點結構體

/*樹節(jié)點*/
typedef struct node{
int data;
struct node * left; /*節(jié)點左邊的樹枝*/
struct node * right;/*節(jié)點右邊的樹枝*/
}Node;

data 是這個節(jié)點的數(shù)據(jù)，left是這個節(jié)點指向左邊節(jié)點的指針，right 是指向右邊節(jié)點的指針。

聲明根節(jié)點結構體

/*樹根*/
typedef struct tree{
Node * root;
}Tree;

根節(jié)點也是一個節(jié)點，只不過這個節(jié)點代表了這棵樹，這個節(jié)點存在，就代表這棵樹沒有死。

定義一個根節(jié)點

Tree tree;
tree.root = NULL;/*創(chuàng)建一個空樹*/

像節(jié)點插入一個數(shù)據(jù)

我們現(xiàn)在模擬一下，插入一個數(shù)據(jù) 5

/*插入函數(shù) 向一個樹里面插入數(shù)據(jù)*/
void insert(Tree* tree, int value)
{
/*創(chuàng)建一個節(jié)點*/
Node* node=(Node*)malloc(sizeof(Node));
node->data = value;
node->left = NULL;
node->right = NULL;

/*判斷樹是不是空樹*/
if (tree->root == NULL)
{
tree->root = node;
}
//.......
}

我們會先判斷 這個樹是不是空的，如果是空的，就把這樹根指向這個 node 節(jié)點。

我們再插入一個數(shù)據(jù) 4

因為 4 小于 5，所以我們需要把 4插入到 5 的左邊節(jié)點去。

insert(&tree, temp);

所以就變成這樣

我們再插入一個數(shù)據(jù) 3

因為 3 小于 4，那我們就再插入到4的left節(jié)點。

如果我們再插入一個 5呢？

大于等于 當前節(jié)點的，都進入right節(jié)點，所以，插入 5 會變成這樣。

遍歷一棵樹

遍歷一棵樹的方法有很多，前序遍歷，中序遍歷，后序遍歷，我這里就不說了，無非就是遞歸判斷節(jié)點是否為空，我這里使用的是中序遍歷。

/*
遍歷一整顆樹
中序遍歷:先左后根再右
*/
void traverse(Node* node)
{
if(node != NULL)
{
traverse(node->left);
printf("%d ",node->data);
traverse(node->right);
}
}

traverse(node->left); 遞歸掃描所有的左子樹節(jié)點 traverse(node->right); 遞歸掃描所有的右子樹節(jié)點

銷毀一棵樹

既然我們是通過 malloc 來創(chuàng)建一棵樹的，那么使用完后，肯定需要釋放內存，要不然內存就會一直消耗占用。

/*銷毀一棵樹*/
void distory_tree(Node* node)
{

if(node != NULL)
{
distory_tree(node->left);
distory_tree(node->right);
printf("free node:%d\n",node->data);
free(node);
node = NULL;
}
}

使用遞歸很爽啊，一直使用一直爽啊。哈哈，那就一直使用遞歸好了。

完整代碼

#include "stdio.h"
#include "stdlib.h"

/*樹節(jié)點*/
typedef struct node{
int data;
struct node * left; /*節(jié)點左邊的樹枝*/
struct node * right;/*節(jié)點右邊的樹枝*/
}Node;

/*樹根*/
typedef struct tree{
Node * root;
}Tree;

/*插入函數(shù) 向一個樹里面插入數(shù)據(jù)*/
void insert(Tree* tree, int value)
{
/*創(chuàng)建一個節(jié)點*/
Node* node=(Node*)malloc(sizeof(Node));
node->data = value;
node->left = NULL;
node->right = NULL;

/*判斷樹是不是空樹*/
if (tree->root == NULL)
{
tree->root = node;
}
else /*不是空樹*/
{
Node* temp = tree->root;/*從樹根開始*/
while (temp != NULL)
{
if(value < temp->data)/*小于就進左兒子*/
{
if(temp->left == NULL)
{
temp->left = node;
return;
}
else /*繼續(xù)判斷*/
{
temp = temp->left;
}
}
else /*否則進右兒子*/
{

if(temp->right == NULL)
{
temp->right = node;
return;
}
else /*繼續(xù)判斷*/
{
temp = temp->right;
}
}
}
}
}

/*
遍歷一整顆樹
中序遍歷:先左后根再右
*/
void traverse(Node* node)
{
if(node != NULL)
{
traverse(node->left);
printf("%d ",node->data);
traverse(node->right);
}
}

/*銷毀一棵樹*/
void distory_tree(Node* node)
{

if(node != NULL)
{
distory_tree(node->left);
distory_tree(node->right);
printf("free node:%d\n",node->data);
free(node);
node = NULL;
}
}

/*主函數(shù)*/
int main()
{
int i = 0;
Tree tree;
tree.root = NULL;/*創(chuàng)建一個空樹*/
int n;
printf("input total num:\n");
/*輸入n個數(shù)并創(chuàng)建這個樹*/
scanf("%d",&n);
for(i = 0; i < n; i++)
{
int temp;
scanf("%d",&temp);
insert(&tree, temp);
}
/*遍歷整個樹*/
traverse(tree.root);

/*銷毀一棵樹*/
distory_tree(tree.root);
return 0;
}

總結

數(shù)據(jù)結構里的樹是一個難點和重點，變化也非常多，我們安卓系統(tǒng)里面的跨進程間通信，使用的binder，底層就是有使用到紅黑樹，大家如果通過這個小例子知道樹這個概念，以后遇到就不至于一愣一愣的。

好吧，就說這么多，文章有問題的，歡迎批評指正，我們要在批評與指正中成長，覺得不錯的，感謝轉發(fā)和再看。

共勉~

—————END—————

掃碼或長按關注
回復「?加群?」進入技術群聊

總結

以上是生活随笔為你收集整理的C语言实现树，你一定看得懂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。