fbpx
维基百科

二叉树

四月 04, 2023

在電腦科學中，二元樹（英語：Binary tree）是每個節點最多只有兩個分支（即不存在分支度大於2的節點）的樹結構[1]。通常分支被稱作“左子樹”或“右子樹”。二元樹的分支具有左右次序，不能随意顛倒。

一棵有9個節點且深度為3的二元樹，其根節點的值為2，它既不平衡亦未經過排序
一棵簡單的滿二叉樹

二元樹的第層至多擁有個節點；深度為的二元樹至多總共有個節點（定义根节点所在深度 ），而總計擁有節點數符合的，稱為「滿二元樹」；深度為有個節點的二元樹，當且僅當其中的每一節點，都可以和深度的滿二元樹，序號1到的節點一對一對應時，稱為完全二元樹。對任何一棵非空的二元樹，如果其葉片（終端節點）數為，分支度為2的節點數為，則。

與普通樹不同，普通樹的節點個數至少為1，而二元樹的節點個數可以為0；普通樹節點的最大分支度沒有限制，而二元樹節點的最大分支度為2；普通樹的節點無左、右次序之分，而二元樹的節點有左、右次序之分。

二元樹通常作為資料結構應用，典型用法是對節點定義一個標記函數，將一些值與每個節點相關聯。這樣標記的二元樹就可以實現二元搜尋樹和二元堆積，並應用於高效率的搜索和排序。

圖論中的定義

二元樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二元樹還要滿足根節點的度不大於2。有了根節點之後，每個頂點定義了唯一的父節點，和最多2個子節點。然而，沒有足夠的資訊來區分左節點和右節點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。

性质

二元樹是一個有根树，並且每個節點最多有2個子節點。非空的二叉樹，若樹葉總數為 n0，分支度為2的總數為 n2，則 n0 = n2 + 1。

 

特殊类型

 

完全二元樹 完美二元樹
總節點k  <= k <=   k =  
樹高h h =   h =  

完美二叉树

一棵深度為k，且有 個節點的二元樹，稱為完美二元樹（Perfect Binary Tree）。這種樹的特點是每一層上的節點數都是最大節點數。

性质

对于一棵深度为   的完美二叉树：

  • 共有   个结点
  • 结点个数一定为奇数
  • 第   层有   个结点
  • 有   个叶子

完全二叉树

在一颗二元樹中，若除最後一層外的其餘層都是滿的，並且最後一層要么是满的，要么在右邊缺少連續若干節點，則此二元樹為完全二元樹（Complete Binary Tree）。具有n個節點的完全二元樹的深度為 。深度為k的完全二元樹，至少有 個節點，至多有 個節點。

存儲

在程式設計語言中能用多種方法來構造二元樹。

順序存儲表示

 
一個存儲在陣列中的完全二元樹

二元樹可以用陣列或链表來存儲，若是滿二元樹就能緊湊排列而不浪費空間。如果某個節點的索引為i，（假設根節點的索引為0）則在它左子節點的索引會是 ，以及右子節點會是 ；而它的父節點（如果有）索引則為 。這種方法更有利於緊湊存儲和更好的訪問的局部性，特別是在前序遍歷中。然而，它需要連續的存儲空間，這樣在存儲高度為h的n個節點所組成的一般樹時，將浪費很多空間。在最糟糕的情況下，如果深度為h的二元樹其每個節點都只有右孩子，則該存儲結構需要佔用 的空間，實際上卻有h個節點，浪費了不少空間，是順序存儲結構的一大缺點。

存储结构

 /* 二叉树的顺序存储表示 */  #define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */  typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根节点 */  typedef struct  {  int level,order; /* 即节点的层(按[满二叉树]计算) */  }position;

基本操作

二叉鏈表存儲表示

 
基於鏈表的二叉樹邏輯結構示意

在使用記錄或記憶體位址指標的程式設計語言中，二叉樹通常用樹結點結構來存儲。有時也包含指向唯一的父節點的指標。如果一個結點的子結點個數小於2，一些子結點指針可能為空值，或者為特殊的哨兵結點。 使用鏈表能避免順序儲存浪費空間的問題，演算法和結構相對簡單，但使用二叉鏈表，由於缺乏父鏈的指引，在找回父節點時需要重新掃描樹得知父節點的節點位址。

存儲結構

/* 二叉樹的二叉鏈表存儲表示 */  typedef struct BiTNode  {  TElemType data;  struct BiTNode *lchild,*rchild; /* 左右孩子指針 */  }BiTNode,*BiTree;

基本操作

三叉鏈表存儲表示

 
基於三叉鏈表的二叉樹的邏輯結構

改進於二叉鏈表，增加父節點的指引，能更好地實現節點間的訪問，不過演算法相對複雜。 當二叉樹用三叉鏈表表示時，有N個結點，就會有N+2個空指針。

存儲結構

 /* 二叉樹的三叉鏈表存儲表示 */  typedef struct BiTPNode  {  TElemType data;  struct BiTPNode *parent,*lchild,*rchild; /* 父、左右孩子指針 */  }BiTPNode,*BiPTree;

基本操作

遍历

主条目：樹的遍歷

我們經常希望訪問樹中的每一個結點並且查看它的值。有很多常見的順序來訪問所有的結點，而且每一種都有有用的性質。

深度優先遍歷

参见：深度優先搜索

在深度優先順序中，我們希望從根結點訪問最遠的結點。和圖的深度優先搜索不同的是，不需記住訪問過的每一個結點，因為樹中不會有環。前序，中序和後序遍歷都是深度優先遍歷的特例。

前（先）序、中序、後序遍歷

遍歷二叉樹：L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹，則先(根)序遍歷二叉樹的順序是DLR，中(根)序遍歷二叉樹的順序是LDR，後(根)序遍歷二叉樹的順序是LRD。還有按層遍歷二叉樹。這些方法的時間複雜度都是O(n)，n為結點個數。

如果T2是由有序樹T轉換而來的二叉樹，那麼T中結點的前序就是T2中結點的前序，T中結點的後序就是T2中結點的中序。任何一棵二叉樹的葉結點在先序、中序和後序遍歷中的相對次序不發改變。設n,m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是n在m的左方。前序序列和中序序列相同的二叉樹為空樹或任一結點均無左孩子的非空二叉樹；中序序列和後序序列相同的二叉樹為空樹或任一結點均無右孩子的非空二叉樹；前序序列和後序序列相同的二叉樹為空樹或僅有一個結點的二叉樹。

假設我們有一個包含值的value和指向兩個子結點的left和right的樹結點結構。我們可以寫出這樣的過程： 

visit(node) print node.value if node.left  != null then visit(node.left) if node.right != null then visit(node.right)

這樣會用前序打印出樹中的值。在前序，每個結點在訪問它的子結點之前訪問。類似地，如果打印語句在最後，每個結點在訪問他的子節點之後訪問，樹中的值會用後序來打印。在這兩種情況中，左子樹中的值比右子樹中得值先打印。 

visit(node) if node.left  != null then visit(node.left) print node.value if node.right != null then visit(node.right)

最後，上面的中序遍歷，每個結點在訪問左子樹和右子樹之間訪問。這在遍歷二叉搜尋樹時很常用，因為它能用遞增的順序來遍歷所有的值。

為什麼呢？如果n是二叉搜尋樹的結點，那麼n的左子樹的所有結點的值都比n的值要小，而且n的右子樹的所有節點的值都比n的值要大。因此，如果我們順序遍歷左子樹，然後訪問n，然後順序遍歷右子樹。我們就已經循序存取了整個樹。

后序遍历伪代码如下： 

visit(node) if node.left  != null then visit(node.left) if node.right != null then visit(node.right) print node.value
 
BinaryTree
 在這個二叉樹中，
  • 前序遍歷的結果：M，G，D，B，A，C，F，E，J，H，I，K，L，S，P，O，N，Q，R，W，U，T，V，X，Z，Y
  • 後序遍歷的結果：A，C，B，E，F，D，I，H，L，K，J，G，N，O，R，Q，P，T，V，U，Y，Z，X，W，S，M
  • 中序遍歷的結果：A，B，C，D，E，F，G，H，I，J，K，L，M，N，O，P，Q，R，S，T，U，V，W，X，Y，Z


以上的遞迴演算法使用與樹的高度成比例的棧空間。如果我們在每個結點中存儲指向父結點的指標，那樣可以使用反覆運算演算法，只使用常數空間實現所有這些遍歷。然而，指向父結點的指標佔用更多的空間。這只在需要指向父節點的指標或棧空間有限時才使用。例如， 這是一個中序遍歷的反覆運算演算法： 

