天天看點
傳回

【資料結構】線索二叉樹的實作（C語言）

文章目錄

    • 線索二叉樹原理
    • 線索二叉樹結構實作
    • 測試代碼

線索二叉樹原理

觀察圖1-1，發現指針域并沒有被充分利用，有許許多多的 ^ 也就是空指針域的存在，應該想辦法利用起來。

【資料結構】線索二叉樹的實作（C語言）

圖1-1

首先我們要來看一下這空指針有多少個呢？對于一個有n個結點的二叉連結清單，每個結點指向左右孩子的兩個指針域，是以一共是2n個指針域。而n個結點的二叉樹一共有n-1條分支線，也就說說，其實是存在2n-（n-1）=n+1個空指針域。

比如圖1-1有10個結點，而帶有“^”空指針域為11，這些存儲空間不存儲任何事物，白白的浪費着記憶體的資源。

另一方面，我們在做周遊時，比如對圖1-1做了中序周遊，得到了字元序列HDIBJEAFCG這樣的字元序列，周遊過後，我們可以知道，結點I的前驅是D，後繼是B，結點F的前驅是A，後繼是C，也就是說，我們可以清楚的看到任意一個結點，它的前驅和後繼是哪一個。

可是這是建立在已經周遊過的基礎上的。在二叉連結清單上，我們隻能知道每個結點指向其左右孩子結點的位址，而不知道某個結點的前驅是誰，後繼是誰。要想知道，必須周遊一次。以後每次需要知道時，都必須先周遊一次。為什麼不考慮在建立時就記住這些前驅和後繼了?

我們可以利用這些空位址，存放指向結點在某種周遊次序下的前驅和後繼結點的位址。我們把這種指向前驅和後繼的指針稱為線索，加上線索的二叉連結清單稱為線索連結清單，相應的二叉樹就稱為線索二叉樹。

圖1-2，我們把整個二叉樹中序周遊之後，将所有的空指針域中的rchild，改為指向它的後繼結點， 也是我們就可以通過指針知道H的後繼是D（圖中的①）I的後繼是B（圖中的②）J的後繼是E（圖中③）E的後繼是A（圖中④），F的後繼是C（圖中⑤），G的後繼因為不存在而執行NULL（圖中⑥），此時共有6個空指針被利用。

【資料結構】線索二叉樹的實作（C語言）

圖1-2

再看圖1-3，我們将這棵二叉樹的所有空指針域中的lchild，改為指向目前結點的前驅，是以H的前驅是NULL（圖中①），I的前驅是D（圖中②）。J的前驅樹B（圖中③）F的前驅是A（圖中④），G的前驅是C（圖中⑤），一共5個空指針域被利用，正好和上面的後繼加起來是11個。

【資料結構】線索二叉樹的實作（C語言）

圖1-3

通過圖1-4（空心箭頭實線為前驅，虛線黑箭頭為後繼），就更容易看出，其實線索二叉樹，等于是把一顆二叉樹轉變成了一個雙向連結清單，這樣我們的插入結點，查找某個結點都帶來了友善，所有我們對 二叉樹以某種次序周遊使其變為線索二叉樹的過程稱為線索化。

【資料結構】線索二叉樹的實作（C語言）

圖1-4

我們如何知道某一結點的lchild是指向它的左孩子還是指向前驅？rchild是指向右孩子還是後繼？比如E結點的lchild是指向它的左孩子J，而child是指向右孩子還是後繼A。顯然我們在決定lchild是指向左孩子還是前驅，rchild是指向右孩子還是後繼上時需要一個分區标志的。是以，我們在每個結點在增設兩個辨別域ltag和rtag，注意ltag和rtag隻是存放0或者1數字的布爾型變量，其占用的記憶體空間要小于像lchild和rchild的指針變量。結點結構如圖1-5所示。

【資料結構】線索二叉樹的實作（C語言）

圖1-5

  • ltag為0時指向結點的左孩子，為1時指向該結點的前驅。
  • rtag為0時指向該結點右孩子，為1時指向該結點的後繼。
  • 是以對圖1-1的二叉連結清單可以改為圖1-6所示的結構圖。
    【資料結構】線索二叉樹的實作（C語言）
    圖1-6

線索二叉樹結構實作

線索二叉樹的存儲結構定義

typedef enum {Link,Thread} PointerTag;	/* Link==0表示指向左右孩子指針, */
										/* Thread==1表示指向前驅或後繼的線索 */
typedef  struct BiThrNode	/* 二叉線索存儲結點結構 */
{
	TElemType data;	/* 結點資料 */
	struct BiThrNode *lchild, *rchild;	/* 左右孩子指針 */
	PointerTag LTag;
	PointerTag RTag;		/* 左右标志 */
} BiThrNode, *BiThrTree;

線索化的實質就是将二叉連結清單的空指針改為指向前驅或者後繼的線索。由于前驅和後繼的資訊隻有在周遊該二叉樹時才能得到，是以線索化的二叉樹的過程就是在周遊的過程中修改空指針的過程。

BiThrTree pre; /* 全局變量,始終指向剛剛通路過的結點 */
/* 中序周遊進行中序線索化 */
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; /* 前驅右孩子指針指向後繼(目前結點p) */
		}
		pre=p; /* 保持pre指向p的前驅 */
		InThreading(p->rchild); /* 遞歸右子樹線索化 */
	}
}

觀察發現其實和二叉樹中序周遊的遞歸代碼幾乎一模一樣。

有了線索二叉樹之後，我們對它周遊時發現，其實就等于是操作一個雙向連結清單結構。

