優(yōu)勢(shì)：便于在中序遍歷下，查找前驅(qū)和后繼。

前驅(qū)/后繼含義：AB中，A是B前驅(qū)，B是A后繼。

ltag=0時(shí)：lchild指向左孩子? ? ? ? ? ? ? ? ltag=1時(shí)：lchild指向前驅(qū)

rtag=0時(shí)：rchild指向右孩子? ? ? ? ? ? ? ? rtag=1時(shí)：rchild指向后繼

?過(guò)程：

1、先前序遍歷創(chuàng)建二叉樹(shù)

2、線(xiàn)索化二叉樹(shù)

3、線(xiàn)索二叉樹(shù)中序遍歷輸出

總代碼：

//線(xiàn)索二叉樹(shù)
//優(yōu)勢(shì)：便于在中序遍歷下，查找前驅(qū)和后繼
#include<stdio.h>
#include<malloc.h>
#include<string>int index = 0;
int first = 1;
char str[30];
typedef enum { Link, Thread } PointerTag;				//0：Link（指向結(jié)點(diǎn)）		1：Thread（指向線(xiàn)索）typedef struct BiThTree
{char data;struct BiThTree* lchild, * rchild;					//左孩子、右孩子PointerTag ltag, rtag;									//0：指向左/右孩子；	1：指向前驅(qū)/后繼struct BiThTree* parent;								//指向雙親結(jié)點(diǎn)
}BiThTree;
BiThTree* head;		//頭
BiThTree* Pre;			//前一個(gè)結(jié)點(diǎn)void Init_BiThTree()
{head = (BiThTree*)malloc(sizeof(BiThTree));head->parent = head;
}//前序遍歷創(chuàng)建二叉樹(shù)
void Create_BiThTree(BiThTree* T)
{if (str[index] == '#')		//空{(diào)T->data = str[index++];return;}T->parent = Pre;									//保存前一個(gè)結(jié)點(diǎn)T->data = str[index++];T->lchild = (BiThTree*)malloc(sizeof(BiThTree));T->rchild = (BiThTree*)malloc(sizeof(BiThTree));T->ltag = Link;T->rtag = Link;Pre = T;											//保存前一個(gè)結(jié)點(diǎn)Create_BiThTree(T->lchild);Create_BiThTree(T->rchild);
}//線(xiàn)索化二叉樹(shù)(中序)
void InThreading(BiThTree* T)
{//如果存在if (T->data != '#'){InThreading(T->lchild);					//遞歸左子樹(shù)//線(xiàn)索化左if (T->lchild->data == '#')				//lchild為空，lchild指向前驅(qū){T->ltag = Thread;						//線(xiàn)索模式if (first)											//首個(gè)賦空{(diào)T->lchild->data = '#';first = 0;}elseT->lchild = Pre;						//lchild指向前驅(qū)}//線(xiàn)索化右else if (Pre->rchild->data == '#')	//前驅(qū)的rchild為空，前驅(qū)的rchild指向后繼{Pre->rtag = Thread;					//線(xiàn)索模式Pre->rchild = T;							//rchild指向后繼}Pre = T;InThreading(T->rchild);					//遞歸右子樹(shù)}
}//線(xiàn)索二叉樹(shù)中序遍歷
void InOrderThTraverse(BiThTree* T)
{if (T->data != '#'){if (T->ltag == Link)InOrderThTraverse(T->lchild);printf("%c結(jié)點(diǎn)	\tlchild：%c\trchild：%c\n", T->data, T->lchild->data, T->rchild->data);if (T->rtag == Link)InOrderThTraverse(T->rchild);}
}int main()
{printf("請(qǐng)按照前序遍歷順序輸入需要?jiǎng)?chuàng)建的二叉樹(shù)結(jié)點(diǎn)：\n");scanf_s("%s", str, 20);Init_BiThTree();								//初始化Create_BiThTree(head);				//前序遍歷創(chuàng)建二叉樹(shù)Pre = head;InThreading(head);						//中序線(xiàn)索化二叉樹(shù)InOrderThTraverse(head);			//線(xiàn)索二叉樹(shù)中序遍歷
}

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法（6-4）线索二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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