數(shù)據(jù)結(jié)構(gòu)之二叉樹

樹（tree）是包含n（n>0）個結(jié)點的有窮集，其中：

1.每個元素稱為結(jié)點（node）；

2.有一個特定的結(jié)點被稱為根結(jié)點或樹根（root）。

3.除根結(jié)點之外的其余數(shù)據(jù)元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。

樹也可以這樣定義：

樹是由根結(jié)點和若干顆子樹構(gòu)成的。樹是由一個集合以及在該集合上定義的一種關(guān)系構(gòu)成的。集合中的元素稱為樹的結(jié)點，所定義的關(guān)系稱為父子關(guān)系。父子關(guān)系在樹的結(jié)點之間建立了一個層次結(jié)構(gòu)。在這種層次結(jié)構(gòu)中有一個結(jié)點具有特殊的地位，這個結(jié)點稱為該樹的根結(jié)點，或稱為樹根。

我們可以形式地給出樹的遞歸定義如下:

單個結(jié)點是一棵樹，樹根就是該結(jié)點本身。

設T1,T2,..,Tk是樹，它們的根結(jié)點分別為n1,n2,..,nk。用一個新結(jié)點n作為n1,n2,..,nk的父親，則得到一棵新樹，結(jié)點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結(jié)點，它們都是結(jié)點n的子結(jié)點。我們還稱T1,T2,..,Tk為結(jié)點n的子樹。

空集合也是樹，稱為空樹?？諛渲袥]有結(jié)點。

那么常見樹的種類有：滿二叉樹，完全二叉樹,二叉樹,紅黑樹,無序樹，哈夫曼樹等等。今天我們主要是來了解二叉樹

   處理(二叉樹)
   {
       if(二叉樹為空) 直接處理;
       else
       {
           處理根節(jié)點;
           處理左子樹;=> 遞歸
           處理右子樹;=> 遞歸
       }
   }

typedef struct Node
   {
       int data;//數(shù)據(jù)內(nèi)容
       struct Node* left;//指向左子樹
       struct Node* right;//指向右子樹
   }Node;

遍歷方式

(1)先序遍歷 => 根   左子樹   右子樹

(2)中序遍歷 => 左子樹  根  右子樹

(3)后序遍歷 => 左子樹  右子樹  根

有序二叉樹

左子樹節(jié)點 <= 根節(jié)點  <= 右子樹節(jié)點

主要搜索和查找數(shù)據(jù)的功能中

接下來我們來看看二叉樹的各類操作的實現(xiàn):

//實現(xiàn)有序二叉樹的各種操作
#include <stdio.h>
#include <stdlib.h>
 
//定義節(jié)點的數(shù)據(jù)類型
typedef struct Node
{
	int data;//存儲數(shù)據(jù)內(nèi)容
	struct Node* left;//左子樹的地址
	struct Node* right;//右子樹的地址
}Node;
 
//定義有序二叉樹的數(shù)據(jù)類型
typedef struct
{
	Node* root;//記錄根節(jié)點的地址
	int cnt;//記錄節(jié)點的個數(shù)
}Tree;
 
//實現(xiàn)向有序二叉樹中插入新節(jié)點的操作
void insert_data(Tree* pt,int data);
//插入新節(jié)點的遞歸函數(shù)
void insert(Node** pRoot,Node* pn);
//采用中序遍歷方法進行遍歷
void travel_data(Tree* pt);
//遍歷的遞歸函數(shù)
void travel(Node* pRoot);
//實現(xiàn)創(chuàng)建新節(jié)點
Node* create_node(int data);
//實現(xiàn)清空樹中的所有節(jié)點
void clear_data(Tree* pt);
//實現(xiàn)清空的遞歸函數(shù)
void clear(Node** pRoot);
//實現(xiàn)查找一個指定的節(jié)點
Node** find_data(Tree* pt,int data);
//查找的遞歸函數(shù)
Node** find(Node** pRoot,int data);
//實現(xiàn)刪除指定的節(jié)點
void del_data(Tree* pt,int data);
//修改指定元素的操作
void modify(Tree* pt,int data,int new_data);
//判斷二叉樹是否為空
int empty(Tree* pt);
//判斷二叉樹是否為滿
int full(Tree* pt);
//計算二叉樹中節(jié)點的個數(shù)
int size(Tree* pt);
//獲取根節(jié)點的元素值
int get_root(Tree* pt);
 