和雙向連結清單結構一樣，在二叉樹線索連結清單上添加一個頭結點，如圖1-7所示，并令其lchild域的指針指向二叉樹的根結點（圖中①），其rchild域的指針指向中序周遊時通路的最後一個結點（圖中的②），反正，令二叉樹的中序序列中的第一個結點中，lchild域指針和最後一個結點的rchild域指針均指向頭結點（圖中的③和④），這樣定義的好處就是我們既可以從第一個結點起順後繼進行周遊，也可以從最後一個結點起前驅進行周遊。

【資料結構】線索二叉樹的實作（C語言）

圖1-7

周遊的代碼如下：

Status InOrderTraverse_Thr(BiThrTree T)
{ 
	BiThrTree p;
	p=T->lchild; /* p指向根結點 */
	while(p!=T)
	{ /* 空樹或周遊結束時,p==T */
		while(p->LTag==Link)
			p=p->lchild;
		printf("%c",p->data); //顯示結點資料，可以更改為對其他結點的操作
		while(p->RTag==Thread&&p->rchild!=T)
		{
			p=p->rchild;
			printf(p->data); /* 通路後繼結點 */
		}
		p=p->rchild;
	}
	return OK;
}

從這段代碼可以看出， 他等于是一個連結清單的掃描，是以時間複雜度為O(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 /* 存儲空間初始配置設定量 */

typedef int Status;	/* Status是函數的類型,其值是函數結果狀态代碼,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;	/* Link==0表示指向左右孩子指針, */
										/* Thread==1表示指向前驅或後繼的線索 */
typedef  struct BiThrNode	/* 二叉線索存儲結點結構 */
{
	TElemType data;	/* 結點資料 */
	struct BiThrNode *lchild, *rchild;	/* 左右孩子指針 */
	PointerTag LTag;
	PointerTag RTag;		/* 左右标志 */
} BiThrNode, *BiThrTree;

TElemType Nil='#'; /* 字元型以空格符為空 */

Status visit(TElemType e)
{
	printf("%c ",e);
	return OK;
}

/* 按前序輸入二叉線索樹中結點的值,構造二叉線索樹T */
/* 0(整型)/空格(字元型)表示空結點 */
Status CreateBiThrTree(BiThrTree *T)
{ 
	TElemType h;
	scanf("%c",&h);

	if(h==Nil)
		*T=NULL;
	else
	{
		*T=(BiThrTree)malloc(sizeof(BiThrNode));
		if(!*T)
			exit(OVERFLOW);
		(*T)->data=h; /* 生成根結點(前序) */
		CreateBiThrTree(&(*T)->lchild); /* 遞歸構造左子樹 */
		if((*T)->lchild) /* 有左孩子 */
			(*T)->LTag=Link;
		CreateBiThrTree(&(*T)->rchild); /* 遞歸構造右子樹 */
		if((*T)->rchild) /* 有右孩子 */
			(*T)->RTag=Link;
	}
	return OK;
}

BiThrTree pre; /* 全局變量,始終指向剛剛通路過的結點 */
/* 中序周遊進行中序線索化 */
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; /* 前驅右孩子指針指向後繼(目前結點p) */
		}
		pre=p; /* 保持pre指向p的前驅 */
		InThreading(p->rchild); /* 遞歸右子樹線索化 */
	}
}

/* 中序周遊二叉樹T,并将其中序線索化,Thrt指向頭結點 */
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ 
	*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
	if(!*Thrt)
		exit(OVERFLOW);
	(*Thrt)->LTag=Link; /* 建頭結點 */
	(*Thrt)->RTag=Thread;
	(*Thrt)->rchild=(*Thrt); /* 右指針回指 */
	if(!T) /* 若二叉樹空,則左指針回指 */
		(*Thrt)->lchild=*Thrt;
	else
	{
		(*Thrt)->lchild=T;
		pre=(*Thrt);
		InThreading(T); /* 中序周遊進行中序線索化 */
		pre->rchild=*Thrt;
		pre->RTag=Thread; /* 最後一個結點線索化 */
		(*Thrt)->rchild=pre;
	}
	return OK;
}

/* 中序周遊二叉線索樹T(頭結點)的非遞歸算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{ 
	BiThrTree p;
	p=T->lchild; /* p指向根結點 */
	while(p!=T)
	{ /* 空樹或周遊結束時,p==T */
		while(p->LTag==Link)
			p=p->lchild;
		if(!visit(p->data)) /* 通路其左子樹為空的結點 */
			return ERROR;
		while(p->RTag==Thread&&p->rchild!=T)
		{
			p=p->rchild;
			visit(p->data); /* 通路後繼結點 */
		}
		p=p->rchild;
	}
	return OK;
}

int main()
{
	BiThrTree H,T;
	printf("請按前序輸入二叉樹(如:'ABDH##I##EJ###CF##G##')\n");
 	CreateBiThrTree(&T); /* 按前序産生二叉樹 */
	InOrderThreading(&H,T); /* 中序周遊,并中序線索化二叉樹 */
	printf("中序周遊(輸出)二叉線索樹:\n");
	InOrderTraverse_Thr(H); /* 中序周遊(輸出)二叉線索樹 */
	printf("\n");
	
	return 0;
}
大話資料結構 二叉樹 指針 連結清單 資料結構
上一篇: 西門子200smart與組态王之間無線Profinet通信執行個體
下一篇: 利用無線通訊技術建構工廠智能化立體倉儲

繼續閱讀