基礎(chǔ)介紹

線索二叉樹就是當(dāng)用鏈表組成的二叉樹其在葉節(jié)點(diǎn)或者分支中有空指針時(shí)，將空指針指向自己的前驅(qū)后者后繼

記錄后繼

記錄前驅(qū)

線索二叉樹

數(shù)據(jù)結(jié)構(gòu)

代碼實(shí)現(xiàn)

#include "string.h" #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0#define MAXSIZE 100 /* 存儲(chǔ)空間初始分配量 */typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼,如OK等 */ typedef char TElemType;typedef enum {Link ,Thread}PointerTag;/* Link==0表示指向左右孩子指針, */ /* Thread==1表示指向前驅(qū)或后繼的線索 */typedef struct BiThrNode {TElemType data;struct BiThrNode* lchild, * rchild;PointerTag LTag;PointerTag RTag; } *BiThrTree;TElemType Nil = '#'; /* 字符型以空格符為空 */Status visit(TElemType e) {printf("%c ", e);return OK;}/* 按前序輸入二叉線索樹中結(jié)點(diǎn)的值,構(gòu)造二叉線索樹T */ /* 0(整型)/空格(字符型)表示空結(jié)點(diǎn) */ Status CreateBiThrTree(BiThrTree* T) {TElemType h;h = 1;if (h == Nil)*T = NULL;else{T = new BiThrTree();if (!*T)exit(OVERFLOW);(*T)->data = h; /* 生成根結(jié)點(diǎn)(前序) */CreateBiThrTree(&(*T)->lchild); /* 遞歸構(gòu)造左子樹 */if ((*T)->lchild) /* 有左孩子 */(*T)->LTag = Link;CreateBiThrTree(&(*T)->rchild); /* 遞歸構(gòu)造右子樹 */if ((*T)->rchild) /* 有右孩子 */(*T)->RTag = Link;}return OK; }BiThrTree pre; /* 全局變量,始終指向剛剛訪問過的結(jié)點(diǎn) *//* 中序遍歷進(jìn)行中序線索化 */ void InThreading(BiThrTree p) {if (p){InThreading(p->lchild);/* 遞歸左子樹線索化 *///中序if (!p->lchild)//沒有左孩子{p->LTag = Thread;p->lchild = pre;}if (!pre->rchild){pre->RTag = Thread;pre->rchild = p;}pre = p;InThreading(p->rchild);/* 遞歸右子樹線索化 */} }/* 中序遍歷二叉樹T,并將其中序線索化,Thrt指向頭結(jié)點(diǎn) */ Status InOrderThreading(BiThrTree* Thrt, BiThrTree T) {*Thrt = (BiThrTree)malloc(sizeof(BiThrNode));if (!*Thrt)exit(OVERFLOW);(*Thrt)->LTag = Link; /* 建頭結(jié)點(diǎn) */ // link == 0(*Thrt)->RTag = Thread; // thread == 1(*Thrt)->rchild = (*Thrt); /* 右指針回指 */if (!T) /* 若二叉樹空,則左指針回指 */(*Thrt)->lchild = *Thrt;else{(*Thrt)->lchild = T;pre = (*Thrt);InThreading(T); /* 中序遍歷進(jìn)行中序線索化 */pre->rchild = *Thrt;pre->RTag = Thread; /* 最后一個(gè)結(jié)點(diǎn)線索化 */(*Thrt)->rchild = pre;}return OK; }/* 中序遍歷二叉線索樹T(頭結(jié)點(diǎn))的非遞歸算法 */ Status InOrderTraverse_Thr(BiThrTree T) {BiThrTree p;p = T->lchild; /* p指向根結(jié)點(diǎn) */while (p != T){ /* 空樹或遍歷結(jié)束時(shí),p==T */while (p->LTag == Link)p = p->lchild;if (!visit(p->data)) /* 訪問其左子樹為空的結(jié)點(diǎn) */return ERROR;while (p->RTag == Thread && p->rchild != T){p = p->rchild;visit(p->data); /* 訪問后繼結(jié)點(diǎn) */}p = p->rchild;}return OK; }int main() {BiThrTree H, T;printf("請按前序輸入二叉樹(如:'ABDH##I##EJ###CF##G##')\n");CreateBiThrTree(&T); /* 按前序產(chǎn)生二叉樹 */InOrderThreading(&H, T); /* 中序遍歷,并中序線索化二叉樹 */printf("中序遍歷(輸出)二叉線索樹:\n");InOrderTraverse_Thr(H); /* 中序遍歷(輸出)二叉線索樹 */printf("\n");return 0; }

總結(jié)

以上是生活随笔為你收集整理的大话数据结构15 ： 线索二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。