int main(void)
{
	//創(chuàng)建有序二叉樹，并且進行初始化
	Tree tree;
	tree.root = NULL;
	tree.cnt = 0;
	//插入新節(jié)點，進行遍歷
	insert_data(&tree,50);
	travel_data(&tree);//50
	insert_data(&tree,70);
	travel_data(&tree);//50 70
	insert_data(&tree,20);
	travel_data(&tree);//20 50 70
	insert_data(&tree,60);
	travel_data(&tree);//20 50 60 70
	
	printf("------------------\n");
	//clear_data(&tree);
	travel_data(&tree);//20 50 60 70
	del_data(&tree,50);
	travel_data(&tree);//20 60 70
	del_data(&tree,30);//刪除失敗
	travel_data(&tree);//20 60 70
	del_data(&tree,20);
	travel_data(&tree);//60 70
 
	printf("--------------------\n");
	modify(&tree,10,20);//插入20
	travel_data(&tree);//20 60 70
	printf("二叉樹中根節(jié)點的元素是：%d\n",get_root(&tree));//70
	printf("二叉樹中節(jié)點的個數(shù)是：%d\n",size(&tree));//3
	printf("%s\n",empty(&tree)?"二叉樹為空":"二叉樹不為空");
	printf("%s\n",full(&tree)?"二叉樹已滿":"二叉樹沒有滿");
	return 0;
}
 
//修改指定元素的操作
//舊元素不存在時，直接插入新元素即可
void modify(Tree* pt,int data,int new_data)
{
	//1.刪除舊元素
	del_data(pt,data);
	//2.插入新元素
	insert_data(pt,new_data);
}
//判斷二叉樹是否為空
int empty(Tree* pt)
{
	return NULL == pt->root;
}
//判斷二叉樹是否為滿
int full(Tree* pt)
{
	return 0;
}
//計算二叉樹中節(jié)點的個數(shù)
int size(Tree* pt)
{
	return pt->cnt;
}
//獲取根節(jié)點的元素值
int get_root(Tree* pt)
{
	if(empty(pt))
	{
		return -1;//表示失敗(以后講到)
	}
	return pt->root->data;
}
 
//實現(xiàn)刪除指定的節(jié)點
void del_data(Tree* pt,int data)
{
	//1.查找目標元素所在節(jié)點的地址
	Node** pp = find_data(pt,data);
	//2.判斷查找失敗情況,不需要刪除
	if(NULL == *pp)
	{
		printf("目標元素不存在，刪除失敗\n");
		return;
	}
	//3.合并左右子樹,左子樹插入到右子樹中
	if((*pp)->left != NULL)
	{
		//左子樹不為空時，需要插入到右子樹中
		insert(&(*pp)->right,(*pp)->left);
	}
	//4.尋找指針記錄要刪除的節(jié)點地址
	Node* q = *pp;
	//5.將原來指向要刪除節(jié)點的指針 重新指向 合并之后的右子樹
	*pp = (*pp)->right;
	//6.刪除目標元素所在的節(jié)點
	free(q);
	q = NULL;
	//7.節(jié)點個數(shù)減1
	pt->cnt--;
}
 
//查找的遞歸函數(shù)
Node** find(Node** pRoot,int data)
{
	//1.判斷二叉樹是否為空，為空直接返回
	if(NULL == *pRoot)
	{
		return pRoot;//&pt->root;
	}
	//2.比較根節(jié)點元素和目標元素的大小，如果相等，直接返回
	if(data == (*pRoot)->data)
	{
		return pRoot;//&pt->root;
	}
	//3.若目標元素小于根節(jié)點元素值,左子樹查找
	else if(data < (*pRoot)->data)
	{
		return find(&(*pRoot)->left,data);
	}
	//4.若目標元素大于根節(jié)點元素,去右子樹查找
	else
	{
		return find(&(*pRoot)->right,data);
	}
}
 
