二叉排序樹(Binary Sort Tree) 又稱為二叉查找樹(Binary Search Tree) - （代碼、分析）

目錄：

    • 代碼：
    • 分析：

代碼：

BSTree.h

#ifndef _BSTREE_H_
#define _BSTREE_H_typedef void BSTree;//定義二叉樹類型
typedef void BSKey;//定義節點的鍵值類型（用于節點排序）typedef struct _tag_BSTreeNode BSTreeNode;//定義二叉樹節點類型
struct _tag_BSTreeNode
{BSKey* key;//鍵值BSTreeNode* left;//左子節點BSTreeNode* right;//右子節點
};typedef void (BSTree_Printf)(BSTreeNode*);//定義參數為一個節點指針并且無返回值的函數類型
typedef int (BSTree_Compare)(BSKey*, BSKey*);//定義參數為兩個鍵值指針并且無返回值的函數類型BSTree* BSTree_Create();//聲明創建樹函數void BSTree_Destroy(BSTree* tree);//聲明銷毀樹函數void BSTree_Clear(BSTree* tree);//聲明清空樹函數int BSTree_Insert(BSTree* tree, BSTreeNode* node, BSTree_Compare* compare);//聲明插入節點函數BSTreeNode* BSTree_Delete(BSTree* tree, BSKey* key, BSTree_Compare* compare);//聲明刪除節點函數BSTreeNode* BSTree_Get(BSTree* tree, BSKey* key, BSTree_Compare* compare);//聲明獲取節點函數BSTreeNode* BSTree_Root(BSTree* tree);//聲明獲取根節點函數int BSTree_Height(BSTree* tree);//聲明獲取樹高度函數int BSTree_Count(BSTree* tree);//聲明獲取節點數量函數int BSTree_Degree(BSTree* tree);//聲明獲取樹度數函數void BSTree_Display(BSTree* tree, BSTree_Printf* pFunc, int gap, char div);//定義統一用函數處理節點函數#endif

BSTree.c