visit(root) prev  := null current := root next  := null while current != null if prev == current.parent prev := current next := current.left if next == null or prev == current.left print current.value prev := current next := current.right if next == null or prev == current.right prev := current next := current.parent current := next


  用二叉樹表示下述運算式：a+b*(c-d)-e/f
  • 先序遍歷的序列是：-+a*b-cd/ef
  • 中序遍歷的序列是：a+b*c-d-e/f
  • 後序遍歷的序列是：abcd-*+ef/-

廣度優先遍歷

参见：廣度優先搜索

和深度優先遍歷不同，廣度優先遍歷會先訪問離根節點最近的節點。二叉樹的廣度優先遍歷又稱按層次遍歷。演算法借助佇列實現。

轉換自多叉樹

一般有序樹可映射为二叉樹，但反之未必成立。

n叉樹轉換為二叉樹的方法：二叉樹中結點x的左子結點為n叉樹中結點x的左子結點；二叉樹中結點x的右子結點為n叉樹中結點x的第一個右邊的同級結點y。

二叉树当且仅当根节点没有右子结点时可转换为n叉树。

例如，在左邊的樹中，A有6個子結點{B,C,D,E,F,G}。它能被轉換成右邊的二叉樹。

 


  • 將一棵樹轉換為二叉樹的方法：
  1. 在兄弟之間加一連線；
  2. 對每個結點，除了其左孩子外，去除其與其餘孩子之間的聯繫；
  3. 以樹的根結點為軸心，將整樹順時針轉45度。

樹的二叉鏈表標記法（孩子兄弟標記法）

樹的二叉鏈表標記法（孩子兄弟標記法）是樹和二叉樹轉換的媒介。

存儲結構

 
二叉樹與森林相互轉換的邏輯示意
 /* 樹的二叉鏈表(孩子—兄弟)存儲表示 */  typedef struct CSNode  {  TElemType data;  struct CSNode *firstchild,*nextsibling;  }CSNode,*CSTree;

基本操作

線索二叉樹

主条目：線索二叉樹

線索二叉樹（英語：threaded binary tree，保留遍歷時結點在任一序列的前驅和後繼的資訊）：若結點有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅；若結點有右子樹，則其rchild域指示其右孩子，否則令rchild指示其後繼。還需在結點結構中增加兩個標誌域LTag和RTag。LTag=0時，lchild域指示結點的左孩子，LTag=1時，lchild域指示結點的前驅；RTag=0時，rchild域指示結點的右孩子，RTag=1時，rchild域指示結點的後繼。以這種結點結構構成的二叉鏈表作為二叉樹的存儲結構，叫做線索鏈表，其中指向結點前驅和後繼的指標叫做線索，加上線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。若對二叉樹進行中序遍歷，則所得的線索二叉樹稱為中序線索二叉樹，線索鏈表稱為為中序線索鏈表。線索二叉樹是一種物理結構。  

在中序線索樹找結點後繼的規律是：若其右標誌為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標誌為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。
在後序線索樹中找到結點的後繼分三種情況：

  1. 若結點是二叉樹的根，則其後繼為空；
  2. 若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；
  3. 若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。

二叉線索存儲表示

存儲結構

二叉樹的二叉線索存儲表示：在線索鏈表上添加一個頭結點，並令其lchild域的指標指向二叉樹的根結點，其rchild域的指標指向中序遍歷時訪問的最後一個結點。令二叉樹中序序列中的第一個結點的lchild域指標和最後一個結點的rchild域的指標均指向頭結點，這樣就建立了一個雙向線索鏈表。二叉樹常採用二叉鏈表方式存儲。 

 /* 二叉樹的二叉線索存儲表示 */  typedef enum{Link,Thread}PointerTag; /* Link(0)：指針，Thread(1)：線索 */  typedef struct BiThrNode  {  TElemType data;  struct BiThrNode *lchild,*rchild; /* 左右孩子指針 */  PointerTag LTag,RTag; /* 左右標誌 */  }BiThrNode,*BiThrTree;

基本操作

外部链接

维基共享资源中相关的多媒体资源：二叉树
  • binary trees（页面存档备份，存于互联网档案馆） entry in the FindStat（页面存档备份，存于互联网档案馆）数据库
  • Gamedev.net introduction on binary trees（页面存档备份，存于互联网档案馆）
  • 二叉树归纳证明（页面存档备份，存于互联网档案馆）
  • Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array（页面存档备份，存于互联网档案馆）
  1. ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. B.5.3 Binary and positional trees. Introduction to algorithms Third. Cambridge, Mass.: MIT Press. 2009: 1177–1178 [2023-02-06]. ISBN 978-0-262-03384-8. 