//實現(xiàn)查找一個指定的節(jié)點
//返回 指向目標元素所在節(jié)點的指針 的地址
Node** find_data(Tree* pt,int data)
{
	//調(diào)用遞歸函數(shù)實現(xiàn)查找
	return find(&pt->root,data);
}
 
//實現(xiàn)清空的遞歸函數(shù)
void clear(Node** pRoot)
{
	//判斷二叉樹是否為空
	if(*pRoot != NULL)
	{
		//1.清空左子樹
		clear(&(*pRoot)->left);
		//2.清空右子樹
		clear(&(*pRoot)->right);
		//3.清空根節(jié)點
		free(*pRoot);
		*pRoot = NULL;
	}
}
 
//實現(xiàn)清空樹中的所有節(jié)點
void clear_data(Tree* pt)
{
	//調(diào)用遞歸函數(shù)實現(xiàn)清空
	clear(&pt->root);
	//二叉樹的節(jié)點個數(shù)清零
	pt->cnt = 0;
}
 
//實現(xiàn)創(chuàng)建新節(jié)點
Node* create_node(int data)
{
	Node* pn = (Node*)malloc(sizeof(Node));
	pn->data = data;
	pn->left = NULL;
	pn->right = NULL;
	return pn;
}
 
//遍歷的遞歸函數(shù)
void travel(Node* pRoot)
{
	//判斷二叉樹不為空時才需要遍歷
	if(pRoot != NULL)
	{
		//1.遍歷左子樹
		travel(pRoot->left);
		//2.遍歷根節(jié)點
		printf("%d ",pRoot->data);
		//3.遍歷右子樹
		travel(pRoot->right);
	}
}
 
//采用中序遍歷方法進行遍歷
void travel_data(Tree* pt)
{
	//調(diào)用遞歸函數(shù)進行遍歷
	travel(pt->root);
	//打印換行
	printf("\n");
}
 
//插入新節(jié)點的遞歸函數(shù)
void insert(Node** pRoot,Node* pn)
{
	//1.判斷二叉樹是否為空,如果為空則讓根節(jié)點指針直接指向新節(jié)點
	if(NULL == *pRoot)
	{
		*pRoot = pn;
		return;
	}
	//2.如果二叉樹非空,比較根節(jié)點和新節(jié)點大小
	//2.1 如果根節(jié)點大于新節(jié)點，插入左子樹
	if((*pRoot)->data > pn->data)
	{
		insert(&(*pRoot)->left,pn);
	}
	//2.2 如果根節(jié)點小于等于新節(jié)點,插入右子樹
	else
	{
		insert(&(*pRoot)->right,pn);
	}
}
 
//實現(xiàn)向有序二叉樹中插入新節(jié)點的操作
void insert_data(Tree* pt,int data)
{
	//1.創(chuàng)建新節(jié)點，進行初始化 create_node
	//Node* pn = (Node*)malloc(sizeof(Node));
	//pn->data = data;
	//pn->left = NULL;
	//pn->right = NULL;
	//2.插入新節(jié)點到二叉樹中,調(diào)用遞歸函數(shù)
	insert(&pt->root,create_node(data));
	//3.二叉樹中節(jié)點個數(shù)加1
	pt->cnt++;
}

運行結(jié)果：

往期精彩

C語言將xxx.bin文件轉(zhuǎn)為數(shù)組

開源STM32產(chǎn)品:無線點菜寶使用評測

別瞎找了，你要的C語言經(jīng)典示例都在這~

專為MCU項目開發(fā)提速的代碼框架BabyOS

若覺得本次分享的文章對您有幫助，隨手點[在看]并轉(zhuǎn)發(fā)分享，也是對我的支持。