二叉树

维基百科,自由的百科全书
跳转至: 导航搜索
一個簡單的二叉樹

计算机科学中,二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹二叉堆

二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點),二叉樹的子樹有左右之分,次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點;深度為k的二叉樹至多有2^k-1個結點;對任何一棵二叉樹T,如果其終端結點數為n_0,度為2的結點數為n_2,則n_0=n_2+1

樹和二叉樹的三個主要差別:

  1. 樹的結點個數至少為1,而二叉樹的結點個數可以為0;
  2. 樹中結點的最大度數沒有限制,而二叉樹結點的最大度數為2;
  3. 樹的結點無左、右之分,而二叉樹的結點有左、右之分。

<完全二叉树和满二叉树>

  1. 满二叉树:一棵深度为k,且有2^k-1个节点称之为满二叉树
  2. 完全二叉树:深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树

圖論中的定義[编辑]

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

二叉树(Binary Tree)的类型[编辑]

二叉树是一个有根,并且每个节点最多有2个子节点。非空的二元树,若树叶总数为 n0,分支度为2的总数为 n2,则 n0 = n2 + 1。

BinaryTree leaf.jpg

一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树(Full Binary Tree)。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其馀层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树(Complete Binary Tree)。具有n个节点的完全二叉树的深度为log_2n+1。深度为k的完全二叉树,至少有2^{k-1}个节点,至多有2^k-1个节点。

FullBT CompleteBT.jpg

Complete Binary Tree Full Binary Tree
總節點k 2^{h-1}< k < 2^h-1 k = 2^h-1
樹高h h = log_2k+1 h = log_2(k+1)

存儲二叉樹的方法[编辑]

編程語言中能用多種方法來構造二叉樹。

順序存儲表示[编辑]

一個存儲在數組中的完全二叉樹

二叉樹可以用數組或线性表來存儲,而且如果這是完全二叉樹,這種方法不會浪費空間。用這種緊湊排列,如果一個結點的索引為i,它的子結點能在索引2i+1和2i+2找到,並且它的父節點(如果有)能在索引floor((i-1)/2)找到(假設根節點的索引為0)。這種方法更有利於緊湊存儲和更好的訪問的局部性,特別是在前序遍歷中。然而,它需要連續的存儲空間,這樣在存儲高度為hn個結點組成的一般普通樹時將會浪費很多空間。一種最極壞的情況下如果深度為h的二叉樹每個節點只有右孩子需要佔用2的h次冪減1,而實際卻只有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;

基本操作[编辑]

三叉鏈表存儲表示[编辑]

基于三叉链表的二叉树的逻辑结构

改进于二叉链表,增加父节点的指引,能更好地实现节点间的访问,不过算法相对复杂。

存儲結構[编辑]

 /* 二叉樹的三叉鏈表存儲表示 */
 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和指向兩個子結點的leftright的樹結點結構。我們可以寫出這樣的過程:

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,然後順序遍歷右子樹。我們就已經順序訪問了整個樹。


一個簡單的二叉樹 在這個二叉樹中,
  • 前序遍歷的結果:2, 7, 2, 6, 5, 11, 5, 9, 4
  • 後序遍歷的結果:2, 5, 11, 6, 7, 4, 9, 5, 2
  • 中序遍歷的結果:2, 7, 5, 6, 11, 2, 5, 4, 9


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

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


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

深度優先遍歷[编辑]

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

廣度優先遍歷[编辑]

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

將n叉樹轉換為二叉樹[编辑]

一般有序樹和二叉樹之間有一一映射關係,能進行相互轉換。

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

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

將n叉樹轉換為二叉樹的例子


  • 將一棵樹轉換為二叉樹的方法:
  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域指示結點的後繼。以這種結點結構構成的二叉鏈表作為二叉樹的存儲結構,叫做線索鏈表,其中指向結點前驅和後繼的指針叫做線索,加上線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。若對二叉樹進行中序遍歷,則所得的線索二叉樹稱為中序線索二叉樹,線索鏈表稱為為中序線索鏈表。線索二叉樹是一種物理結構。 Tbt1.jpg

在中序線索樹找結點後繼的規律是:若其右標誌為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;

基本操作[编辑]