樹(資料結構) - 維基百科，自由的百科全書

在計算機科學中，樹（英語：tree）是一種抽象資料類型（ADT）或是實作這種抽象資料類型的資料結構，用來類比具有樹狀結構性質的資料集合。

它是由n（n>0）個有限節點 ... 樹(資料結構) 維基百科，自由的百科全書 跳至導覽 跳至搜尋 此條目包含指南或教學內容。

(2016年3月13日)請藉由移除或重寫指南段落來改善條目，或在討論頁提出討論。

此條目沒有列出任何參考或來源。

(2016年3月13日)維基百科所有的內容都應該可供查證。

請協助補充可靠來源以改善這篇條目。

無法查證的內容可能會因為異議提出而移除。

一棵樹 在計算機科學中，樹（英語：tree）是一種抽象資料類型（ADT）或是實作這種抽象資料類型的資料結構，用來類比具有樹狀結構性質的資料集合。

它是由n（n>0）個有限節點組成一個具有層次關係的集合。

把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

它具有以下的特點： 每個節點都只有有限個子節點或無子節點； 沒有父節點的節點稱為根節點； 每一個非根節點有且只有一個父節點； 除了根節點外，每個子節點可以分為多個不相交的子樹； 樹裡面沒有環路(cycle) 目次 1術語 2樹的種類 3存儲 3.1父節點表示法 3.1.1存儲結構 3.1.2基本操作 3.1.2.1構造空樹 3.1.2.2構造樹 3.1.2.3判斷樹是否為空 3.1.2.4獲取樹的深度 3.1.2.5獲取根節點 3.1.2.6獲取第i個節點的值 3.1.2.7改變節點的值 3.1.2.8獲取節點的父節點 3.1.2.9獲取節點的最左孩子節點 3.1.2.10獲取節點的右兄弟節點 3.1.2.11輸出樹 3.1.2.12向樹中插入另一棵樹 3.1.2.13刪除子樹 3.1.2.14層序遍歷樹 3.2孩子鍊表表示法 3.2.1存儲結構 4森林、樹與二元樹的轉換 5外部連結 6參考文獻 術語[編輯] 節點的度：一個節點含有的子樹的個數稱為該節點的度； 樹的度：一棵樹中，最大的節點度稱為樹的度； 葉節點或終端節點：度為零的節點； 非終端節點或分支節點：度不為零的節點； 父親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 兄弟節點：具有相同父節點的節點互稱為兄弟節點； 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推； 深度：對於任意節點n,n的深度為從根到n的唯一路徑長，根的深度為0； 高度：對於任意節點n,n的高度為從n到一片樹葉的最長路徑長，所有樹葉的高度為0； 堂兄弟節點：父節點在同一層的節點互為堂兄弟； 節點的祖先：從根到該節點所經分支上的所有節點； 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。

森林：由m（m>=0）棵互不相交的樹的集合稱為森林； 樹的種類[編輯] 無序樹：樹中任意節點的子節點之間沒有順序關係，這種樹稱為無序樹，也稱為自由樹。

有序樹：樹中任意節點的子節點之間有順序關係，這種樹稱為有序樹； 二元樹：每個節點最多含有兩個子樹的樹稱為二元樹； 完全二元樹：對於一棵二元樹，假設其深度為d（d>1）。

除了第d層外，其它各層的節點數目均已達最大值，且第d層所有節點從左向右連續地緊密排列，這樣的二元樹被稱為完全二元樹； 滿二元樹：所有葉節點都在最底層的完全二元樹； 平衡二元樹（AVL樹）：若且唯若任何節點的兩棵子樹的高度差不大於1的二元樹； 排序二元樹(二元搜尋樹（英語：BinarySearchTree))：也稱二元搜尋樹、有序二元樹； 霍夫曼樹：帶權路徑最短的二元樹稱為哈夫曼樹或最佳二元樹； B樹：一種對讀寫操作進行最佳化的自平衡的二元搜尋樹，能夠保持資料有序，擁有多於兩個子樹。

