二叉树

✍ dations ◷ 2024-12-22 16:04:59 #自2015年4月包含过多范例的条目,数据结构,树结构,二叉树

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

二叉树的第 $i {\displaystyle i}$ 。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为的个节点所组成的一般树时，将浪费很多空间。在最糟糕的情况下，如果深度为h的二叉树其每个节点都只有右孩子，则该存储结构需要占用 $2^{h}-1$ 是二叉搜索树的结点，那么的左子树的所有结点的值都比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

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。

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

n叉树转换为二叉树的方法：二叉树中结点x的左子结点为n叉树中结点x的左子结点；二叉树中结点x的右子结点为n叉树中结点x的第一个右边的同级结点y。

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

例如，在左边的树中，A有6个子结点{B,C,D,E,F,G}。它能被转换成右边的二叉树。

将n叉树转换为二叉树的例子

树的二叉链表标记法（孩子兄弟标记法）是树和二叉树转换的介质。

 /* 樹的二叉鏈表(孩子—兄弟)存儲表示 */ 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)->firstchild) /* T有長子 */       DestroyTree(&(*T)->firstchild); /* 銷毀T的長子為根結點的子樹 */     if((*T)->nextsibling) /* T有下一個兄弟 */       DestroyTree(&(*T)->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個)的值 */   CSTree p,p1;   LinkQueue q;   int i,l;   InitQueue(&q);   printf("請輸入根結點(字元型,空格為空): ");   scanf("%c%*c",&c);   if(c!=Nil) /* 非空樹 */   {     *T=(CSTree)malloc(sizeof(CSNode)); /* 建立根結點 */     (*T)->data=c;     (*T)->nextsibling=NULL;     EnQueue(&q,*T); /* 入隊根結點的指針 */     while(!QueueEmpty(q)) /* 隊不空 */     {       DeQueue(&q,&p); /* 出隊一個結點的指標 */       printf("請按長幼順序輸入結點%c的所有孩子: ",p->data);       gets(c);       l=strlen(c);       if(l>0) /* 有孩子 */       {         p1=p->firstchild=(CSTree)malloc(sizeof(CSNode)); /* 建立長子結點 */         p1->data=c;         for(i=1;i<l;i++)         {           p1->nextsibling=(CSTree)malloc(sizeof(CSNode)); /* 建立下一個兄弟結點 */           EnQueue(&q,p1); /* 入隊上一個結點 */           p1=p1->nextsibling;           p1->data=c;         }         p1->nextsibling=NULL;         EnQueue(&q,p1); /* 入隊最後一個結點 */       }       else         p->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->firstchild) /* 樹無長子 */     return 1;   for(p=T->firstchild;p;p=p->nextsibling)   { /* 求子樹深度的最大值 */     depth=TreeDepth(p);     if(depth>max)       max=depth;   }   return max+1; /* 樹的深度=子樹深度最大值+1 */ }

 TElemType Value(CSTree p) { /* 返回p所指結點的值 */   return p->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(&q); /* 初始化佇列 */     EnQueue(&q,T); /* 根結點入隊 */     while(!QueueEmpty(q)) /* 隊不空 */     {       DeQueue(&q,&a); /* 出隊,佇列元素賦給a */       if(a->data==s)	 return a;       if(a->firstchild) /* 有長子 */         EnQueue(&q,a->firstchild); /* 入隊長子 */       if(a->nextsibling) /* 有下一個兄弟 */         EnQueue(&q,a->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->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(&q);   if(T) /* 樹非空 */   {     if(Value(T)==cur_e) /* 根結點值為cur_e */       return Nil;     EnQueue(&q,T); /* 根結點入隊 */     while(!QueueEmpty(q))     {       DeQueue(&q,&p);       if(p->firstchild) /* p有長子 */       {         if(p->firstchild->data==cur_e) /* 長子為cur_e */           return Value(p); /* 返回雙親 */         t=p; /* 雙親指針賦給t */         p=p->firstchild; /* p指向長子 */         EnQueue(&q,p); /* 入隊長子 */         while(p->nextsibling) /* 有下一個兄弟 */         {           p=p->nextsibling; /* p指向下一個兄弟 */	 if(Value(p)==cur_e) /* 下一個兄弟為cur_e */	 return Value(t); /* 返回雙親 */	 EnQueue(&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&&f->firstchild) /* 找到結點cur_e且結點cur_e有長子 */     return f->firstchild->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&&f->nextsibling) /* 找到結點cur_e且結點cur_e有右兄弟 */     return f->nextsibling->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->nextsibling=p->firstchild; /* p的原長子現是c的下一個兄弟(c本無兄弟) */       p->firstchild=c;     }     else /* 找插入點 */     {       p=p->firstchild; /* 指向p的長子 */       j=2;       while(p&&i>j)       {         p=p->nextsibling;         j++;       }       if(j==i) /* 找到插入位置 */       {         c->nextsibling=p->nextsibling;         p->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->firstchild;       p->firstchild=b->nextsibling; /* p的原次子現是長子 */       b->nextsibling=NULL;       DestroyTree(&b);     }     else /* 刪除非長子 */     {       p=p->firstchild; /* p指向長子 */       j=2;       while(p&&i>j)       {         p=p->nextsibling;         j++;       }       if(j==i) /* 找到第i棵子樹 */       {         b=p->nextsibling;         p->nextsibling=b->nextsibling;         b->nextsibling=NULL;         DestroyTree(&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->firstchild) /* 有長子 */     {       PostOrderTraverse(T->firstchild,Visit); /* 後根遍歷長子子樹 */       p=T->firstchild->nextsibling; /* p指向長子的下一個兄弟 */       while(p)       {         PostOrderTraverse(p,Visit); /* 後根遍歷下一個兄弟子樹 */         p=p->nextsibling; /* p指向再下一個兄弟 */       }     }     Visit(Value(T)); /* 最後訪問根結點 */   } }

 void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType)) { /* 層序遍歷孩子—兄弟二叉鏈表結構的樹T */   CSTree p;   LinkQueue q;   InitQueue(&q);   if(T)   {     Visit(Value(T)); /* 先訪問根結點 */     EnQueue(&q,T); /* 入隊根結點的指針 */     while(!QueueEmpty(q)) /* 隊不空 */     {       DeQueue(&q,&p); /* 出隊一個結點的指標 */       if(p->firstchild) /* 有長子 */       {         p=p->firstchild;         Visit(Value(p)); /* 訪問長子結點 */         EnQueue(&q,p); /* 入隊長子結點的指針 */         while(p->nextsibling) /* 有下一個兄弟 */         {           p=p->nextsibling;           Visit(Value(p)); /* 訪問下一個兄弟 */           EnQueue(&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域的指针均指向头结点，这样就创建了一个双向线索链表。二叉树常采用二叉链表方式存储。

二叉树

基本操作

线索二叉树

相关