數據結構之樹的一些基本操作

樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關系構成的。集合中的元素稱為樹的結點，所定義的關系稱為父子關系。父子關系在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹根。
頭文件 tree.h

#ifndef __TREE_H__
#define __TREE_H__#include "error.h"struct _treeNode;                   // 結構體聲明// 孩子結點鏈表的類型
typedef struct _childNode
{struct _treeNode * childNode;struct _childNode* next;        // 指向孩子結點鏈表下一個元素
}ChildNode;// 樹節點類型
typedef char TreeData;
typedef struct _treeNode
{TreeData data;struct _treeNode * parent;      // 指向父節點的指針struct _treeNode * next;        // 指向鏈表的下一個結點struct _childNode* childList;   // 孩子鏈表的頭節點int degree;                     // 結點的度
}TreeNode;typedef struct _tree
{struct _treeNode* head;         // 樹鏈表的頭節點int len;                        // 樹結點個數
}Tree;// 定義一個函數指針類型
typedef void(*TreePrint)(TreeNode *node);Tree* Create_Tree();// pos 代表要插入結點父親結點的位置
// 約定：
// 1 新插入的結點插入在當前父親結點所有孩子的右邊
// 2 根節點的位置是 0
int Insert_Tree (Tree* tree, TreeData data, int pos);// 打印樹
void Display (Tree* tree, TreePrint pFunc);// 刪除結點
int Delete (Tree* tree, int pos, TreeData *x);// 求指定位置樹結點的值
int Tree_Get (Tree* tree, int pos, TreeData *x);// 清空樹中所有的節點
int Tree_Clear (Tree* tree);// 樹的銷毀 
void Tree_Destroy   (Tree* tree);// 獲取根節點的地址
TreeNode* Tree_Root (Tree* tree);// 求樹的結點個數
int Tree_Count  (Tree* tree);// 求樹的高度
int Tree_Height (Tree* tree);// 求樹的度
int Tree_Degree (Tree* tree);// 打印
void printA (TreeNode* node);#endif  // __TREE_H__

源文件 tree.c

