本页使用了标题或全文手工转换

二叉树

维基百科,自由的百科全书
(重定向自完全二叉树
跳到导航 跳到搜索
一棵有9个节点且深度为3的二叉树,其根节点的值为2,它既不平衡亦未经过排序
一棵简单的满二叉树

计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

二叉树的第层至多拥有个节点;深度为的二叉树至多总共有个节点(定义根节点所在深度 ),而总计拥有节点数符合的,称为“满二叉树”;深度为个节点的二叉树,当且仅当其中的每一节点,都可以和深度的满二叉树,序号1到的节点一对一对应时,称为完全二叉树。对任何一棵非空的二叉树,如果其叶片(终端节点)数为,分支度为2的节点数为,则

与普通树不同,普通树的节点个数至少为1,而二叉树的节点个数可以为0;普通树节点的最大分支度没有限制,而二叉树节点的最大分支度为2;普通树的节点无左、右次序之分,而二叉树的节点有左、右次序之分。

二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树二叉堆,并应用于高效率的搜索和排序。

图论中的定义[编辑]

二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后,每个顶点定义了唯一的父节点,和最多2个子节点。然而,没有足够的信息来区分左节点和右节点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林

性质[编辑]

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

BinaryTree leaf.jpg

特殊类型[编辑]

FullBT CompleteBT.jpg

完全二叉树 完美二叉树
总节点k <= k <= k =
树高h h = h =

完美二叉树[编辑]

一棵深度为k,且有个节点的二叉树,称为完美二叉树(Perfect Binary Tree)。这种树的特点是每一层上的节点数都是最大节点数。

性质[编辑]

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

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

完全二叉树[编辑]

在一颗二叉树中,若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么在右边缺少连续若干节点,则此二叉树完全二叉树(Complete Binary Tree)。具有n个节点的完全二叉树的深度为。深度为k的完全二叉树,至少有个节点,至多有个节点。

存储[编辑]

程序设计语言中能用多种方法来构造二叉树。

顺序存储表示[编辑]

一个存储在数组中的完全二叉树

二叉树可以用数组链接串列来存储,若是满二叉树就能紧凑排列而不浪费空间。如果某个节点的索引为i,(假设根节点的索引为0)则在它左子节点的索引会是,以及右子节点会是;而它的父节点(如果有)索引则为。这种方法更有利于紧凑存储和更好的访问的局部性,特别是在前序遍历中。然而,它需要连续的存储空间,这样在存储高度为hn个节点所组成的一般树时,将浪费很多空间。在最糟糕的情况下,如果深度为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和指向两个子结点的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,然后顺序遍历右子树。我们就已经循序访问了整个树。

后序遍历伪代码如下:

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


Bitree.JPG 用二叉树表示下述表达式: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}。它能被变换成右边的二叉树。

将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;

基本操作[编辑]

外部链接[编辑]