快捷導(dǎo)航

C語(yǔ)言線索二叉樹基礎(chǔ)解讀

更新時(shí)間：2022年04月25日 17:10:29 作者：洛語(yǔ)言

線索二叉樹還是按照鏈二叉樹的方法創(chuàng)建，只不過在結(jié)點(diǎn)原本為空的左指針改為指向該結(jié)點(diǎn)在中序遍歷中的前驅(qū)，結(jié)點(diǎn)原本為空的右指針改為指向該結(jié)點(diǎn)在中序遍歷中的后繼，也就是說(shuō)把空的指針給利用了起來(lái)

線索二叉樹的意義

對(duì)于一個(gè)有n個(gè)節(jié)點(diǎn)的二叉樹，每個(gè)節(jié)點(diǎn)有指向左右孩子的指針域。其中會(huì)出現(xiàn)n+ 1個(gè)空指針域，這些空間不儲(chǔ)存任何事物，浪費(fèi)著內(nèi)存的資源。
對(duì)于一些需要頻繁進(jìn)行二叉樹遍歷操作的場(chǎng)合，二叉樹的非遞歸遍歷操作過程相對(duì)比較復(fù)雜，遞歸遍歷雖然簡(jiǎn)單明了，但是會(huì)有額外的開銷，對(duì)于操作的時(shí)間和空間都比較浪費(fèi)。
我們可以考慮利用這些空地址，存放指向節(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼節(jié)點(diǎn)的地址。通過這些前驅(qū)和后繼節(jié)點(diǎn)的地址可以知道，從當(dāng)前位置下一步應(yīng)該走向哪里。

線索二叉樹的定義

指向前驅(qū)和后繼的指針稱為線索，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹就稱為線索二叉樹。
對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化。

線索二叉樹結(jié)構(gòu)的實(shí)現(xiàn)

二叉樹的線索存儲(chǔ)結(jié)構(gòu)

為了區(qū)分二叉樹某一節(jié)點(diǎn)是指向它的孩子節(jié)點(diǎn)還是指向前驅(qū)或者后繼節(jié)點(diǎn)，我們可以在每個(gè)節(jié)點(diǎn)增設(shè)兩個(gè)標(biāo)志，Ltag，Rtag.

其中:

Ltag為0時(shí)，代表該節(jié)點(diǎn)指向它的左孩子，Ltag為1時(shí)，代表該節(jié)點(diǎn)指向它的前驅(qū)節(jié)點(diǎn)。
Rtag為0時(shí)，代表該節(jié)點(diǎn)指向它的右孩子，Rtag為1時(shí)，代表該節(jié)點(diǎn)指向它的后繼節(jié)點(diǎn)。

所以，線索二叉樹結(jié)構(gòu)定義代碼如下：

typedef char BTDataType;
typedef enum{Link,Thread}PointerTag;//Link 是0，Thread 是1。
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	PointerTag LTag ;
	PointerTag RTag;
	BTDataType data;
}BTNode;

二叉樹的中序線索化

線索化的過程就是在遍歷過程中修改空指針的過程

以上二叉樹中序遍歷可以得到：

D B E A F C
D的前驅(qū)是空，后繼是B
B的前驅(qū)是D，后繼是E
E的前驅(qū)是B，后繼是A
F的前驅(qū)是A，后繼是C
C的前驅(qū)是F，后繼是空

線索化后：

中序遍歷線索化的遞歸函數(shù)代碼如下：

//中序線索化
BTNode* pre = NULL;/*全局變量，始終指向剛剛訪問過的節(jié)點(diǎn)*/
void InThreading(BTNode* p)
{
	if (p == NULL) return;
	InThreading(p->left);//遞歸左子樹線索化
	if (!p->left)//左孩子為空，left指針指向前驅(qū)
	{
		p->LTag = Thread;
		p->left = pre;
	}
	if (pre!=NULL && !pre->right)//右孩子為空，right指針指向后繼指針。
	//這里判斷 pre!=NULL 是因?yàn)榫€索化中序遍歷的第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)D)時(shí)，它并沒有前驅(qū)節(jié)點(diǎn)，此時(shí)的pre仍然是NULL。
	{
		pre->RTag = Thread;
		pre->right = p;
	}
	pre = p;//保持pre指向p的前驅(qū)
	InThreading(p->right);
}

分析：

if (!p->left)表示如果某節(jié)點(diǎn)的左指針域?yàn)榭?，因?yàn)槠淝膀?qū)節(jié)點(diǎn)剛剛訪問過，并且賦值給了pre，所以可以將pre賦值給 l -> left，并且修改 p-> LTag = Thread，以完成前驅(qū)節(jié)點(diǎn)的線索化。
pre 是 p 的前驅(qū)，那么， p 就是 pre 的后繼。當(dāng)pre -> right 為空時(shí)，就可以將p賦值給 pre -> right ，并且修改 pre -> RTag = Thread。

線索二叉樹的中序遍歷

void MidOrder(BTNode*p)
{
	while (p != NULL)
	{
		while (p->LTag == Link)//
		{
			p = p->left;
		}
		printf("%c ",p->data);
		while (p->RTag == Thread && p->right != p)
		{
			p = p->right;
			printf("%c ", p->data);
		}
		p = p->right;
	}
	return;
}

分析：

while (T->ltag == Link)從根節(jié)點(diǎn)開始遍歷，如果左標(biāo)記是Link讓它一直循環(huán)下去，直到找到標(biāo)記為Thread的的結(jié)點(diǎn)，也就是要遍歷的第一個(gè)結(jié)點(diǎn)，然后根據(jù)后驅(qū)指針找到后繼結(jié)點(diǎn)
后面就是重復(fù)以上過程，直到遍歷完整個(gè)二叉數(shù)。