儲存[編輯] 父節點表示法[編輯] 儲存結構[編輯] /*树节点的定义*/ #defineMAX_TREE_SIZE100 typedefstruct { TElemTypedata; intparent;/*父节点位置域*/ }PTNode; typedefstruct { PTNodenodes[MAX_TREE_SIZE]; intn;/*节点数*/ }PTree; A B E   H     I     J         C   D   F   G   K         基本操作[編輯] 設已有鏈佇列類型LinkQueue的定義及基本操作（參見佇列）。

構造空樹[編輯] 清空或銷毀一個樹也是同樣的操作 voidClearTree(PTree*T) { T->n=0; } 構造樹[編輯] voidCreateTree(PTree*T) { LinkQueueq; QElemTypep,qq; inti=1,j,l; charc[MAX_TREE_SIZE];/*临时存放孩子节点数组*/ InitQueue(&q);/*初始化队列*/ printf("请输入根节点(字符型，空格为空):"); scanf("%c%*c",&T->nodes[0].data);/*根节点序号为0，%*c吃掉回车符*/ if(T->nodes[0].data!=Nil)/*非空树*/ { T->nodes[0].parent=-1;/*根节点无父节点*/ qq.name=T->nodes[0].data; qq.num=0; EnQueue(&q,qq);/*入队此节点*/ while(inodes[i].data=c[j]; T->nodes[i].parent=qq.num; p.name=c[j]; p.num=i; EnQueue(&q,p);/*入队此节点*/ i++; } } if(i>MAX_TREE_SIZE) { printf("节点数超过数组容量\n"); exit(OVERFLOW); } T->n=i; } else T->n=0; } 判斷樹是否為空[編輯] StatusTreeEmpty(PTree*T) {/*初始条件：树T存在。

操作结果：若T为空树，则返回TRUE，否则返回FALSE*/ returnT->n==0; } 取得樹的深度[編輯] intTreeDepth(PTree*T) {/*初始条件：树T存在。

操作结果：返回T的深度*/ intk,m,def,max=0; for(k=0;kn;++k) { def=1;/*初始化本节点的深度*/ m=T->nodes[k].parent; while(m!=-1) { m=T->nodes[m].parent; def++; } if(maxn;i++) if(T->nodes[i].parent<0) returnT->nodes[i].data; returnNil; } 取得第i個節點的值[編輯] TElemTypeValue(PTree*T,inti) {/*初始条件：树T存在，i是树T中节点的序号。

操作结果：返回第i个节点的值*/ if(in) returnT->nodes[i].data; else returnNil; } 改變節點的值[編輯] StatusAssign(PTree*T,TElemTypecur_e,TElemTypevalue) {/*初始条件：树T存在，cur_e是树T中节点的值。

操作结果：改cur_e为value*/ intj; for(j=0;jn;j++) { if(T->nodes[j].data==cur_e) { T->nodes[j].data=value; returnOK; } } returnERROR; } 取得節點的父節點[編輯] TElemTypeParent(PTree*T,TElemTypecur_e) {/*初始条件：树T存在，cur_e是T中某个节点*/ /*操作结果：若cur_e是T的非根节点，则返回它的父节点，否则函数值为＂空＂*/ intj; for(j=1;jn;j++)/*根节点序号为0*/ if(T->nodes[j].data==cur_e) returnT->nodes[T->nodes[j].parent].data; returnNil; } 取得節點的最左孩子節點[編輯] TElemTypeLeftChild(PTree*T,TElemTypecur_e) {/*初始条件：树T存在，cur_e是T中某个节点*/ /*操作结果：若cur_e是T的非叶子节点，则返回它的最左孩子，否则返回＂空＂*/ inti,j; for(i=0;in;i++) if(T->nodes[i].data==cur_e)/*找到cur_e，其序号为i*/ break; for(j=i+1;jn;j++)/*根据树的构造函数，孩子的序号＞其父节点的序号*/ if(T->nodes[j].parent==i)/*根据树的构造函数，最左孩子(长子)的序号＜其它孩子的序号*/ returnT->nodes[j].data; returnNil; } 取得節點的右兄弟節點[編輯] TElemTypeRightSibling(PTree*T,TElemTypecur_e) {/*初始条件：树T存在，cur_e是T中某个节点*/ /*操作结果：若cur_e有右(下一个)兄弟，则返回它的右兄弟，否则返回＂空＂*/ inti; for(i=0;in;i++) if(T->nodes[i].data==cur_e)/*找到cur_e，其序号为i*/ break; if(T->nodes[i+1].parent==T->nodes[i].parent) /*根据树的构造函数，若cur_e有右兄弟的话则右兄弟紧接其后*/ returnT->nodes[i+1].data; returnNil; } 輸出樹[編輯] voidPrint(PTree*T) {/*输出树T。

加*/ inti; printf("节点个数=%d\n",T->n); printf("节点父节点\n"); for(i=0;in;i++) { printf("%c",Value(T,i));/*节点*/ if(T->nodes[i].parent>=0)/*有父节点*/ printf("%c",Value(T,T->nodes[i].parent));/*父节点*/ printf("\n"); } } 向樹中插入另一棵樹[編輯] StatusInsertChild(PTree*T,TElemTypep,inti,PTreec) {/*初始条件：树T存在，p是T中某个节点，1≤i≤p所指节点的度+1，非空树c与T不相交*/ /*操作结果：插入c为T中p节点的第i棵子树*/ intj,k,l,f=1,n=0;/*设交换标志f的初值为1，p的孩子数n的初值为0*/ PTNodet; if(!TreeEmpty(T))/*T不空*/ { for(j=0;jn;j++)/*在T中找p的序号*/ if(T->nodes[j].data==p)/*p的序号为j*/ break; l=j+1;/*如果c是p的第1棵子树，则插在j+1处*/ if(i>1)/*c不是p的第1棵子树*/ { for(k=j+1;kn;k++)/*从j+1开始找p的前i-1个孩子*/ if(T->nodes[k].parent==j)/*当前节点是p的孩子*/ { n++;/*孩子数加1*/ if(n==i-1)/*找到p的第i-1个孩子，其序号为k1*/ break; } l=k+1;/*c插在k+1处*/ }/*p的序号为j，c插在l处*/ if(ln)/*插入点l不在最后*/ for(k=T->n-1;k>=l;k--)/*依次将序号l以后的节点向后移c.n个位置*/ { T->nodes[k+c.n]=T->nodes[k]; if(T->nodes[k].parent>=l) T->nodes[k+c.n].parent+=c.n; } for(k=0;knodes[l+k].data=c.nodes[k].data;/*依次将树c的所有节点插于此处*/ T->nodes[l+k].parent=c.nodes[k].parent+l; } T->nodes[l].parent=j;/*树c的根节点的父节点为p*/ T->n+=c.n;/*树T的节点数加c.n个*/ while(f) {/*从插入点之后，将节点仍按层序排列*/ f=0;/*交换标志置0*/ for(j=l;jn-1;j++) if(T->nodes[j].parent>T->nodes[j+1].parent) {/*如果节点j的父节点排在节点j+1的父节点之后（树没有按层序排列），交换两节点*/ t=T->nodes[j]; T->nodes[j]=T->nodes[j+1]; T->nodes[j+1]=t; f=1;/*交换标志置1*/ for(k=j;kn;k++)/*改变父节点序号*/ if(T->nodes[k].parent==j) T->nodes[k].parent++;/*父节点序号改为j+1*/ elseif(T->nodes[k].parent==j+1) T->nodes[k].parent--;/*父节点序号改为j*/ } } returnOK; } else/*树T不存在*/ returnERROR; } 刪除子樹[編輯] Statusdeleted[MAX_TREE_SIZE+1];/*删除标志数组(全局量)*/ voidDeleteChild(PTree*T,TElemTypep,inti) {/*初始条件：树T存在，p是T中某个节点，1≤i≤p所指节点的度*/ /*操作结果：删除T中节点p的第i棵子树*/ intj,k,n=0; LinkQueueq; QElemTypepq,qq; for(j=0;j<=T->n;j++) deleted[j]=0;/*置初值为0(不删除标记)*/ pq.name='a';/*此成员不用*/ InitQueue(&q);/*初始化队列*/ for(j=0;jn;j++) if(T->nodes[j].data==p) break;/*j为节点p的序号*/ for(k=j+1;kn;k++) { if(T->nodes[k].parent==j) n++; if(n==i) break;/*k为p的第i棵子树节点的序号*/ } if(kn)/*p的第i棵子树节点存在*/ { n=0; pq.num=k; deleted[k]=1;/*置删除标记*/ n++; EnQueue(&q,pq); while(!QueueEmpty(q)) { DeQueue(&q,&qq); for(j=qq.num+1;jn;j++) if(T->nodes[j].parent==qq.num) { pq.num=j; deleted[j]=1;/*置删除标记*/ n++; EnQueue(&q,pq); } } for(j=0;jn;j++) if(deleted[j]==1) { for(k=j+1;k<=T->n;k++) { deleted[k-1]=deleted[k]; T->nodes[k-1]=T->nodes[k]; if(T->nodes[k].parent>j) T->nodes[k-1].parent--; } j--; } T->n-=n;/*n为待删除节点数*/ } } 層序遍歷樹[編輯] voidTraverseTree(PTree*T,void(*Visit)(TElemType)) {/*初始条件：二叉树T存在,Visit是对节点操作的应用函数*/ /*操作结果：层序遍历树T,对每个节点调用函数Visit一次且仅一次*/ inti; for(i=0;in;i++) Visit(T->nodes[i].data); printf("\n"); } 孩子連結串列表示法[編輯] 儲存結構[編輯] /*树的孩子链表存储表示*/ typedefstructCTNode{//孩子节点 intchild; structCTNode*next; }*ChildPtr; typedefstruct{ ElemTypedata；//节点的数据元素 ChildPtrfirstchild；//孩子链表头指针 }CTBox; typedefstruct{ CTBoxnodes[MAX_TREE_SIZE]； intn,r；//节点数和根节点的位置 }CTree; A B E   H     I     J         C   D   F   G   K         森林、樹與二元樹的轉換[編輯] 見二元樹相應章節 外部連結[編輯] （中文）樹-資料結構(Python)byEINDEX 參考文獻[編輯] 閱論編演算法排序比較排序 泡沫排序 選擇排序 插入排序 希爾排序 快速排序 合併排序 堆積排序 雞尾酒排序 梳排序 侏儒排序 圖書館排序 內省排序 奇偶排序 線性時間排序 鴿巢排序 基數排序 計數排序 桶排序 並列排序 排序網路（英語：Sortingnetwork） Batcher合併網路 不實用的 Bogo排序 臭皮匠排序 圖 拓撲排序 搜尋列表 線性搜尋 二分搜尋 插值搜尋 樹・圖 廣度優先搜尋 最良優先搜尋（英語：Best-firstsearch） 均一開銷搜尋 A* 深度優先搜尋 迭代深化深度優先搜尋 深度限制搜尋（日語：深さ制限探索） 雙向搜尋 分枝限定法（英語：Branchandbound） 字串 KMP演算法 博耶-穆爾字串搜尋演算法 AC自動機演算法 拉賓-卡普演算法 bitap演算法 最短路問題 戴克斯特拉演算法 貝爾曼-福特演算法 A*搜尋演算法 Floyd-Warshall演算法 最小生成樹 普林姆演算法 克魯斯克爾演算法 最大流最小割 福特-富爾克森演算法 埃德蒙茲-卡普演算法 迪尼茨演算法 線性規劃 單純形法 卡馬卡爾演算法（英語：Karmarkar'salgorithm） 順序統計量 選擇演算法 中位數的中位數（英語：Medianofmedians） 種類 近似演算法 隨機化演算法 其他 分治法 動態規劃 貪婪演算法 Category:演算法 閱論編電腦科學中的樹二元樹 二元搜尋樹（BST） 笛卡爾樹 MVP樹 Toptree（英語：Toptree） T樹 線索二元樹 自平衡二元搜尋樹 AA樹 AVL樹 左傾紅黑樹 紅黑樹 替罪羊樹 伸展樹 樹堆 加權平衡樹 B樹 B+樹 B*樹 Bx樹 UB樹 2-3樹 2-3-4樹 (a,b)-樹 Dancingtree（英語：Dancingtree） H樹 堆 二元堆積 二項堆 斐波那契堆 左偏樹 配對堆 斜堆 VanEmdeBoastree（英語：VanEmdeBoastree） Trie 字尾樹 基數樹 三元搜尋樹 X-快速字首樹 Y-快速字首樹 AC自動機 二元空間分割（BSP）樹 四元樹 八元樹 k-d樹 隱式k-d樹 VP樹 非二元樹 指數樹（英語：Exponentialtree） 融合樹（英語：Fusiontree） PQ樹（英語：PQtree） SPQR樹（英語：SPQRtree） 空間資料分割樹 R樹 R*樹 R+樹 X樹 M樹 線段樹 可持久化線段樹 希爾伯特R樹 優先R樹 其他樹 雜湊日曆 雜湊樹 Fingertree（英語：Fingertree） 順序統計樹 Metrictree（英語：Metrictree） Covertree（英語：Covertree） BK樹 Doublychainedtree（英語：Doublychainedtree） iDistance（英語：iDistance） Link-cuttree（英語：Link-cuttree） Log-structuredmerge-tree（英語：Log-structuredmerge-tree） 樹狀陣列 雜湊樹 閱論編資料結構類型 集合 容器 抽象類型 關聯陣列 多重關連陣列（英語：Multimap） 列表 堆疊 佇列 雙端佇列 優先佇列 雙端優先佇列 集合 多重集 併查集 可持久化資料結構 線段樹 陣列 字串 位陣列 環形緩衝區 動態陣列（英語：Dynamicarray） 雜湊表 雜湊陣列樹（英語：Hashedarraytree） 稀疏矩陣 鏈（英語：Linkeddatastructure） 關聯表（英語：Associationlist） 連結串列 跳躍列表 鬆散連結串列（英語：Unrolledlinkedlist） 互斥或連結串列 樹 線段樹 自平衡二元搜尋樹 B樹 二元樹 AA樹 AVL樹 紅黑樹 平衡樹 伸展樹 二元搜尋樹 堆 二元堆積 左偏樹 二項堆 斐波那契堆 R樹 R*樹 R+樹 HilbertR樹（英語：HilbertR-tree） 字首樹 雜湊樹 圖 有向圖 有向無環圖 二元決策圖 無向圖 確定性非迴圈有限自動機（英語：Deterministicacyclicfinitestateautomaton） 資料結構術語列表 取自「https://zh.wikipedia.org/w/index.php?title=树_(数据结构)&oldid=68602937」 分類：​樹結構資料結構隱藏分類：​自2016年3月包含指南或教學內容的條目自2016年3月缺少來源的條目含有英語的條目 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他專案 維基共享資源 其他語言 العربيةБългарскиCatalàČeštinaЧӑвашлаDanskDeutschEnglishEsperantoEspañolEestiفارسیSuomiFrançaisMagyarBahasaIndonesiaItaliano日本語한국어LietuviųLatviešuМакедонскиമലയാളംМонголNederlandsNorskbokmålPolskiPortuguêsРусскийSrpskohrvatski/српскохрватскиSimpleEnglishSlovenščinaСрпски/srpskiSvenskaதமிழ்ไทยTagalogTürkçeУкраїнськаTiếngViệt粵語 編輯連結