線索二叉樹介紹

我們在有n個結點的二叉鏈表中，每個結點有指向左右2個孩子的指針域，所以有2n個指針域，而n個結點的二叉樹一共有n-1條分支線，也就是說，其實存在2n-(n-1) = n+1 個空指針域。空間十分浪費。在另一方面，我們對二叉樹做中序遍歷時，我只知道每個樹結點的左右孩子是誰，卻不知道該樹結點的前驅和后繼是誰。要想知道必須重新遍歷一遍。

為什么不考慮在創建時就記住這些前驅和后繼呢，那將會省去很多時間。仔細想想，如果我們的樹結點左右孩子都不為NULL ，如果采用中序遍歷，那么該結點的前驅結點是不是左孩子，后繼結點是不是右孩子？這就是為什么我們要采用中序遍歷的形式來對二叉樹進行線索化，那么我需要將孩子結點為NULL的樹結點 空間利用起來！因為字節點雖然為NULL，但是都有前驅和后繼結點，那么我們可以考慮將 lchild 放樹節點的前驅結點，rchild放樹結點的后繼結點。那么這里我們是否要考慮區分lchild，rchild 是原有的子節點還是我們后續線索化添加的前驅后繼結點呢？所以要在線索二叉樹結點的數據結構都要體現唄。我們把這種指向前驅和后繼的指針稱為線索，加上線索的二叉鏈表稱為線索鏈表，相應的的二叉樹就稱為線索二叉樹（Threaded Binary Tree）。

線索二叉樹實現思路

創建線索二叉樹和創建普通的二叉樹（二叉鏈表）相似，我們同樣約定采用前序遍歷的方式進行創建樹結點。如果普通二叉樹不是很清楚的，請看樹：二叉鏈表的實現。

如何線索化二叉樹呢？我們采用中序遍歷二叉樹訪問每一個樹結點的時候，我們只知道當前結點，如何知道前驅結點呢？我們能否考慮將剛剛訪問的結點（pre）保存下來，每次訪問樹結點的時候，發現左孩子結點為NULL，就將其線索化！它的前驅結點是不是pre結點呢？！tree->lchild = pre；那個剛剛訪問的結點 (pre)的右孩子結點 為NULL，那么將其線索化 pre 它的后繼結點是不是當前結點呢？！pre->rchild = tree；具體詳細代碼請看代碼實現。

下面是一張簡陋的二叉線索樹的圖，箭頭方向 代表該結點前驅和后繼結點。紅色箭頭表示 原來的孩子結點都不為空，直接就是自己的前驅或者后繼結點。黑色箭頭表示的通過線索添加的前驅后驅結點，都是孩子結點為NULL 而添加的。

線索二叉樹代碼實現

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> typedef char TElemType; //指針指向類型，Link(0) 表示為左右孩子結點，Thread(1) 表示前驅或者后驅結點 typedef enum{Link,Thread}PointerTag; typedef struct BiThrNode {TElemType data;struct BiThrNode *lchild, *rchild;PointerTag ltag, rtag; }BiThrNode,*BiThrTree;//全局變量，pre 指向剛剛訪問的樹結點 BiThrTree pre = NULL;//約定前序遍歷的方式 創建線索二叉樹 void CreateBiThrTree(BiThrTree* tree) {TElemType data;scanf("%c", &data);if (' ' == data){*tree = NULL;}else{*tree = (BiThrTree)malloc(sizeof(BiThrNode));(*tree)->data = data;(*tree)->ltag = (*tree)->rtag = Link;CreateBiThrTree(&(*tree)->lchild);CreateBiThrTree(&(*tree)->rchild);}return; } //中序遍歷的形式 將二叉樹結點 線索化 void MidOrderTraverse_Thr(BiThrTree tree) {if (NULL != tree){//線索化左子樹MidOrderTraverse_Thr(tree->lchild);if (NULL == tree->lchild){tree->ltag = Thread;tree->lchild = pre;}if (NULL == pre->rchild){pre->rtag = Thread;pre->rchild = tree;}pre = tree;//線索化右子樹MidOrderTraverse_Thr(tree->rchild);}return; } //創建一個頭結點（lchild指向二叉樹根結點），配合二叉樹 對二叉樹進行線索化。 void BiThrTree_Thr(BiThrTree *head, BiThrTree tree) {//創建二叉樹的頭結點，頭結點默認ltag為Link 指向根結點，rtag 默認為線索，rchild指向中序遍歷最后一個結點（樹最右的結點）BiThrTree headNode = (BiThrTree)malloc(sizeof(BiThrNode));headNode->ltag = Link;headNode->rtag = Thread;//空樹 ，左右結點指向自己if (NULL == tree){headNode->lchild = headNode;headNode->rchild = headNode;}else{pre = headNode;//pre 初始化為頭結點headNode->lchild = tree;MidOrderTraverse_Thr(tree);//線索化完畢，pre指向樹中序遍歷的最后一個結點（樹最右邊的結點）pre->rtag = Thread;pre->rchild = headNode;headNode->rchild = pre;}*head = headNode;return; } void visit(TElemType data) {printf("%c ", data); } //中序遍歷 線索二叉樹，非遞歸形式 void MidOrderTraverse(BiThrTree head) {BiThrTree tree = head->lchild;//循環結束條件：空樹 或者 中序遍歷完畢while (tree != head){//一直循環，直到找到樹最左邊的結點（樹的中序遍歷的起點）while (tree->ltag == Link){tree = tree->lchild;}visit(tree->data);//循環完畢tree為中序遍歷中的 根結點while (tree->rtag == Thread && tree->rchild != head){tree = tree->rchild;visit(tree->data);}//進行右子樹tree = tree->rchild;}printf("\n");return; }int main(int argc, char *argv[]) {BiThrTree tree = NULL, head = NULL;printf("請輸入前序遍歷結點:");CreateBiThrTree(&tree);BiThrTree_Thr(&head, tree);printf("中序遍歷線索二叉樹:");MidOrderTraverse(head);return 0; }

運行結果檢測

注意輸入是，ABC__D__E_G__，下劃線是空格的意思。

總結

以上是生活随笔為你收集整理的树：线索二叉树详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。