四月 04, 2023
二叉树, 此條目可能包含了过多, 不重要或有倾向的範例, 2015年4月8日, 請協助改善條目, 增加敘述, 去除不太相关與过剩的範例, 可参考更優秀條目寫作指南獲得更進一步資訊, 本條目有隱藏内容, 可能會损害讀者的閱覽体验, 請協助改善條目, 以符合维基百科标准, 2015年3月2日, 一般應該僅由特定標準化模板提供摺疊資料表格, 勿因故事劇情或項目混雜而隱藏, 內容應該考慮其他方式呈現, 重複記載, 過度細節與無助了解主題的堆砌內容等需要考慮除去, 在電腦科學中, 二元樹, 英語, binary, tree,. 此條目可能包含了过多 不重要或有倾向的範例 2015年4月8日 請協助改善條目 增加敘述 去除不太相关與过剩的範例 可参考更優秀條目寫作指南獲得更進一步資訊 本條目有隱藏内容 可能會损害讀者的閱覽体验 請協助改善條目 以符合维基百科标准 2015年3月2日 一般應該僅由特定標準化模板提供摺疊資料表格 勿因故事劇情或項目混雜而隱藏 內容應該考慮其他方式呈現 重複記載 過度細節與無助了解主題的堆砌內容等需要考慮除去 在電腦科學中 二元樹 英語 Binary tree 是每個節點最多只有兩個分支 即不存在分支度大於2的節點 的樹結構 1 通常分支被稱作 左子樹 或 右子樹 二元樹的分支具有左右次序 不能随意顛倒 一棵有9個節點且深度為3的二元樹 其根節點的值為2 它既不平衡亦未經過排序 一棵簡單的滿二叉樹 二元樹的第i displaystyle i 層至多擁有2 i 1 displaystyle 2 i 1 個節點 深度為k displaystyle k 的二元樹至多總共有2 k 1 1 displaystyle 2 begin aligned k 1 end aligned 1 個節點 定义根节点所在深度 k 0 0 displaystyle k 0 0 而總計擁有節點數符合的 稱為 滿二元樹 深度為k displaystyle k 有n displaystyle n 個節點的二元樹 當且僅當其中的每一節點 都可以和深度k displaystyle k 的滿二元樹 序號1到n displaystyle n 的節點一對一對應時 稱為完全二元樹 對任何一棵非空的二元樹T displaystyle T 如果其葉片 終端節點 數為n 0 displaystyle n 0 分支度為2的節點數為n 2 displaystyle n 2 則n 0 n 2 1 displaystyle n 0 n 2 1 與普通樹不同 普通樹的節點個數至少為1 而二元樹的節點個數可以為0 普通樹節點的最大分支度沒有限制 而二元樹節點的最大分支度為2 普通樹的節點無左 右次序之分 而二元樹的節點有左 右次序之分 二元樹通常作為資料結構應用 典型用法是對節點定義一個標記函數 將一些值與每個節點相關聯 這樣標記的二元樹就可以實現二元搜尋樹和二元堆積 並應用於高效率的搜索和排序 目录 1 圖論中的定義 2 性质 3 特殊类型 3 1 完美二叉树 3 1 1 性质 3 2 完全二叉树 4 存儲 4 1 順序存儲表示 4 1 1 存储结构 4 1 2 基本操作 4 2 二叉鏈表存儲表示 4 2 1 存儲結構 4 2 2 基本操作 4 3 三叉鏈表存儲表示 4 3 1 存儲結構 4 3 2 基本操作 5 遍历 5 1 深度優先遍歷 5 1 1 前 先 序 中序 後序遍歷 5 2 廣度優先遍歷 6 轉換自多叉樹 6 1 樹的二叉鏈表標記法 孩子兄弟標記法 6 1 1 存儲結構 6 1 2 基本操作 7 線索二叉樹 7 1 二叉線索存儲表示 7 1 1 存儲結構 7 1 2 基本操作 8 外部链接圖論中的定義 编辑二元樹是一個連通的無環圖 並且每一個頂點的度不大於3 有根二元樹還要滿足根節點的度不大於2 有了根節點之後 每個頂點定義了唯一的父節點 和最多2個子節點 然而 沒有足夠的資訊來區分左節點和右節點 如果不考慮連通性 允許圖中有多個連通分量 這樣的結構叫做森林 性质 编辑二元樹是一個有根树 並且每個節點最多有2個子節點 非空的二叉樹 若樹葉總數為 n0 分支度為2的總數為 n2 則 n0 n2 1 特殊类型 编辑 完全二元樹 完美二元樹總節點k 2 h 1 displaystyle 2 h 1 lt k lt 2 h 1 displaystyle 2 h 1 k 2 h 1 displaystyle 2 h 1 樹高h h l o g 2 k 1 displaystyle log 2 k 1 h l o g 2 k 1 displaystyle log 2 k 1 完美二叉树 编辑 一棵深度為k 且有2 k 1 displaystyle 2 begin aligned k end aligned 1 個節點的二元樹 稱為完美二元樹 Perfect Binary Tree 這種樹的特點是每一層上的節點數都是最大節點數 性质 编辑 对于一棵深度为 k displaystyle k 的完美二叉树 共有 2 k 1 displaystyle 2 k 1 个结点 结点个数一定为奇数 第 i displaystyle i 层有 2 i 1 displaystyle 2 i 1 个结点 有 2 k 1 displaystyle 2 k 1 个叶子完全二叉树 编辑 在一颗二元樹中 若除最後一層外的其餘層都是滿的 並且最後一層要么是满的 要么在右邊缺少連續若干節點 則此二元樹為完全二元樹 Complete Binary Tree 具有n個節點的完全二元樹的深度為l o g 2 n 1 displaystyle log 2 n 1 深度為k的完全二元樹 至少有2 k 1 displaystyle 2 begin aligned k 1 end aligned 個節點 至多有2 k 1 displaystyle 2 begin aligned k end aligned 1 個節點 存儲 编辑在程式設計語言中能用多種方法來構造二元樹 順序存儲表示 编辑 一個存儲在陣列中的完全二元樹 二元樹可以用陣列或链表來存儲 若是滿二元樹就能緊湊排列而不浪費空間 如果某個節點的索引為i 假設根節點的索引為0 則在它左子節點的索引會是2 i 1 displaystyle 2i 1 以及右子節點會是2 i 2 displaystyle 2i 2 而它的父節點 如果有 索引則為 i 1 2 displaystyle left lfloor frac i 1 2 right rfloor 這種方法更有利於緊湊存儲和更好的訪問的局部性 特別是在前序遍歷中 然而 它需要連續的存儲空間 這樣在存儲高度為h的n個節點所組成的一般樹時 將浪費很多空間 在最糟糕的情況下 如果深度為h的二元樹其每個節點都只有右孩子 則該存儲結構需要佔用2 h 1 displaystyle 2 h 1 的空間 實際上卻有h個節點 浪費了不少空間 是順序存儲結構的一大缺點 存储结构 编辑 二叉树的顺序存储表示 define MAX TREE SIZE 100 二叉树的最大节点数 typedef TElemType SqBiTree MAX TREE SIZE 0号单元存储根节点 typedef struct int level order 即节点的层 按 满二叉树 计算 position 基本操作 编辑 基於C C 的實現演算法 二元樹 的順序存儲的基本操作 23個 define ClearBiTree InitBiTree 在順序存儲結構中 兩函數完全一樣 define DestroyBiTree InitBiTree 在順序存儲結構中 兩函數完全一樣 void InitBiTree SqBiTree T SqBiTree amp T 構造 空二元樹 T 因為T是陣列名稱 故不需要 amp int i for i 0 i lt MAX TREE SIZE i T i Nil 初值為空 Nil在主程中定義 void CreateBiTree SqBiTree T 按層序次序輸入二叉樹中結點的值 字元型或整型 構造順序存儲的二叉樹T int i 0 if CHAR 結點類型為字元 int l char s MAX TREE SIZE InitBiTree T 構造 空二元樹 T printf 請按層序輸入結點的值 字元 空格表示空結點 節點數 d n MAX TREE SIZE gets s 輸入字串 l strlen s 求字串的長度 for i lt l i 將字串賦值給T T i s i else 節點類型為整型 InitBiTree T 構造 空二元樹 T printf 請按層序輸入節點的值 整型 0表示空節點 輸999結束 節點數 d n MAX TREE SIZE while 1 scanf d amp T i if T i 999 T i Nil break i endif for i 1 i lt MAX TREE SIZE i if T i 1 2 1 Nil amp amp T i Nil 此非根節點 不空 無雙親 printf 出現無雙親的非根節點 form n T i exit ERROR int BiTreeDepth SqBiTree T 初始條件 二元樹 T存在 操作結果 返回T的深度 int i j 1 for i MAX TREE SIZE 1 i gt 0 i 找到最後一個節點 if T i Nil break i 為了便於計算 do j while i gt pow 2 j pow是原型為double pow double x double y 計算x的y次方 h log lt sub gt 2 lt sub gt k 1來計算 二元樹 的深度 return j Status Root SqBiTree T TElemType e 初始條件 二元樹 T存在 操作結果 當T不空 用e返回T的根 返回OK 否則返回ERROR e無定義 if BiTreeEmpty T T空 return ERROR else e T 0 return OK TElemType Value SqBiTree T position e 初始條件 二元樹 T存在 e是T中某個結點 的位置 操作結果 返回處於位置e 層 本層序號 的結點的值 return T int pow 2 e level 1 e order 2 Status Assign SqBiTree T position e TElemType value 初始條件 二叉樹T存在 e是T中某個結點 的位置 操作結果 給處於位置e 層 本層序號 的結點賦新值value int i int pow 2 e level 1 e order 2 將層 本層序號轉為矩陣的序號 if value Nil amp amp T i 1 2 1 Nil 給葉子賦非空值但雙親為空 return ERROR else if value Nil amp amp T i 2 1 Nil T i 2 2 Nil 給雙親賦空值但有葉子 不空 return ERROR T i value return OK TElemType Parent SqBiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 若e是T的非根結點 則返回它的雙親 否則返回 空 int i if T 0 Nil 空樹 return Nil for i 1 i lt MAX TREE SIZE 1 i if T i e 找到e return T i 1 2 1 return Nil 沒找到e TElemType LeftChild SqBiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的左孩子 若e無左孩子 則返回 空 int i if T 0 Nil 空樹 return Nil for i 0 i lt MAX TREE SIZE 1 i if T i e 找到e return T i 2 1 return Nil 沒找到e TElemType RightChild SqBiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的右孩子 若e無右孩子 則返回 空 int i if T 0 Nil 空樹 return Nil for i 0 i lt MAX TREE SIZE 1 i if T i e 找到e return T i 2 2 return Nil 沒找到e TElemType LeftSibling SqBiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的左兄弟 若e是T的左孩子或無左兄弟 則返回 空 int i if T 0 Nil 空樹 return Nil for i 1 i lt MAX TREE SIZE 1 i if T i e amp amp i 2 0 找到e且其序號為偶數 是右孩子 return T i 1 return Nil 沒找到e TElemType RightSibling SqBiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的右兄弟 若e是T的右孩子或無右兄弟 則返回 空 int i if T 0 Nil 空樹 return Nil for i 1 i lt MAX TREE SIZE 1 i if T i e amp amp i 2 找到e且其序號為奇數 是左孩子 return T i 1 return Nil 沒找到e void Move SqBiTree q int j SqBiTree T int i InsertChild 用到 加 把從q的j結點開始的子樹移為從T的i結點開始的子樹 if q 2 j 1 Nil q的左子樹不空 Move q 2 j 1 T 2 i 1 把q的j結點的左子樹移為T的i結點的左子樹 if q 2 j 2 Nil q的右子樹不空 Move q 2 j 2 T 2 i 2 把q的j結點的右子樹移為T的i結點的右子樹 T i q j 把q的j結點移為T的i結點 q j Nil 把q的j結點置空 void InsertChild SqBiTree T TElemType p int LR SqBiTree c 初始條件 二叉樹T存在 p是T中某個結點的值 LR為0或1 非空二叉樹c與T不相交且右子樹為空 操作結果 根據LR為0或1 插入c為T中p結點的左或右子樹 p結點的原有左或右子樹則成為c的右子樹 int j k i 0 for j 0 j lt int pow 2 BiTreeDepth T 1 j 查找p的序號 if T j p j為p的序號 break k 2 j 1 LR k為p的左或右孩子的序號 if T k Nil p原來的左或右孩子不空 Move T k T 2 k 2 把從T的k結點開始的子樹移為從k結點的右子樹開始的子樹 Move c i T k 把從c的i結點開始的子樹移為從T的k結點開始的子樹 typedef int QElemType 設佇列元素類型為整型 序號 include c3 2 h 鏈佇列 include bo3 2 c 鏈佇列的基本操作 Status DeleteChild SqBiTree T position p int LR 初始條件 二叉樹T存在 p指向T中某個結點 LR為1或0 操作結果 根據LR為1或0 刪除T中p所指結點的左或右子樹 int i Status k OK 佇列不空的標誌 LinkQueue q InitQueue amp q 初始化佇列 用於存放待刪除的結點 i int pow 2 p level 1 p order 2 將層 本層序號轉為矩陣的序號 if T i Nil 此結點空 return ERROR i i 2 1 LR 待刪除子樹的根結點在矩陣中的序號 while k if T 2 i 1 Nil 左結點不空 EnQueue amp q 2 i 1 入隊左結點的序號 if T 2 i 2 Nil 右結點不空 EnQueue amp q 2 i 2 入隊右結點的序號 T i Nil 刪除此結點 k DeQueue amp q amp i 佇列不空 return OK void VisitFunc TElemType 函數變數 void PreTraverse SqBiTree T int e PreOrderTraverse 調用 VisitFunc T e if T 2 e 1 Nil 左子樹不空 PreTraverse T 2 e 1 if T 2 e 2 Nil 右子樹不空 PreTraverse T 2 e 2 void PreOrderTraverse SqBiTree T void Visit TElemType 初始條件 二叉樹存在 Visit是對結點操作的應用函數 操作結果 先序遍歷T 對每個結點調用函數Visit一次且僅一次 VisitFunc Visit if BiTreeEmpty T 樹不空 PreTraverse T 0 printf n void InTraverse SqBiTree T int e InOrderTraverse 調用 if T 2 e 1 Nil 左子樹不空 InTraverse T 2 e 1 VisitFunc T e if T 2 e 2 Nil 右子樹不空 InTraverse T 2 e 2 void InOrderTraverse SqBiTree T void Visit TElemType 初始條件 二叉樹存在 Visit是對結點操作的應用函數 操作結果 中序遍歷T 對每個結點調用函數Visit一次且僅一次 VisitFunc Visit if BiTreeEmpty T 樹不空 InTraverse T 0 printf n void PostTraverse SqBiTree T int e PostOrderTraverse 調用 if T 2 e 1 Nil 左子樹不空 PostTraverse T 2 e 1 if T 2 e 2 Nil 右子樹不空 PostTraverse T 2 e 2 VisitFunc T e void PostOrderTraverse SqBiTree T void Visit TElemType 初始條件 二叉樹T存在 Visit是對結點操作的應用函數 操作結果 後序遍歷T 對每個結點調用函數Visit一次且僅一次 VisitFunc Visit if BiTreeEmpty T 樹不空 PostTraverse T 0 printf n void LevelOrderTraverse SqBiTree T void Visit TElemType 層序遍歷二叉樹 int i MAX TREE SIZE 1 j while T i Nil i 找到最後一個非空結點的序號 for j 0 j lt i j 從根結點起 按層序遍歷二叉樹 if T j Nil Visit T j 只遍歷非空的結點 printf n void Print SqBiTree T 逐層 按本層序號輸出二叉樹 int j k position p TElemType e for j 1 j lt BiTreeDepth T j printf 第 d層 j for k 1 k lt pow 2 j 1 k p level j p order k e Value T p if e Nil printf d form k e printf n 二叉鏈表存儲表示 编辑 基於鏈表的二叉樹邏輯結構示意 在使用記錄或記憶體位址指標的程式設計語言中 二叉樹通常用樹結點結構來存儲 有時也包含指向唯一的父節點的指標 如果一個結點的子結點個數小於2 一些子結點指針可能為空值 或者為特殊的哨兵結點 使用鏈表能避免順序儲存浪費空間的問題 演算法和結構相對簡單 但使用二叉鏈表 由於缺乏父鏈的指引 在找回父節點時需要重新掃描樹得知父節點的節點位址 存儲結構 编辑 二叉樹的二叉鏈表存儲表示 typedef struct BiTNode TElemType data struct BiTNode lchild rchild 左右孩子指針 BiTNode BiTree 基本操作 编辑 基於C C 的實現演算法 二叉樹的二叉鏈表存儲的基本操作 22個 define ClearBiTree DestroyBiTree 清空二叉樹和銷毀二叉樹的操作一樣 include func6 3 c 包括InitBiTree DestroyBiTree PreOrderTraverse 和InOrderTraverse 4函數 void CreateBiTree BiTree T 演算法6 4 按先序次序輸入二叉樹中結點的值 可為字元型或整型 在主程中定義 構造二叉鏈表表示的二叉樹T 變數Nil表示空 子 樹 有改動 TElemType ch scanf form amp ch if ch Nil 空 T NULL else T BiTree malloc sizeof BiTNode 生成根結點 if T exit OVERFLOW T gt data ch CreateBiTree amp T gt lchild 構造左子樹 CreateBiTree amp T gt rchild 構造右子樹 Status BiTreeEmpty BiTree T 初始條件 二叉樹T存在 操作結果 若T為空二叉樹 則返回TRUE 否則FALSE if T return FALSE else return TRUE int BiTreeDepth BiTree T 初始條件 二叉樹T存在 操作結果 返回T的深度 int i j if T NULL 如果T NULL 这样写便于理解 当然也可以写成if T return 0 空樹深度為0 if T gt lchild i BiTreeDepth T gt lchild i為左子樹的深度 else i 0 if T gt rchild j BiTreeDepth T gt rchild j為右子樹的深度 else j 0 return i gt j i 1 j 1 T的深度為其左右子樹的深度中的大者 1 TElemType Root BiTree T 初始條件 二叉樹T存在 操作結果 返回T的根 if BiTreeEmpty T return Nil else return T gt data TElemType Value BiTree p 初始條件 二叉樹T存在 p指向T中某個結點 操作結果 返回p所指結點的值 return p gt data void Assign BiTree p TElemType value 給p所指結點賦值為value p gt data value typedef BiTree QElemType 設佇列元素為二叉樹的指針類型 include c3 2 h 鏈佇列 include bo3 2 c 鏈佇列的基本操作 TElemType Parent BiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 若e是T的非根結點 則返回它的雙親 否則返回 空 LinkQueue q QElemType a if T 非空樹 InitQueue amp q 初始化佇列 EnQueue amp q T 樹根指針入隊 while QueueEmpty q 隊不空 DeQueue amp q amp a 出隊 佇列元素賦給a if a gt lchild amp amp a gt lchild gt data e a gt rchild amp amp a gt rchild gt data e 找到e 是其左或右孩子 return a gt data 返回e的雙親的值 else 沒找到e 則入隊其左右孩子指針 如果非空 if a gt lchild EnQueue amp q a gt lchild if a gt rchild EnQueue amp q a gt rchild return Nil 樹空或沒找到e BiTree Point BiTree T TElemType s 返回二叉樹T中指向元素值為s的結點的指標 另加 LinkQueue q QElemType a if T 非空樹 InitQueue amp q 初始化佇列 EnQueue amp q T 根指針入隊 while QueueEmpty q 隊不空 DeQueue amp q amp a 出隊 佇列元素賦給a if a gt data s return a if a gt lchild 有左孩子 EnQueue amp q a gt lchild 入隊左孩子 if a gt rchild 有右孩子 EnQueue amp q a gt rchild 入隊右孩子 return NULL TElemType LeftChild BiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的左孩子 若e無左孩子 則返回 空 BiTree a if T 非空樹 a Point T e a是結點e的指針 if a amp amp a gt lchild T中存在結點e且e存在左孩子 return a gt lchild gt data 返回e的左孩子的值 return Nil 其餘情況返回空 TElemType RightChild BiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的右孩子 若e無右孩子 則返回 空 BiTree a if T 非空樹 a Point T e a是結點e的指針 if a amp amp a gt rchild T中存在結點e且e存在右孩子 return a gt rchild gt data 返回e的右孩子的值 return Nil 其餘情況返回空 TElemType LeftSibling BiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的左兄弟 若e是T的左孩子或無左兄弟 則返回 空 TElemType a BiTree p if T 非空樹 a Parent T e a為e的雙親 if a Nil 找到e的雙親 p Point T a p為指向結點a的指標 if p gt lchild amp amp p gt rchild amp amp p gt rchild gt data e p存在左右孩子且右孩子是e return p gt lchild gt data 返回p的左孩子 e的左兄弟 return Nil 其餘情況返回空 TElemType RightSibling BiTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的右兄弟 若e是T的右孩子或無右兄弟 則返回 空 TElemType a BiTree p if T 非空樹 a Parent T e a為e的雙親 if a Nil 找到e的雙親 p Point T a p為指向結點a的指標 if p gt lchild amp amp p gt rchild amp amp p gt lchild gt data e p存在左右孩子且左孩子是e return p gt rchild gt data 返回p的右孩子 e的右兄弟 return Nil 其餘情況返回空 Status InsertChild BiTree p int LR BiTree c 形參T無用 初始條件 二叉樹T存在 p指向T中某個結點 LR為0或1 非空二叉樹c與T不相交且右子樹為空 操作結果 根據LR為0或1 插入c為T中p所指結點的左或右子樹 p所指結點的 原有左或右子樹則成為c的右子樹 if p p不空 if LR 0 c gt rchild p gt lchild p gt lchild c else LR 1 c gt rchild p gt rchild p gt rchild c return OK return ERROR p空 Status DeleteChild BiTree p int LR 形參T無用 初始條件 二叉樹T存在 p指向T中某個結點 LR為0或1 操作結果 根據LR為0或1 刪除T中p所指結點的左或右子樹 if p p不空 if LR 0 刪除左子樹 ClearBiTree amp p gt lchild else 刪除右子樹 ClearBiTree amp p gt rchild return OK return ERROR p空 typedef BiTree SElemType 設棧元素為二叉樹的指針類型 include c3 1 h 順序棧 include bo3 1 c 順序棧的基本操作 void InOrderTraverse1 BiTree T void Visit TElemType 採用二叉鏈表存儲結構 Visit是對資料元素操作的應用函數 演算法6 3 有改動 中序遍歷二叉樹T的非遞迴演算法 利用棧 對每個資料元素調用函數Visit SqStack S InitStack amp S while T StackEmpty S if T 根指針進棧 遍歷左子樹 Push amp S T T T gt lchild else 根指針退棧 訪問根結點 遍歷右子樹 Pop amp S amp T Visit T gt data T T gt rchild printf n void InOrderTraverse2 BiTree T void Visit TElemType 採用二叉鏈表存儲結構 Visit是對資料元素操作的應用函數 演算法6 2 有改動 中序遍歷二叉樹T的非遞迴演算法 利用棧 對每個資料元素調用函數Visit SqStack S BiTree p InitStack amp S Push amp S T 根指針進棧 while StackEmpty S while GetTop S amp p amp amp p Push amp S p gt lchild 向左走到盡頭 Pop amp S amp p 空指針退棧 if StackEmpty S 訪問結點 向右一步 Pop amp S amp p Visit p gt data Push amp S p gt rchild printf n void PostOrderTraverse BiTree T void Visit TElemType 初始條件 二叉樹T存在 Visit是對結點操作的應用函數 操作結果 後序遞迴遍歷T 對每個結點調用函數Visit一次且僅一次 if T T不空 PostOrderTraverse T gt lchild Visit 先後序遍歷左子樹 PostOrderTraverse T gt rchild Visit 再後序遍歷右子樹 Visit T gt data 最後訪問根結點 void LevelOrderTraverse BiTree T void Visit TElemType 初始條件 二叉樹T存在 Visit是對結點操作的應用函數 操作結果 層序遞迴遍歷T 利用佇列 對每個結點調用函數Visit一次且僅一次 LinkQueue q QElemType a if T InitQueue amp q 初始化佇列q EnQueue amp q T 根指針入隊 while QueueEmpty q 佇列不空 DeQueue amp q amp a 出隊元素 指標 賦給a Visit a gt data 訪問a所指結點 if a gt lchild NULL a有左孩子 EnQueue amp q a gt lchild 入隊a的左孩子 if a gt rchild NULL a有右孩子 EnQueue amp q a gt rchild 入隊a的右孩子 printf n 三叉鏈表存儲表示 编辑 基於三叉鏈表的二叉樹的邏輯結構 改進於二叉鏈表 增加父節點的指引 能更好地實現節點間的訪問 不過演算法相對複雜 當二叉樹用三叉鏈表表示時 有N個結點 就會有N 2個空指針 存儲結構 编辑 二叉樹的三叉鏈表存儲表示 typedef struct BiTPNode TElemType data struct BiTPNode parent lchild rchild 父 左右孩子指針 BiTPNode BiPTree 基本操作 编辑 基於C C 的實現演算法 二叉樹的三叉鏈表存儲的基本操作 21個 define ClearBiTree DestroyBiTree 清空二叉樹和銷毀二叉樹的操作一樣 void InitBiTree BiPTree T 操作結果 構造空二叉樹T T NULL void DestroyBiTree BiPTree T 初始條件 二叉樹T存在 操作結果 銷毀二叉樹T if T 非空樹 if T gt lchild 有左孩子 DestroyBiTree amp T gt lchild 銷毀左孩子子樹 if T gt rchild 有右孩子 DestroyBiTree amp T gt rchild 銷毀右孩子子樹 free T 釋放根結點 T NULL 空指針賦0 void CreateBiTree BiPTree T 按先序次序輸入二叉樹中結點的值 可為字元型或整型 在主程中定義 構造三叉鏈表表示的二叉樹T TElemType ch scanf form amp ch if ch Nil 空 T NULL else T BiPTree malloc sizeof BiTPNode 動態生成根結點 if T exit OVERFLOW T gt data ch 給根結點賦值 T gt parent NULL 根結點無雙親 CreateBiTree amp T gt lchild 構造左子樹 if T gt lchild 有左孩子 T gt lchild gt parent T 給左孩子的雙親域賦值 CreateBiTree amp T gt rchild 構造右子樹 if T gt rchild 有右孩子 T gt rchild gt parent T 給右孩子的雙親域賦值 Status BiTreeEmpty BiPTree T 初始條件 二叉樹T存在 操作結果 若T為空二叉樹 則返回TRUE 否則FALSE if T return FALSE else return TRUE int BiTreeDepth BiPTree T 初始條件 二叉樹T存在 操作結果 返回T的深度 int i j if T return 0 空樹深度為0 if T gt lchild i BiTreeDepth T gt lchild i為左子樹的深度 else i 0 if T gt rchild j BiTreeDepth T gt rchild j為右子樹的深度 else j 0 return i gt j i 1 j 1 T的深度為其左右子樹的深度中的大者 1 TElemType Root BiPTree T 初始條件 二叉樹T存在 操作結果 返回T的根 if T return T gt data else return Nil TElemType Value BiPTree p 初始條件 二叉樹T存在 p指向T中某個結點 操作結果 返回p所指結點的值 return p gt data void Assign BiPTree p TElemType value 給p所指結點賦值為value p gt data value typedef BiPTree QElemType 設佇列元素為二叉樹的指針類型 include c3 2 h 鏈佇列 include bo3 2 c 鏈佇列的基本操作 BiPTree Point BiPTree T TElemType e 返回二叉樹T中指向元素值為e的結點的指標 加 LinkQueue q QElemType a if T 非空樹 InitQueue amp q 初始化佇列 EnQueue amp q T 根結點入隊 while QueueEmpty q 隊不空 DeQueue amp q amp a 出隊 佇列元素賦給a if a gt data e return a if a gt lchild 有左孩子 EnQueue amp q a gt lchild 入隊左孩子 if a gt rchild 有右孩子 EnQueue amp q a gt rchild 入隊右孩子 return NULL TElemType Parent BiPTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 若e是T的非根結點 則返回它的雙親 否則返回 空 BiPTree a if T 非空樹 a Point T e a是結點e的指針 if a amp amp a T T中存在結點e且e是非根結點 return a gt parent gt data 返回e的雙親的值 return Nil 其餘情況返回空 TElemType LeftChild BiPTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的左孩子 若e無左孩子 則返回 空 BiPTree a if T 非空樹 a Point T e a是結點e的指針 if a amp amp a gt lchild T中存在結點e且e存在左孩子 return a gt lchild gt data 返回e的左孩子的值 return Nil 其餘情況返回空 TElemType RightChild BiPTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的右孩子 若e無右孩子 則返回 空 BiPTree a if T 非空樹 a Point T e a是結點e的指針 if a amp amp a gt rchild T中存在結點e且e存在右孩子 return a gt rchild gt data 返回e的右孩子的值 return Nil 其餘情況返回空 TElemType LeftSibling BiPTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的左兄弟 若e是T的左孩子或無左兄弟 則返回 空 BiPTree a if T 非空樹 a Point T e a是結點e的指針 if a amp amp a T amp amp a gt parent gt lchild amp amp a gt parent gt lchild a T中存在結點e且e存在左兄弟 return a gt parent gt lchild gt data 返回e的左兄弟的值 return Nil 其餘情況返回空 TElemType RightSibling BiPTree T TElemType e 初始條件 二叉樹T存在 e是T中某個結點 操作結果 返回e的右兄弟 若e是T的右孩子或無右兄弟 則返回 空 BiPTree a if T 非空樹 a Point T e a是結點e的指針 if a amp amp a T amp amp a gt parent gt rchild amp amp a gt parent gt rchild a T中存在結點e且e存在右兄弟 return a gt parent gt rchild gt data 返回e的右兄弟的值 return Nil 其餘情況返回空 Status InsertChild BiPTree p int LR BiPTree c 形參T無用 初始條件 二叉樹T存在 p指向T中某個結點 LR為0或1 非空二叉樹c與T不相交且右子樹為空 操作結果 根據LR為0或1 插入c為T中p所指結點的左或右子樹 p所指結點 的原有左或右子樹則成為c的右子樹 if p p不空 if LR 0 c gt rchild p gt lchild if c gt rchild c有右孩子 p原有左孩子 c gt rchild gt parent c p gt lchild c c gt parent p else LR 1 c gt rchild p gt rchild if c gt rchild c有右孩子 p原有右孩子 c gt rchild gt parent c p gt rchild c c gt parent p return OK return ERROR p空 Status DeleteChild BiPTree p int LR 形參T無用 初始條件 二叉樹T存在 p指向T中某個結點 LR為0或1 操作結果 根據LR為0或1 刪除T中p所指結點的左或右子樹 if p p不空 if LR 0 刪除左子樹 ClearBiTree amp p gt lchild else 刪除右子樹 ClearBiTree amp p gt rchild return OK return ERROR p空 void PreOrderTraverse BiPTree T void Visit BiPTree 先序遞迴遍歷二叉樹T if T Visit T 先訪問根結點 PreOrderTraverse T gt lchild Visit 再先序遍歷左子樹 PreOrderTraverse T gt rchild Visit 最後先序遍歷右子樹 void InOrderTraverse BiPTree T void Visit BiPTree 中序遞迴遍歷二叉樹T if T InOrderTraverse T gt lchild Visit 中序遍歷左子樹 Visit T 再訪問根結點 InOrderTraverse T gt rchild Visit 最後中序遍歷右子樹 void PostOrderTraverse BiPTree T void Visit BiPTree 後序遞迴遍歷二叉樹T if T PostOrderTraverse T gt lchild Visit 後序遍歷左子樹 PostOrderTraverse T gt rchild Visit 後序遍歷右子樹 Visit T 最後訪問根結點 void LevelOrderTraverse BiPTree T void Visit BiPTree 層序遍歷二叉樹T 利用佇列 LinkQueue q QElemType a if T InitQueue amp q EnQueue amp q T while QueueEmpty q DeQueue amp q amp a Visit a if a gt lchild NULL EnQueue amp q a gt lchild if a gt rchild NULL EnQueue amp q a gt rchild 遍历 编辑主条目 樹的遍歷 我們經常希望訪問樹中的每一個結點並且查看它的值 有很多常見的順序來訪問所有的結點 而且每一種都有有用的性質 深度優先遍歷 编辑 参见 深度優先搜索 在深度優先順序中 我們希望從根結點訪問最遠的結點 和圖的深度優先搜索不同的是 不需記住訪問過的每一個結點 因為樹中不會有環 前序 中序和後序遍歷都是深度優先遍歷的特例 前 先 序 中序 後序遍歷 编辑 遍歷二叉樹 L D R分別表示遍歷左子樹 訪問根結點和遍歷右子樹 則先 根 序遍歷二叉樹的順序是DLR 中 根 序遍歷二叉樹的順序是LDR 後 根 序遍歷二叉樹的順序是LRD 還有按層遍歷二叉樹 這些方法的時間複雜度都是O n n為結點個數 如果T2是由有序樹T轉換而來的二叉樹 那麼T中結點的前序就是T2中結點的前序 T中結點的後序就是T2中結點的中序 任何一棵二叉樹的葉結點在先序 中序和後序遍歷中的相對次序不發改變 設n m為一棵二叉樹上的兩個結點 在中序遍歷時 n在m前的條件是n在m的左方 前序序列和中序序列相同的二叉樹為空樹或任一結點均無左孩子的非空二叉樹 中序序列和後序序列相同的二叉樹為空樹或任一結點均無右孩子的非空二叉樹 前序序列和後序序列相同的二叉樹為空樹或僅有一個結點的二叉樹 假設我們有一個包含值的value和指向兩個子結點的left和right的樹結點結構 我們可以寫出這樣的過程 visit node print node value if node left null then visit node left if node right null then visit node right 這樣會用前序打印出樹中的值 在前序 每個結點在訪問它的子結點之前訪問 類似地 如果打印語句在最後 每個結點在訪問他的子節點之後訪問 樹中的值會用後序來打印 在這兩種情況中 左子樹中的值比右子樹中得值先打印 visit node if node left null then visit node left print node value if node right null then visit node right 最後 上面的中序遍歷 每個結點在訪問左子樹和右子樹之間訪問 這在遍歷二叉搜尋樹時很常用 因為它能用遞增的順序來遍歷所有的值 為什麼呢 如果n是二叉搜尋樹的結點 那麼n的左子樹的所有結點的值都比n的值要小 而且n的右子樹的所有節點的值都比n的值要大 因此 如果我們順序遍歷左子樹 然後訪問n 然後順序遍歷右子樹 我們就已經循序存取了整個樹 后序遍历伪代码如下 visit node if node left null then visit node left if node right null then visit node right print node value BinaryTree 在這個二叉樹中 前序遍歷的結果 M G D B A C F E J H I K L S P O N Q R W U T V X Z Y 後序遍歷的結果 A C B E F D I H L K J G N O R Q P T V U Y Z X W S M 中序遍歷的結果 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z以上的遞迴演算法使用與樹的高度成比例的棧空間 如果我們在每個結點中存儲指向父結點的指標 那樣可以使用反覆運算演算法 只使用常數空間實現所有這些遍歷 然而 指向父結點的指標佔用更多的空間 這只在需要指向父節點的指標或棧空間有限時才使用 例如 這是一個中序遍歷的反覆運算演算法 visit root prev null current root next null while current null if prev current parent prev current next current left if next null or prev current left print current value prev current next current right if next null or prev current right prev current next current parent current next 用二叉樹表示下述運算式 a b c d e f 先序遍歷的序列是 a b cd ef 中序遍歷的序列是 a b c d e f 後序遍歷的序列是 abcd ef 廣度優先遍歷 编辑 参见 廣度優先搜索 和深度優先遍歷不同 廣度優先遍歷會先訪問離根節點最近的節點 二叉樹的廣度優先遍歷又稱按層次遍歷 演算法借助佇列實現 轉換自多叉樹 编辑一般有序樹可映射为二叉樹 但反之未必成立 n叉樹轉換為二叉樹的方法 二叉樹中結點x的左子結點為n叉樹中結點x的左子結點 二叉樹中結點x的右子結點為n叉樹中結點x的第一個右邊的同級結點y 二叉树当且仅当根节点没有右子结点时可转换为n叉树 例如 在左邊的樹中 A有6個子結點 B C D E F G 它能被轉換成右邊的二叉樹 將一棵樹轉換為二叉樹的方法 在兄弟之間加一連線 對每個結點 除了其左孩子外 去除其與其餘孩子之間的聯繫 以樹的根結點為軸心 將整樹順時針轉45度 樹的二叉鏈表標記法 孩子兄弟標記法 编辑 樹的二叉鏈表標記法 孩子兄弟標記法 是樹和二叉樹轉換的媒介 存儲結構 编辑 二叉樹與森林相互轉換的邏輯示意 樹的二叉鏈表 孩子 兄弟 存儲表示 typedef struct CSNode TElemType data struct CSNode firstchild nextsibling CSNode CSTree 基本操作 编辑 基於C C 的演算法實現 樹的二叉鏈表 孩子 兄弟 存儲的基本操作 17個 define ClearTree DestroyTree 二者操作相同 include func6 2 c 包括PreOrderTraverse void InitTree CSTree T 操作結果 構造空樹T T NULL void DestroyTree CSTree T 初始條件 樹T存在 操作結果 銷毀樹T if T if T gt firstchild T有長子 DestroyTree amp T gt firstchild 銷毀T的長子為根結點的子樹 if T gt nextsibling T有下一個兄弟 DestroyTree amp T gt nextsibling 銷毀T的下一個兄弟為根結點的子樹 free T 釋放根結點 T NULL typedef CSTree QElemType 定義佇列元素類型 include c3 2 h 定義LinkQueue類型 鏈佇列 include bo3 2 c LinkQueue類型的基本操作 void CreateTree CSTree T 構造樹T char c 20 臨時存放孩子結點 設不超過20個 的值 CSTree p p1 LinkQueue q int i l InitQueue amp q printf 請輸入根結點 字元型 空格為空 scanf c c amp c 0 if c 0 Nil 非空樹 T CSTree malloc sizeof CSNode 建立根結點 T gt data c 0 T gt nextsibling NULL EnQueue amp q T 入隊根結點的指針 while QueueEmpty q 隊不空 DeQueue amp q amp p 出隊一個結點的指標 printf 請按長幼順序輸入結點 c的所有孩子 p gt data gets c l strlen c if l gt 0 有孩子 p1 p gt firstchild CSTree malloc sizeof CSNode 建立長子結點 p1 gt data c 0 for i 1 i lt l i p1 gt nextsibling CSTree malloc sizeof CSNode 建立下一個兄弟結點 EnQueue amp q p1 入隊上一個結點 p1 p1 gt nextsibling p1 gt data c i p1 gt nextsibling NULL EnQueue amp q p1 入隊最後一個結點 else p gt firstchild NULL 長子指針為空 else T NULL 空樹 Status TreeEmpty CSTree T 初始條件 樹T存在 操作結果 若T為空樹 則返回TURE 否則返回FALSE if T T不空 return FALSE else return TRUE int TreeDepth CSTree T 初始條件 樹T存在 操作結果 返回T的深度 CSTree p int depth max 0 if T 樹空 return 0 if T gt firstchild 樹無長子 return 1 for p T gt firstchild p p p gt nextsibling 求子樹深度的最大值 depth TreeDepth p if depth gt max max depth return max 1 樹的深度 子樹深度最大值 1 TElemType Value CSTree p 返回p所指結點的值 return p gt data TElemType Root CSTree T 初始條件 樹T存在 操作結果 返回T的根 if T return Value T else return Nil CSTree Point CSTree T TElemType s 返回二叉鏈表 孩子 兄弟 樹T中指向元素值為s的結點的指標 另加 LinkQueue q QElemType a if T 非空樹 InitQueue amp q 初始化佇列 EnQueue amp q T 根結點入隊 while QueueEmpty q 隊不空 DeQueue amp q amp a 出隊 佇列元素賦給a if a gt data s return a if a gt firstchild 有長子 EnQueue amp q a gt firstchild 入隊長子 if a gt nextsibling 有下一個兄弟 EnQueue amp q a gt nextsibling 入隊下一個兄弟 return NULL Status Assign CSTree T TElemType cur e TElemType value 初始條件 樹T存在 cur e是樹T中結點的值 操作結果 改cur e為value CSTree p if T 非空樹 p Point T cur e p為cur e的指針 if p 找到cur e p gt data value 賦新值 return OK return ERROR 樹空或沒找到 TElemType Parent CSTree T TElemType cur e 初始條件 樹T存在 cur e是T中某個結點 操作結果 若cur e是T的非根結點 則返回它的雙親 否則函數值為 空 CSTree p t LinkQueue q InitQueue amp q if T 樹非空 if Value T cur e 根結點值為cur e return Nil EnQueue amp q T 根結點入隊 while QueueEmpty q DeQueue amp q amp p if p gt firstchild p有長子 if p gt firstchild gt data cur e 長子為cur e return Value p 返回雙親 t p 雙親指針賦給t p p gt firstchild p指向長子 EnQueue amp q p 入隊長子 while p gt nextsibling 有下一個兄弟 p p gt nextsibling p指向下一個兄弟 if Value p cur e 下一個兄弟為cur e return Value t 返回雙親 EnQueue amp q p 入隊下一個兄弟 return Nil 樹空或沒找到cur e TElemType LeftChild CSTree T TElemType cur e 初始條件 樹T存在 cur e是T中某個結點 操作結果 若cur e是T的非葉子結點 則返回它的最左孩子 否則返回 空 CSTree f f Point T cur e f指向結點cur e if f amp amp f gt firstchild 找到結點cur e且結點cur e有長子 return f gt firstchild gt data else return Nil TElemType RightSibling CSTree T TElemType cur e 初始條件 樹T存在 cur e是T中某個結點 操作結果 若cur e有右兄弟 則返回它的右兄弟 否則返回 空 CSTree f f Point T cur e f指向結點cur e if f amp amp f gt nextsibling 找到結點cur e且結點cur e有右兄弟 return f gt nextsibling gt data else return Nil 樹空 Status InsertChild CSTree T CSTree p int i CSTree c 初始條件 樹T存在 p指向T中某個結點 1 i p所指結點的度 1 非空樹c與T不相交 操作結果 插入c為T中p結點的第i棵子樹 因為p所指結點的位址不會改變 故p不需是參考類型 int j if T T不空 if i 1 插入c為p的長子 c gt nextsibling p gt firstchild p的原長子現是c的下一個兄弟 c本無兄弟 p gt firstchild c else 找插入點 p p gt firstchild 指向p的長子 j 2 while p amp amp i gt j p p gt nextsibling j if j i 找到插入位置 c gt nextsibling p gt nextsibling p gt nextsibling c else p原有孩子數小於i 1 return ERROR return OK else T空 return ERROR Status DeleteChild CSTree T CSTree p int i 初始條件 樹T存在 p指向T中某個結點 1 i p所指結點的度 操作結果 刪除T中p所指結點的第i棵子樹 因為p所指結點的位址不會改變 故p不需是參考類型 CSTree b int j if T T不空 if i 1 刪除長子 b p gt firstchild p gt firstchild b gt nextsibling p的原次子現是長子 b gt nextsibling NULL DestroyTree amp b else 刪除非長子 p p gt firstchild p指向長子 j 2 while p amp amp i gt j p p gt nextsibling j if j i 找到第i棵子樹 b p gt nextsibling p gt nextsibling b gt nextsibling b gt nextsibling NULL DestroyTree amp b else p原有孩子數小於i return ERROR return OK else return ERROR void PostOrderTraverse CSTree T void Visit TElemType 後根遍歷孩子 兄弟二叉鏈表結構的樹T CSTree p if T if T gt firstchild 有長子 PostOrderTraverse T gt firstchild Visit 後根遍歷長子子樹 p T gt firstchild gt nextsibling p指向長子的下一個兄弟 while p PostOrderTraverse p Visit 後根遍歷下一個兄弟子樹 p p gt nextsibling p指向再下一個兄弟 Visit Value T 最後訪問根結點 void LevelOrderTraverse CSTree T void Visit TElemType 層序遍歷孩子 兄弟二叉鏈表結構的樹T CSTree p LinkQueue q InitQueue amp q if T Visit Value T 先訪問根結點 EnQueue amp q T 入隊根結點的指針 while QueueEmpty q 隊不空 DeQueue amp q amp p 出隊一個結點的指標 if p gt firstchild 有長子 p p gt firstchild Visit Value p 訪問長子結點 EnQueue amp q p 入隊長子結點的指針 while p gt nextsibling 有下一個兄弟 p p gt nextsibling Visit Value p 訪問下一個兄弟 EnQueue amp q p 入隊兄弟結點的指針 線索二叉樹 编辑主条目 線索二叉樹 線索二叉樹 英語 threaded binary tree 保留遍歷時結點在任一序列的前驅和後繼的資訊 若結點有左子樹 則其lchild域指示其左孩子 否則令lchild域指示其前驅 若結點有右子樹 則其rchild域指示其右孩子 否則令rchild指示其後繼 還需在結點結構中增加兩個標誌域LTag和RTag LTag 0時 lchild域指示結點的左孩子 LTag 1時 lchild域指示結點的前驅 RTag 0時 rchild域指示結點的右孩子 RTag 1時 rchild域指示結點的後繼 以這種結點結構構成的二叉鏈表作為二叉樹的存儲結構 叫做線索鏈表 其中指向結點前驅和後繼的指標叫做線索 加上線索的二叉樹稱為線索二叉樹 對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化 若對二叉樹進行中序遍歷 則所得的線索二叉樹稱為中序線索二叉樹 線索鏈表稱為為中序線索鏈表 線索二叉樹是一種物理結構 在中序線索樹找結點後繼的規律是 若其右標誌為1 則右鏈為線索 指示其後繼 否則遍歷其右子樹時訪問的第一個結點 右子樹最左下的結點 為其後繼 找結點前驅的規律是 若其左標誌為1 則左鏈為線索 指示其前驅 否則遍歷左子樹時最後訪問的一個結點 左子樹中最右下的結點 為其前驅 在後序線索樹中找到結點的後繼分三種情況 若結點是二叉樹的根 則其後繼為空 若結點是其雙親的右孩子 或是其雙親的左孩子且其雙親沒有右子樹 則其後繼即為雙親結點 若結點是其雙親的左孩子 且其雙親有右子樹 則其後繼為雙親右子樹上按後序遍歷列出的第一個結點 二叉線索存儲表示 编辑 存儲結構 编辑 二叉樹的二叉線索存儲表示 在線索鏈表上添加一個頭結點 並令其lchild域的指標指向二叉樹的根結點 其rchild域的指標指向中序遍歷時訪問的最後一個結點 令二叉樹中序序列中的第一個結點的lchild域指標和最後一個結點的rchild域的指標均指向頭結點 這樣就建立了一個雙向線索鏈表 二叉樹常採用二叉鏈表方式存儲 二叉樹的二叉線索存儲表示 typedef enum Link Thread PointerTag Link 0 指針 Thread 1 線索 typedef struct BiThrNode TElemType data struct BiThrNode lchild rchild 左右孩子指針 PointerTag LTag RTag 左右標誌 BiThrNode BiThrTree 基本操作 编辑 基於C C 的演算法實現 二叉樹的二叉線索存儲的基本操作 void CreateBiThrTree BiThrTree T 按先序輸入線索二叉樹中結點的值 構造線索二叉樹T 0 整型 空格 字元型 表示空結點 TElemType ch scanf form amp ch if ch Nil T NULL else T BiThrTree malloc sizeof BiThrNode 生成根結點 先序 if T exit OVERFLOW T gt data ch 給根結點賦植 CreateBiThrTree amp T gt lchild 遞迴構造左子樹 if T gt lchild 有左孩子 T gt LTag Link 給左標誌賦值 指標 CreateBiThrTree amp T gt rchild 遞迴構造右子樹 if T gt rchild 有右孩子 T gt RTag Link 給右標誌賦值 指標 BiThrTree pre 全域變數 始終指向剛剛訪問過的結點 void InThreading BiThrTree p 通過中序遍歷進行中序線索化 線索化之後pre指向最後一個結點 演算法6 7 if p 線索二叉樹不空 InThreading p gt lchild 遞迴左子樹線索化 if p gt lchild 沒有左孩子 p gt LTag Thread 左標誌為線索 前驅 p gt lchild pre 左孩子指標指向前驅 if pre amp amp pre gt rchild 前驅不爲空并且前驅沒有右孩子 pre gt RTag Thread 前驅的右標誌為線索 後繼 pre gt rchild p 前驅右孩子指標指向其後繼 當前結點p pre p 保持pre指向p的前驅 InThreading p gt rchild 遞迴右子樹線索化 void InOrderThreading BiThrTree Thrt BiThrTree T 中序遍歷二叉樹T 並將其中序線索化 Thrt指向頭結點 演算法6 6 Thrt BiThrTree malloc sizeof BiThrNode if Thrt 生成頭結點不成功 exit OVERFLOW Thrt gt LTag Link 建頭結點 左標誌為指標 Thrt gt RTag Thread 右標誌為線索 Thrt gt rchild Thrt 右指針回指 if T 若二叉樹空 則左指針回指 Thrt gt lchild Thrt else Thrt gt lchild T 頭結點的左指標指向根結點 pre Thrt pre 前驅 的初值指向頭結點 InThreading T 中序遍歷進行中序線索化 pre指向中序遍歷的最後一個結點 pre gt rchild Thrt 最後一個結點的右指標指向頭結點 pre gt RTag Thread 最後一個結點的右標誌為線索 Thrt gt rchild pre 頭結點的右指標指向中序遍歷的最後一個結點 void InOrderTraverse Thr BiThrTree T void Visit TElemType 中序遍歷線索二叉樹T 頭結點 的非遞迴演算法 演算法6 5 BiThrTree p p T gt lchild p指向根結點 while p T 空樹或遍歷結束時 p T while p gt LTag Link 由根結點一直找到二叉樹的最左結點 p p gt lchild Visit p gt data 訪問此結點 while p gt RTag Thread amp amp p gt rchild T p gt rchild是線索 後繼 且不是遍歷的最後一個結點 p p gt rchild Visit p gt data 訪問後繼結點 p p gt rchild 若p gt rchild不是線索 是右孩子 p指向右孩子 返回迴圈 找這棵子樹中序遍歷的第1個結點 void PreThreading BiThrTree p PreOrderThreading 調用的遞迴函數 if pre gt rchild p的前驅沒有右孩子 pre gt rchild p p前驅的後繼指向p pre gt RTag Thread pre的右孩子為線索 if p gt lchild p沒有左孩子 p gt LTag Thread p的左孩子為線索 p gt lchild pre p的左孩子指向前驅 pre p 移動前驅 if p gt LTag Link p有左孩子 PreThreading p gt lchild 對p的左孩子遞迴呼叫preThreading if p gt RTag Link p有右孩子 PreThreading p gt rchild 對p的右孩子遞迴呼叫preThreading void PreOrderThreading BiThrTree Thrt BiThrTree T 先序線索化二叉樹T 頭結點的右指標指向先序遍歷的最後1個結點 Thrt BiThrTree malloc sizeof BiThrNode if Thrt 生成頭結點 exit OVERFLOW Thrt gt LTag Link 頭結點的左指針為孩子 Thrt gt RTag Thread 頭結點的右指針為線索 Thrt gt rchild Thrt 頭結點的右指標指向自身 if T 空樹 Thrt gt lchild Thrt 頭結點的左指標也指向自身 else 非空樹 Thrt gt lchild T 頭結點的左指標指向根結點 pre Thrt 前驅為頭結點 PreThreading T 從頭結點開始先序遞迴線索化 pre gt rchild Thrt 最後一個結點的後繼指向頭結點 pre gt RTag Thread Thrt gt rchild pre 頭結點的後繼指向最後一個結點 void PreOrderTraverse Thr BiThrTree T void Visit TElemType 先序遍歷線索二叉樹T 頭結點 的非遞迴演算法 BiThrTree p T gt lchild p指向根結點 while p T p沒指向頭結點 遍歷的最後1個結點的後繼指向頭結點 Visit p gt data 訪問根結點 if p gt LTag Link p有左孩子 p p gt lchild p指向左孩子 後繼 else p無左孩子 p p gt rchild p指向右孩子或後繼 void PostThreading BiThrTree p PostOrderThreading 調用的遞迴函數 if p p不空 PostThreading p gt lchild 對p的左孩子遞迴呼叫PostThreading PostThreading p gt rchild 對p的右孩子遞迴呼叫PostThreading if p gt lchild p沒有左孩子 p gt LTag Thread p的左孩子為線索 p gt lchild pre p的左孩子指向前驅 if pre gt rchild p的前驅沒有右孩子 pre gt RTag Thread p前驅的右孩子為線索 pre gt rchild p p前驅的後繼指向p pre p 移動前驅 void PostOrderThreading BiThrTree Thrt BiThrTree T 後序遞迴線索化二叉樹 Thrt BiThrTree malloc sizeof BiThrNode if Thrt 生成頭結點 exit OVERFLOW Thrt gt LTag Link 頭結點的左指針為孩子 Thrt gt RTag Thread 頭結點的右指針為線索 if T 空樹 Thrt gt lchild Thrt gt rchild Thrt 頭結點的左右指標指向自身 else 非空樹 Thrt gt lchild Thrt gt rchild T 頭結點的左右指標指向根結點 最後一個結點 pre Thrt 前驅為頭結點 PostThreading T 從頭結點開始後序遞迴線索化 if pre gt RTag Link 最後一個結點沒有右孩子 pre gt rchild Thrt 最後一個結點的後繼指向頭結點 pre gt RTag Thread void DestroyBiTree BiThrTree T DestroyBiThrTree調用的遞迴函數 T指向根結點 if T 非空樹 if T gt LTag 0 有左孩子 DestroyBiTree amp T gt lchild 銷毀左孩子子樹 if T gt RTag 0 有右孩子 DestroyBiTree amp T gt rchild 銷毀右孩子子樹 free T 釋放根結點 T NULL 空指針賦0 void DestroyBiThrTree BiThrTree Thrt 初始條件 線索二叉樹Thrt存在 操作結果 銷毀線索二叉樹Thrt if Thrt 頭結點存在 if Thrt gt lchild 根結點存在 DestroyBiTree amp Thrt gt lchild 遞迴銷毀頭結點lchild所指二叉樹 free Thrt 釋放頭結點 Thrt NULL 線索二叉樹Thrt指針賦0 外部链接 编辑维基共享资源中相关的多媒体资源 二叉树binary trees 页面存档备份 存于互联网档案馆 entry in the FindStat 页面存档备份 存于互联网档案馆 数据库 Gamedev net introduction on binary trees 页面存档备份 存于互联网档案馆 二叉树归纳证明 页面存档备份 存于互联网档案馆 Balanced binary search tree on array How to create bottom up an Ahnentafel list or a balanced binary search tree on array 页面存档备份 存于互联网档案馆 Binary trees and Implementation of the same with working code examples Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein B 5 3 Binary and positional trees Introduction to algorithms Third Cambridge Mass MIT Press 2009 1177 1178 2023 02 06 ISBN 978 0 262 03384 8 取自 https zh wikipedia org w index php title 二叉树 amp oldid 75911091, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。