#include <stdio.h>
#include <malloc.h>
#include "BSTree.h"typedef struct _tag_BSTree TBSTree;//定義實際使用二叉樹類型
struct _tag_BSTree
{int count;//數量BSTreeNode* root;//根節點
};
//用遞歸調用函數處理節點函數
static void recursive_display(BSTreeNode* node, BSTree_Printf* pFunc, int format, int gap, char div) // O(n)
{int i = 0;if( (node != NULL) && (pFunc != NULL) ){for(i=0; i<format; i++){printf("%c", div);}pFunc(node);printf("\n");if( (node->left != NULL) || (node->right != NULL) ){recursive_display(node->left, pFunc, format + gap, gap, div);recursive_display(node->right, pFunc, format + gap, gap, div);}}else{for(i=0; i<format; i++){printf("%c", div);}printf("\n");}
}static int recursive_count(BSTreeNode* root) //遞歸計算節點數量函數（沒使用到）
{int ret = 0;if( root != NULL ){ret = recursive_count(root->left) + 1 + recursive_count(root->right);}return ret;
}static int recursive_height(BSTreeNode* root) // 遞歸計算高度函數
{int ret = 0;if( root != NULL ){int lh = recursive_height(root->left);int rh = recursive_height(root->right);ret = ((lh > rh) ? lh : rh) + 1;}return ret;
}static int recursive_degree(BSTreeNode* root) //遞歸計算度數函數
{int ret = 0;if( root != NULL ){if( root->left != NULL ){ret++;}if( root->right != NULL ){ret++;}if( ret == 1 ){int ld = recursive_degree(root->left);int rd = recursive_degree(root->right);if( ret < ld ){ret = ld;}if( ret < rd ){ret = rd;}}}return ret;
}static int recursive_insert(BSTreeNode* root, BSTreeNode* node, BSTree_Compare* compare)
{int ret = 1;int r = compare(node->key, root->key);//1參數小于2參數返回負數，大于返回正數，等于返回0if( r == 0 )//如果兩個鍵相等插入結果等于0返回到調用函數，表示插入失敗{ret = 0;}else if( r < 0 )//如果插入節點的鍵小于當前比較的節點的鍵，表示應該是往當前比較的節點的左子節點走{if( root->left != NULL )//如果當前比較的節點的左子節點不為空{//將其左子節點作為下一個與插入節點比較的節點再調用函數進棧，是否插入成功結果返回這里ret = recursive_insert(root->left, node, compare);}else{//否則直接將插入節點作為當前比較節點的左子節點root->left = node;}}else if( r > 0 )//如果插入節點的鍵小于當前比較根節點的鍵，表示應該是往當前比較根節點的右子節點走{if( root->right != NULL )//如果當前比較的節點的右子節點不為空{//將其右子節點作為下一個與插入節點比較的節點再調用函數進棧，是否插入成功結果返回這里ret = recursive_insert(root->right, node, compare);}else{//否則直接將插入節點作為當前比較節點的右子節點root->right = node;}}return ret;//將結果返回
}static BSTreeNode* recursive_get(BSTreeNode* root, BSKey* key, BSTree_Compare* compare)//遞歸查找節點函數
{BSTreeNode* ret = NULL;if( root != NULL ){int r = compare(key, root->key);if( r == 0 ){ret = root;}else if( r < 0 ){ret = recursive_get(root->left, key, compare);}else if( r > 0 ){ret = recursive_get(root->right, key, compare);}}return ret;
}static BSTreeNode* delete_node(BSTreeNode** pRoot)//進行刪除節點函數
{BSTreeNode* ret = *pRoot;//取得要刪除節點地址if( (*pRoot)->right == NULL )//如果刪除節點的右子節點等于空{*pRoot = (*pRoot)->left;//將刪除節點的左子節點賦到本來指向刪除節點的指針}else if( (*pRoot)->left == NULL )//如果刪除節點的左子節點等于空{*pRoot = (*pRoot)->right;//將刪除節點的右子節點賦到本來指向刪除節點的指針}else//否則表示左右子節點都不為空{BSTreeNode* g = *pRoot;//取得要刪除節點地址BSTreeNode* c = (*pRoot)->left;//取得要刪除節點的左子節點地址//從刪除節點左子節點開始找出一個鍵與刪除節點鍵最接近的節點，作為刪除節點的那個位置//因為從刪除節點的左子節點開始，所以它的右子節點一直沿伸的節點的鍵是最接近刪除節點的//c用于指向作為替換到刪除節點位置的節點 g是c的父節點while( c->right != NULL )//從刪除節點的左子節點往右查找，找到右節點為空的節點{g = c;//更新位置c = c->right;//更新下一個檢測的位置}if( g != *pRoot )//g不等于刪除節點，表示找到合適的節點{//因為c要替換到刪除節點的位置，這時c節點只有左子節點（有指向或NULL）需要處理連接的，//因為c的右子節點確保為NULL了，經過上面的查找，再將c父節點的本來指向c節點的右子節點//指向c的左子節點，而且c的左子節點鍵肯定大于c的父節點所以是c的父節點的右子節點//相當替換了c節點原來的位置g->right = c->left;}else//否則表示刪除節點的左子節點就是合適替換到刪除節點位置的節點{//直接將刪除節點的左子節點等于c的左子節點，這里就只有c左子節點有指向的g->left = c->left;}c->left = (*pRoot)->left;//將刪除節點本來的左子節點部分賦給c節點左子節點c->right = (*pRoot)->right;//將刪除節點本來的右子節部分賦給c節點的右子節點*pRoot = c;//把c節點更新到原來刪除節點的指針位置}return ret;//返回刪除節點
}static BSTreeNode* recursive_delete(BSTreeNode** pRoot, BSKey* key, BSTree_Compare* compare)
{BSTreeNode* ret = NULL;if( (pRoot != NULL) && (*pRoot != NULL) )//比較節點指針地址與指向不為空{  //將當前節點與key值進行比較等于0表示找到了，小于表示應該往當前節點左子節點查找，大于往右子節點查找int r = compare(key, (*pRoot)->key);if( r == 0 )//找到后調用刪除節點函數進行刪除{//注意：pRoot不是當前節點地址，是指向要刪除節點的節點指針的地址（也就是樹的根節點指針地址或是上一個節點的左子節點指針或右子節點指針地址）ret = delete_node(pRoot);//將節點指針地址作為參數進行刪除操作}else if( r < 0 ){//將當前節點的左子節點指針地址調用函數繼續查找ret = recursive_delete(&((*pRoot)->left), key, compare);}else if( r > 0 ){//將當前節點的右子節點指針地址調用函數繼續查找ret = recursive_delete(&((*pRoot)->right), key, compare);}}return ret;
}BSTree* BSTree_Create() // 定義創建樹函數
{TBSTree* ret = (TBSTree*)malloc(sizeof(TBSTree));if( ret != NULL ){ret->count = 0;ret->root = NULL;}return ret;
}void BSTree_Destroy(BSTree* tree) // 定義銷毀樹函數
{free(tree);
}void BSTree_Clear(BSTree* tree) // 定義清空樹函數
{TBSTree* btree = (TBSTree*)tree;if( btree != NULL ){btree->count = 0;btree->root = NULL;}
}int BSTree_Insert(BSTree* tree, BSTreeNode* node, BSTree_Compare* compare) //定義插入節點函數
{TBSTree* btree = (TBSTree*)tree;//取得樹int ret = (btree != NULL) && (node != NULL) && (compare != NULL);//判斷參數不為空if( ret ){node->left = NULL;//將插入節點左子節點設空node->right = NULL;//將插入節點右子節點設空if( btree->root == NULL )//如果根節點等于空表示是第一個節點{btree->root = node;}else{//調用遞歸檢測插入位置ret = recursive_insert(btree->root, node, compare);}if( ret )//如果插入成功{btree->count++;//節點數量增加}}return ret;
}BSTreeNode* BSTree_Delete(BSTree* tree, BSKey* key, BSTree_Compare* compare)//定義刪除節點函數
{TBSTree* btree = (TBSTree*)tree;//取得樹BSTreeNode* ret = NULL; if( (btree != NULL) && (key != NULL) && (compare != NULL) )//判斷參數不為空{ret = recursive_delete(&btree->root, key, compare);if( ret != NULL ){btree->count--;}}return ret;
}BSTreeNode* BSTree_Get(BSTree* tree, BSKey* key, BSTree_Compare* compare)//定義獲取節點函數
{TBSTree* btree = (TBSTree*)tree;//取得樹BSTreeNode* ret = NULL; if( (btree != NULL) && (key != NULL) && (compare != NULL) )//判斷參數不為空{ret = recursive_get(btree->root, key, compare);//調用遞歸查找 }return ret;//返回獲取節點
}BSTreeNode* BSTree_Root(BSTree* tree) // 定義獲取根節點函數
{TBSTree* btree = (TBSTree*)tree;BSTreeNode* ret = NULL;if( btree != NULL ){ret = btree->root;}return ret;
}int BSTree_Height(BSTree* tree) // 定義獲取樹高度函數
{TBSTree* btree = (TBSTree*)tree;int ret = 0;if( btree != NULL ){ret = recursive_height(btree->root);//調用遞歸計算高度函數}return ret;
}int BSTree_Count(BSTree* tree) // 定義獲取節點數量函數
{TBSTree* btree = (TBSTree*)tree;int ret = 0;if( btree != NULL ){ret = btree->count;}return ret;
}int BSTree_Degree(BSTree* tree) // 定義獲取樹度數函數
{TBSTree* btree = (TBSTree*)tree;int ret = 0;if( btree != NULL ){ret = recursive_degree(btree->root);//調用遞歸計算度數函數}return ret;
}void BSTree_Display(BSTree* tree, BSTree_Printf* pFunc, int gap, char div) //定義用統一函數處理節點函數
{TBSTree* btree = (TBSTree*)tree;if( btree != NULL ){recursive_display(btree->root, pFunc, 0, gap, div);}
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "BSTree.h"struct Node
{BSTreeNode header;char v;
};void printf_data(BSTreeNode* node)
{if( node != NULL ){printf("%c", ((struct Node*)node)->v);}
}int compare_key(BSKey* k1, BSKey* k2)
{return (int)k1 - (int)k2;
}int main(int argc, char *argv[])
{BSTree* tree = BSTree_Create();struct Node n1 = {{(BSKey*)1, NULL, NULL}, 'A'};struct Node n2 = {{(BSKey*)2, NULL, NULL}, 'B'};struct Node n3 = {{(BSKey*)3, NULL, NULL}, 'C'};struct Node n4 = {{(BSKey*)4, NULL, NULL}, 'D'};struct Node n5 = {{(BSKey*)5, NULL, NULL}, 'E'};struct Node n6 = {{(BSKey*)6, NULL, NULL}, 'F'};BSTree_Insert(tree, (BSTreeNode*)&n4, compare_key);BSTree_Insert(tree, (BSTreeNode*)&n1, compare_key);BSTree_Insert(tree, (BSTreeNode*)&n3, compare_key);BSTree_Insert(tree, (BSTreeNode*)&n6, compare_key);BSTree_Insert(tree, (BSTreeNode*)&n2, compare_key);BSTree_Insert(tree, (BSTreeNode*)&n5, compare_key);printf("Height: %d\n", BSTree_Height(tree));printf("Degree: %d\n", BSTree_Degree(tree));printf("Count: %d\n", BSTree_Count(tree));printf("Search Key 5: %c\n", ((struct Node*)BSTree_Get(tree, (BSKey*)5, compare_key))->v);printf("Full Tree: \n");BSTree_Display(tree, printf_data, 4, '-');BSTree_Delete(tree, (BSKey*)4, compare_key);printf("After Delete Key 4: \n");printf("Height: %d\n", BSTree_Height(tree));printf("Degree: %d\n", BSTree_Degree(tree));printf("Count: %d\n", BSTree_Count(tree));printf("Full Tree: \n");BSTree_Display(tree, printf_data, 4, '-');BSTree_Clear(tree);printf("After Clear: \n");printf("Height: %d\n", BSTree_Height(tree));printf("Degree: %d\n", BSTree_Degree(tree));printf("Count: %d\n", BSTree_Count(tree));BSTree_Display(tree, printf_data, 4, '-');BSTree_Destroy(tree);getchar();return 0;
}

分析：

在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/379133.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/379133.shtml
英文地址，請注明出處：http://en.pswp.cn/news/379133.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

springboot tomcat默認線程數_記一次JAVA線程池的錯誤用法

springboot tomcat默認線程數_記一次JAVA線程池的錯誤用法

最近項目一個項目要結項了&#xff0c;但客戶要求 TPS 能達到上千&#xff0c;而用我寫的代碼再怎么弄成只能達到 30 的 TPS&#xff0c;然后我又將代碼中能緩存的都緩存了&#xff0c;能拆分的也都拆分了&#xff0c;拆分時用的線程池來實現的&#xff1b;其實現的代碼主要為…
閱讀更多...
引以為鑒-ARM開發板連線注意事項

引以為鑒-ARM開發板連線注意事項

前些日子把實驗室的三臺機子放到一個工位上&#xff0c;非常擁擠&#xff0c;做實驗也很不方便。因此&#xff0c;想把ARM開發板的環境重新搭建到自己的電腦上。說完就做&#xff0c;上午就開始忙活起來。把開發板上的USB線、串口線、JTAT接口、還有電源線一一插好。接著就開始…
閱讀更多...
CString 類型和引用

CString 類型和引用

怎么理解CString & 類型&#xff1f;在函數參數表中&#xff0c;列了一項是此類型&#xff0c;據說是引用。可以給個具體方法&#xff0c;示例么&#xff1f; 由于子程序調用是棧傳遞參數&#xff0c;因此對參數的修改不會改變調用者傳入的參數的值。如果要改變調用者的參數…
閱讀更多...
Java IdentityHashMap putAll（）方法與示例

Java IdentityHashMap putAll（）方法與示例

IdentityHashMap類putAll()方法 (IdentityHashMap Class putAll() method) putAll() method is available in java.util package. putAll()方法在java.util包中可用。 putAll() method is used to copy all of the entry (key-value pairs) that exists from the given map (m)…
閱讀更多...
Python---實驗八

Python---實驗八

1&#xff0c;現在有一份‘邀請函.txt’的空白文件&#xff0c;請在同級目錄下編寫一段代碼&#xff0c;寫入內容‘誠摯邀請您來參加本次宴會’。 with open(fG:\study\Python\邀請函.txt,modew,encodingutf-8) as y:y.write(誠摯邀請您來參加本次宴會)效果圖如下&#xff1a;…
閱讀更多...
哈希表 - （代碼、分析 ）

哈希表 - （代碼、分析 ）

目錄&#xff1a;代碼&#xff1a;分析&#xff1a;代碼&#xff1a; BSTree.h BSTree.c 二叉排序樹(Binary Sort Tree) 又稱為二叉查找樹(Binary Search Tree) Hash.h #ifndef _HASH_H_ #define _HASH_H_typedef void Hash;//定義哈希表類型 typedef void HashKey;//定義哈…
閱讀更多...
scala spark 數據對比_IT大牛耗時三個月總結出大數據領域學習路線，網友評論：炸鍋了...

scala spark 數據對比_IT大牛耗時三個月總結出大數據領域學習路線，網友評論：炸鍋了...

大數據不是某個專業或一門編程語言&#xff0c;實際上它是一系列技術的組合運用。有人通過下方的等式給出了大數據的定義。大數據 編程技巧 數據結構和算法 分析能力 數據庫技能 數學 機器學習 NLP OS 密碼學 并行編程雖然這個等式看起來很長&#xff0c;需要學習的東…
閱讀更多...
Java IdentityHashMap equals（）方法與示例

Java IdentityHashMap equals（）方法與示例

IdentityHashMap類equals()方法 (IdentityHashMap Class equals() method) equals() method is available in java.util package. equals()方法在java.util包中可用。 equals() method is used to check whether this IdentityHashMap object and the given object (ob) are eq…
閱讀更多...
jQuery中關于Ajax的詳解

jQuery中關于Ajax的詳解

本文介紹如何使用jquery實現Ajax功能. 用于發送Ajax請求的相關函數如load, get, getJSON和post這些漸變Ajax方法, 對于核心的ajax 方法沒有過多介紹, 主要是通過配置復雜的參數實現完全控制Ajax請求。 Ajax讓用戶頁面豐富起來, 增強用戶體驗. Ajax是所有Web開發的必修課. 雖然A…
閱讀更多...
Python---實驗九作業

Python---實驗九作業

1&#xff0c;使用tkinter實現計算器程序。實現效果如下&#xff1a; from tkinter import * from tkinter.ttk import *def frame(master):"""將共同的屬性作為默認值, 以簡化Frame創建過程"""w Frame(master)w.pack(sideTOP, expandYES, fill…
閱讀更多...
分析FLV文件分析和解析器的開源代碼

分析FLV文件分析和解析器的開源代碼

分析一下GitHub上一份FLV文件分析和解析器的開源代碼 GitHub源碼地址&#xff1a;功能強大的 FLV 文件分析和解析器 &#xff1a;可以將flv文件的視頻tag中的h264類型數據和音頻tag中的aac類型數據導出 &#xff08;只限h264和aac&#xff09; (這個代碼不太適合用于大文件的分…
閱讀更多...
用pv操作描述如下前驅圖_LinkedList實現分析（二）——常用操作

用pv操作描述如下前驅圖_LinkedList實現分析（二）——常用操作

上一篇文章LinkedList實現分析(一)——LinkedList初探與對象創建介紹了LinkedList中的一些重要屬性和構造方法&#xff0c;下面我們將詳細介紹一下LinkedList提高的常用方法的實現原理元素添加###add(E e)方法往LinkedList添加元素&#xff0c;LinkedList提供了多重方式&#x…
閱讀更多...
C++多重繼承與虛基類及與.NET的比較

C++多重繼承與虛基類及與.NET的比較

多重繼承前面我們介紹的派生類只有一個基類&#xff0c;稱為單基派生或單一繼承。在實際運用中&#xff0c;我們經常需要派生類同時具有多個基類&#xff0c;這種方法稱為多基派生或多重繼承。2.1 多重繼承的聲明&#xff1a;在 C 中&#xff0c;聲明具有兩個以上基類的派生類與…
閱讀更多...
Javascript的IE和Firefox兼容性匯編

Javascript的IE和Firefox兼容性匯編

window.event現有問題&#xff1a;使用 window.event 無法在 FF 上運行解決方法&#xff1a;FF 的 event 只能在事件發生的現場使用&#xff0c;此問題暫無法解決。可以這樣變通&#xff1a;原代碼(可在IE中運行)&#xff1a;<input type"button" name"someB…
閱讀更多...
Java Double類compareTo（）方法與示例

Java Double類compareTo（）方法與示例

雙類compareTo()方法 (Double class compareTo() method) compareTo() method is available in java.lang package. compareTo()方法在java.lang包中可用。 compareTo() method is used to check equality or inequality for this Double-object against the given Double-obje…
閱讀更多...
平院實訓門禁系統導入

平院實訓門禁系統導入

這是我的配置&#xff08;如果是Win10最好每一步都管理員身份運行&#xff09; win7 SQLServer2008 VS2012 切記&#xff1a;注意&#xff1a;當你SQLserver創建數據庫和VS連接數據庫的時候得用同一種方式&#xff0c;要么都用window&#xff08;主機名&#xff09;&#xff0…
閱讀更多...
ffmpeg 解碼音頻（aac、mp3）輸出pcm文件

ffmpeg 解碼音頻（aac、mp3）輸出pcm文件

ffmpeg 解碼音頻&#xff08;aac、mp3&#xff09;輸出pcm文件 播放pcm可以參考&#xff1a; ffplay -ar 48000 -ac 2 -f f32le out.pcm main.c #include <stdio.h> #include <stdlib.h> #include <string.h>#include <libavutil/frame.h> #include …
閱讀更多...
Jquery getJSON（）

Jquery getJSON（）

getJSON與aspx 準備工作 Customer類 public class Customer{public int Unid { get; set; }public string CustomerName { get; set; }public string Memo { get; set; }public string Other { get; set; }}&#xff08;一&#xff09;ashx Customer customer new Customer { …
閱讀更多...
北京中信銀行總行地址_中信銀行拉薩分行舉行“存款保險標識”啟用和存款保險條例宣傳活動...

北京中信銀行總行地址_中信銀行拉薩分行舉行“存款保險標識”啟用和存款保險條例宣傳活動...

11月NOV中信銀行拉薩分行舉行“存款保險標識”啟用和《存款保險條例》宣傳活動揭牌啟用儀式111月Jul根據人民銀行和總行關于“存款保險標識”啟用工作相關要求&#xff0c;分行行領導高度重視“存款保險標識”啟用和《存款保險條例》宣傳活動工作&#xff0c;按照統一工作部署、…
閱讀更多...
Java ClassLoader getPackage（）方法與示例

Java ClassLoader getPackage（）方法與示例

ClassLoader類的getPackage()方法 (ClassLoader Class getPackage() method) getPackage() method is available in java.lang package. getPackage()方法在java.lang包中可用。 getPackage() method is used to return the package that has been defined in ClassLoader or t…
閱讀更多...
最新文章

Copyright @ 2022~2023