#include "tree.h"
#include <stdlib.h>Tree *Create_Tree()
{// 創建樹節點Tree* tree = (Tree*) malloc(sizeof(Tree)/sizeof(char));if (NULL == tree){errno = MALLOC_ERROR;return NULL;}// 給樹結點鏈表創建頭節點tree->head = (TreeNode*) malloc(sizeof(TreeNode)/sizeof(char));if (NULL == tree->head){errno = MALLOC_ERROR;free (tree);return NULL;}tree->head->parent    = NULL;tree->head->childList = NULL;tree->head->next      = NULL;   // 代表樹中沒有結點// 空樹結點為0tree->len = 0;return tree;
}int Insert_Tree (Tree* tree, TreeData data, int pos)
{if (NULL == tree || pos < 0 || pos > tree->len){errno = ERROR;return FALSE;}if (pos != 0 && tree->len == pos){errno = ERROR;return FALSE;}// 新建結點TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode)/sizeof(char));if (NULL == node){   errno = MALLOC_ERROR;return FALSE;}node->data = data;node->next = NULL;// 創建該新節點的孩子結點鏈表的頭節點node->childList = (ChildNode*) malloc(sizeof(ChildNode)/sizeof(char));if (NULL == node->childList){   errno = MALLOC_ERROR;free (node);return FALSE;}   node->childList->next      = NULL;node->childList->childNode = NULL;node->degree = 0;int i;// 找父節點TreeNode* parent = tree->head->next;     // 當前樹節點的第一個結點for (i = 0; i < pos; i++){parent = parent->next;}node->parent = parent; // 在父親結點的子結點鏈表中加入一個結點if (parent != NULL){// 創建一個孩子結點ChildNode* childnode = (ChildNode*) malloc(sizeof(ChildNode)/sizeof(char));if (NULL == childnode){errno = MALLOC_ERROR;free (node->childList);free (node);return FALSE;}childnode->childNode = node;childnode->next      = NULL;// 加入到父親結點子結點鏈表當中ChildNode* tmp = parent->childList;   // 子結點鏈表的頭節點while (tmp->next){   tmp = tmp->next;}tmp->next = childnode;parent->degree += 1;}TreeNode* tmp = tree->head;              // 樹節點鏈表的頭節點while (tmp->next){tmp = tmp->next;}tmp->next = node;tree->len += 1;return TRUE;
}// 遞歸打印結點
void r_display (TreeNode* node, int gap, TreePrint pFunc)
{if (NULL == node){return;}// 打印距離前一個結點的距離int i;for (i = 0; i < gap; i++){printf ("%c", '-');}// 打印結點自己// printf ("%c\n", node->data);pFunc (node);ChildNode* child = node->childList->next; // 該結點的第一個孩子// 打印該結點的孩子while (child){r_display (child->childNode, gap+4, pFunc);child = child->next;  // 下一個孩子}
}void Display (Tree *tree, TreePrint pFunc)
{if (NULL == tree){return;}r_display (tree->head->next, 0, pFunc);
}void r_delete (Tree *tree, TreeNode *node)
{if (NULL == tree || NULL == node)return;// 從樹鏈表中移除這個結點,找node的前一個結點TreeNode* tmp = tree->head;  // 鏈表的頭節點while (tmp->next){if (tmp->next == node){tmp->next = node->next;tree->len--;break;}tmp = tmp->next;}// 將父親結點中子結點鏈表中指向node的結點刪除TreeNode* parent = node->parent;if (NULL != parent){ChildNode* tmp = parent->childList;  // 子結點鏈表的頭節點while (tmp->next){if (tmp->next->childNode == node){ChildNode* p = tmp->next;tmp->next    = p->next;free (p);parent->degree--;break;}tmp = tmp->next;}}// 將該結點的孩子結點刪掉ChildNode* child = node->childList->next; // 子結點鏈表中的第一個結點while (child){ChildNode* pchild = child->next;r_delete (tree, child->childNode);child  = pchild;}free (node->childList);free (node);
}int Delete (Tree *tree, int pos, TreeData *x)
{if (NULL == tree || pos < 0 || pos > tree->len){errno = ERROR;return FALSE;}if (0 != pos && tree->len == pos){errno = ERROR;return FALSE;}int i;// 找結點TreeNode* current = tree->head->next;  for (i = 0; i < pos; i++){current = current->next;}*x = current->data;r_delete (tree, current);return TRUE;}int Tree_Get (Tree* tree, int pos, TreeData *x)
{if (NULL == tree || pos < 0 || pos > tree->len){errno = ERROR;return FALSE;}if (0 != pos && tree->len == pos){errno = ERROR;return FALSE;}int i;// 找結點TreeNode* current = tree->head->next;  for (i = 0; i < pos; i++){current = current->next;}*x = current->data;return TRUE;
}int Tree_Clear (Tree* tree)
{if (NULL == tree){errno = ERROR;return FALSE;}TreeData x;return Delete (tree, 0, &x);
}void Tree_Destroy (Tree* tree)
{if (NULL == tree){errno = ERROR;return;}Tree_Clear (tree);free (tree->head);free (tree);
}TreeNode* Tree_Root (Tree* tree)
{if (NULL == tree){errno = ERROR;return NULL;}return tree->head->next;
}int Tree_Count (Tree* tree)
{if (NULL == tree){errno = ERROR;return FALSE;}return tree->len;
}// 遞歸求高度
int r_height (TreeNode* node)
{if (NULL == node){return 0;}int subHeight = 0;int max       = 0;ChildNode* child = node->childList->next;while (child){subHeight = r_height (child->childNode);if (subHeight > max){max = subHeight;}child = child->next;}return max + 1;
}int Tree_Height (Tree* tree)
{if (NULL == tree){errno = ERROR;return FALSE;}int height = r_height (tree->head->next);return height;
}// 遞歸求度
int r_degree (TreeNode* node)
{if (NULL == node){return 0;}int max       = node->degree;int subDegree = 0;ChildNode* child = node->childList->next;while (child){subDegree = r_degree (child->childNode);if (subDegree > max){max = subDegree;}child = child->next;}return max;
}int Tree_Degree (Tree* tree)
{if (NULL == tree){errno = ERROR;return FALSE;}int degree = r_degree (tree->head->next);return degree;
}void printA (TreeNode* node)
{printf ("%c\n", node->data);
}

主函數 main.c

#include <stdio.h>
#include "tree.h"int main()
{Tree* tree = Create_Tree();if (NULL == tree){myError ("Create_Tree");return -1;}Insert_Tree (tree, 'A', 0);Insert_Tree (tree, 'B', 0);Insert_Tree (tree, 'C', 0);Insert_Tree (tree, 'D', 0);Insert_Tree (tree, 'E', 1);Insert_Tree (tree, 'F', 1);Insert_Tree (tree, 'H', 3);Insert_Tree (tree, 'I', 3);Insert_Tree (tree, 'J', 3);Insert_Tree (tree, 'X', 3);Insert_Tree (tree, 'Z', 8);Display (tree, printA);//printf ("刪除B ：\n");TreeData x;//Delete(tree, 1, &x);//Display(tree, printA);printf ("height = %d\n", Tree_Height(tree));printf ("degree = %d\n", Tree_Degree(tree));return 0;
}

error.h是我自己寫的一個包含常見錯誤的頭文件，這里我就不發了。

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

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

相關文章

利用FS寄存器獲取KERNEL32.DLL基址算法的證明(ZZ)

利用FS寄存器獲取KERNEL32.DLL基址算法的證明(ZZ)

轉自&#xff1a;http://blog.csdn.net/int2e/archive/2008/01/09/2032732.aspxFS寄存器指向當前活動線程的TEB結構&#xff08;線程結構&#xff09; 偏移 說明 000 指向SEH鏈指針 004 線程堆棧頂部 008 線程堆棧底部 00C SubSystemTib 010 FiberData 014 ArbitraryUse…
閱讀更多...
很老很老的老偏方，小病一掃光

很老很老的老偏方，小病一掃光

1、洋蔥、生姜治頭皮屑 ①將一個的洋蔥頭用紗布包好&#xff0c;用它揉擦頭皮&#xff0c;24小時后用溫水洗頭&#xff0c;即可止頭癢&#xff0c;除頭皮屑。 ②先將生姜切片&#xff0c;放入鍋里煮沸&#xff0c;待水溫不燙的時候倒上適量醋&#xff0c;加水洗頭。 2、小白果…
閱讀更多...
script 放置最佳位置以及 html 執行順序

script 放置最佳位置以及 html 執行順序

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 看到知乎上有很多討論關于javascript位置的文章。所以特意留意了這方面的問題。 首先要了解到的是&#xff1a; html文件是自上而下的執…
閱讀更多...
677A

677A

#include <stdio.h> int main() {int n, h;scanf("%d%d", &n, &h);int temp, width0;int i;for(i0; i<n; i){scanf("%d", &temp);if(temp<h)width;elsewidth2;}printf("%d\n", width);return 0; }轉載于:https://www.cn…
閱讀更多...
數據結構之二叉樹的一些基本操作

數據結構之二叉樹的一些基本操作

二叉樹是樹的特殊一種&#xff0c;具有如下特點&#xff1a;1、每個結點最多有兩顆子樹&#xff0c;結點的度最大為2。2、左子樹和右子樹是有順序的&#xff0c;次序不能顛倒。3、即使某結點只有一個子樹&#xff0c;也要區分左右子樹。 頭文件 BTree.h #ifndef __BTREE_H__ …
閱讀更多...
【Arduino】使用C#實現Arduino與電腦進行串行通訊

【Arduino】使用C#實現Arduino與電腦進行串行通訊

在給Arduino編程的時候&#xff0c;因為沒有調試工具&#xff0c;經常要通過使用串口通訊的方式調用Serial.print和Serial.println輸出Arduino運行過程中的相關信息&#xff0c;然后在電腦上用Arduino IDE的Serial Monitor來查看print出來的信息。Serial Monitor不僅可以接受Ar…
閱讀更多...
虛擬機NAT模式聯網

虛擬機NAT模式聯網

阿里開源鏡像軟件&#xff1a;https://opsx.alibaba.com/mirror 如何使VMware ip與本機ip處于同一網段 https://blog.csdn.net/kakuma_chen/article/details/71425620 轉載于:https://www.cnblogs.com/cdy0626/p/11131440.html
閱讀更多...
VS2008下最新X264(svn 2009.9)編譯不過的解決辦法

VS2008下最新X264(svn 2009.9)編譯不過的解決辦法

總有人說最新的版本 編譯不過&#xff0c;搞的群、 論壇里到處都是這種求助貼。建議斑竹把這個解決辦法放到醒目的位置&#xff0c;以減少噪音。科普開始1、編譯問題由于MS的VS編譯器對C99標準支持不好&#xff0c;不支持函數當中混合定義、聲明變量。解決辦法&#xff1a;在函…
閱讀更多...
node、npm、vue安裝 -- VUE 項目 demo 實例

node、npm、vue安裝 -- VUE 項目 demo 實例

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 1. 安裝node&#xff1a; sudo yum install epel-release sudo yum install nodejs node --version // 安裝好后查看版本2. 安裝 npm …
閱讀更多...
用C語言實現簡單的停車場管理

用C語言實現簡單的停車場管理

這個程序是利用棧和循環隊列實現的&#xff0c;自己得先處理好邏輯關系就好了。由于題目沒有要求&#xff0c;這個程序就沒加重復判斷&#xff0c;比如一輛車已經停在車位上或者便道上&#xff0c;再來一輛就判斷不了了。關于棧&#xff0c;就是先進后出的思想&#xff0c;隊列…
閱讀更多...
推薦一個配置linux服務的網站

推薦一個配置linux服務的網站

該網站的各種linux服務的配置都是基于CentOS系統的 基本上各種linux服務都有了 http://www.server-world.info/en/轉載于:https://www.cnblogs.com/Skyar/p/3582389.html
閱讀更多...
mariadb數據庫增刪改查

mariadb數據庫增刪改查

1.常用數據類型 1&#xff09;整數:int, bit 2&#xff09;小數:decimal 　　 #decimal(5,2)表示共有五位數&#xff0c;保留兩位小數 3&#xff09;字符串:varchar, char　　 4&#xff09;日期時間:date, time, datetime 5&#xff09;枚舉類型(enu…
閱讀更多...
為什么你工作努力卻沒有起色？

為什么你工作努力卻沒有起色？

成為職場達人&#xff0c;未必要經常挑燈夜戰。相反&#xff0c;注意到下面幾條&#xff0c;會讓你少走彎路。 1&#xff09;成長的機會永遠比眼前的待遇重要——做重要的事比多拿錢重要。 我知道在水木bbs上的worklife版本&#xff0c;每天都在上演的就是比較自己的第一個o…
閱讀更多...
《 Spring 實戰 》（第4版） 讀書筆記 （未完結，更新中...）

《 Spring 實戰 》（第4版） 讀書筆記 （未完結，更新中...）

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 Pxx 表示在書的第 xx 頁。 Spring 框架的核心是 Spring 容器。 1. (P7.) 構造器注入是依賴注入的方式之一。 緊耦合&#xff1a;在 …
閱讀更多...
數據結構排序法之希爾排序法(Shell Sort)

數據結構排序法之希爾排序法(Shell Sort)

希爾排序&#xff0c;也叫遞減增量排序&#xff0c;是插入排序的一種更高效的改進版本。希爾排序是不穩定的排序算法。 希爾排序是基于插入排序的以下兩點性質而提出改進方法的&#xff1a; 1、插入排序在對幾乎已經排好序的數據操作時&#xff0c;效率高&#xff0c;即可以達…
閱讀更多...
Windows To Ghost系統封裝之必備軟件集 - 好壓

Windows To Ghost系統封裝之必備軟件集 - 好壓

好壓壓縮軟件&#xff08;HaoZip&#xff09;是強大的壓縮文件管理器&#xff0c;是完全免費的新一代壓縮軟件&#xff0c;相比其它壓縮軟件系統資源占用更少&#xff0c;有更好的兼容性&#xff0c;壓縮率比較高。 它提供了對ZIP、7Z和TAR文件的完整支持&#xff0c;能解壓RAR…
閱讀更多...
js 彈窗并定時關閉

js 彈窗并定時關閉

1. $(input).click(function() {prompt(點擊成功, 2000) })function prompt(newName, time, fn) {var $div $(<div></div>);$div.css({position: fixed,top: 0,left: 0,width: 100%,height: 100%,z-index: 200,background-color: rgba(0,0,0,0.4),// background-c…
閱讀更多...
數據結構排序法之插入法

數據結構排序法之插入法

插入排序是一種簡單直觀的排序算法。它的工作原理非常類似于我們抓撲克牌。 對于未排序數據(右手抓到的牌)&#xff0c;在已排序序列(左手已經排好序的手牌)中從后向前掃描&#xff0c;找到相應位置并插入。 插入排序在實現上&#xff0c;通常采用in-place排序&#xff08;即…
閱讀更多...
XSLT學習筆記

XSLT學習筆記

1. 樣式聲明&#xff1a;<xsl:stylesheet>或<xsl:transform> 2. XSLT常用元素&#xff1a; 2.1 <xsl:template>&#xff1a;創建模板 Match屬性的作用是使模板和XML元素相關聯 e.g.:<xsl:template match"\">......</xsl:template&g…
閱讀更多...
職場：人生從沒有最佳時機！一個離職客服人員的領悟

職場：人生從沒有最佳時機！一個離職客服人員的領悟

每個人都有感到失落迷惘的時候。 人生用專制又霸道的方式運行著&#xff0c;每當我們心想一切塵埃落定、生活穩固的時候&#xff0c;生活總愛給我們驚喜&#xff0c;粉碎我們短暫的安逸&#xff0c;讓我們不得不重新思考。 「我走對路了嗎?」 「我能夠賺更多錢、爬到更高的地位…
閱讀更多...
最新文章

Copyright @ 2022~2023