C語言中序周遊實作線索二叉樹（二叉樹的改進）

文章目錄

• 結構體
• 初始化
• 建立中序線索二叉樹
• • • 線索化的規則是：左線索指針指向目前結點在中序周遊序列中的前驅結點，右線索指針指向後繼結點
  • 下面以這棵二叉樹進行分析
  • • • 1.遞歸找到根的左孩子的左孩子……（即中序周遊的第一個結點）
• 擷取第一個結點
• 擷取最後一個結點
• 擷取目前結點的前驅
• 擷取目前結點的後繼
• 擷取目前結點的父結點
• 線索二叉樹的中序周遊
• 查找指定的元素
• 測試

結構體

#define ElemType char

typedef enum{LINK,THREAD}Tag_Type;//LINK表示指針,指向結點的左右孩子
                                  //THREAD表示線索，指向結點的前驅(L)或後繼(R)
typedef struct BinTreeNode
{
	ElemType data;
	struct BinTreeNode *leftChild;
	struct BinTreeNode *rightChild;
	Tag_Type ltag;//線索标記
	Tag_Type rtag;
}BinTreeNode;

typedef struct BinTree
{
	BinTreeNode *root;
	ElemType     refvalue; //stop value
}BinTree;
           

初始化

void InitBinTree(BinTree *bt, ElemType ref)
{
	bt->root = NULL;
	bt->refvalue = ref;
}

//用于開辟一個新結點的空間和這個結點鍊的初始化
BinTreeNode* _Buynode(ElemType x)
{
	BinTreeNode *s = (BinTreeNode*)malloc(sizeof(BinTreeNode));
	assert(s != NULL);
	s->data = x;//給這個空間指派（資料）
	s->leftChild = s->rightChild = NULL;
	s->ltag = s->rtag = LINK;//一開始标記為指針，指向左右孩子
	return s;
}
           

建立中序線索二叉樹

線索化的規則是：左線索指針指向目前結點在中序周遊序列中的前驅結點，右線索指針指向後繼結點

void CreateInThread(BinTree *bt)
{
	BinTreeNode *pre = NULL;//一開始前驅結點設為NULL
	CreateInThread(bt->root,pre);
	pre->rightChild = NULL;//如果是最後一個元素，他沒有後繼
	pre->rtag = THREAD;
}
void CreateInThread(BinTreeNode *&t, BinTreeNode *&pre)
{//t表示指向根節點的指針
	if(t == NULL)
		return;
	CreateInThread(t->leftChild,pre);
	//建立目前節點的額前驅線索
	if(t->leftChild == NULL)
	{
		t->ltag = THREAD;
		t->leftChild = pre;
	}
	//建立前驅結點的後繼線索
	if(pre!=NULL && pre->rightChild==NULL)
	{
		pre->rtag = THREAD;
		pre->rightChild = t;
	}
	pre = t;
	CreateInThread(t->rightChild,pre);
}
           

下面以這棵二叉樹進行分析

沒有加入線索前的線索二叉樹

該二叉樹的中序周遊轉化為線性結構的順序是CBEDFAGH

1.遞歸找到根的左孩子的左孩子……（即中序周遊的第一個結點）

遞歸到C後繼續遞歸，發現遞歸到C的左孩子為空，于是跳出遞歸，這樣就找到了C，執行遞歸後面的代碼，發現C的左孩子是空的，

左标記标記為Thread（書上把他當做1，說明這是個線索，指向前驅），此時C的左孩子就相當于指向C的前驅。

繼續執行，C的前驅為空，不執行下面的if

pre前驅結點指向C

繼續周遊t的右孩子（此時t是C），C沒有右孩子，return ；

接下來指針t回到了C

因為遞歸會傳回原來因為一些條件沒有被執行完的東西，t這時回到了B

B的左孩子不為空，不執行第一個if，但是此時pre（也就是C）不為空且pre（C）的右孩子為空，執行第二個if

這時就完成了C的前驅和後繼，B的前驅

然後pre指針指向此時的t（即B），因為B左右都有孩子，是以标志為LINk

遞歸周遊B的右孩子，此時在遞歸執行B的右孩子的左孩子（即D）時，又發現了左孩子，繼續遞歸，到達了E

pre指針指向了E，然後建立對前驅結點（即E）的後繼線索

t指針繼續指向t的後孩子，發現為空，回退到E,接着回退到D，建立E（pre）的後繼是D（即現在的t）

pre指向D

然後對D的右孩子，F先建立前驅線索，當t回退到A時，再建立F的後繼線索，如此往複，直到pre指向最後一個結點，讓pre的後繼指向NULL。

得到了一顆線索二叉樹

擷取第一個結點

BinTreeNode* First(BinTree *bt)
{
	return First(bt->root);
}
BinTreeNode* First(BinTreeNode *t)//中序周遊的第一個結點就是根結點的左孩子的左孩子……直到那個左孩子的左孩子是空
{
	if(t == NULL)
		return NULL;
	BinTreeNode *p = t;//p指針先指向根結點
	while(p->ltag == LINK)
		p = p->leftChild;
	return p;
}
           

擷取最後一個結點

BinTreeNode* Last(BinTree *bt)
{
	return Last(bt->root);
}
BinTreeNode* Last(BinTreeNode *t)
{
	if(t == NULL)
		return NULL;
	BinTreeNode *p = t;
	while(p->rtag == LINK)//根結點的右子樹中，隻要右标記為線，說明這是最後一個結點
		p = p->rightChild;
	return p;
}
           

擷取目前結點的前驅

BinTreeNode* Prio(BinTree *bt, BinTreeNode *cur)
{
	return Prio(bt->root,cur);
}
BinTreeNode* Prio(BinTreeNode *t, BinTreeNode *cur)
{
	if(t==NULL || cur==NULL)
		return NULL;
	if(cur->ltag == THREAD)//如果目前結點的左标記是線索（1），說明指向的是前驅結點
		return cur->leftChild;
	return Last(cur->leftChild);//如果是A位置,他的前驅就是F，即A的左子樹的最後一個結點
}
           

擷取目前結點的後繼

BinTreeNode* Next(BinTree *bt, BinTreeNode *cur)
{
	return Next(bt->root,cur);
}
BinTreeNode* Next(BinTreeNode *t, BinTreeNode *cur)
{
	if(t==NULL || cur==NULL)
		return NULL;
	if(cur->rtag == THREAD)//如果目前結點的右标記是線索（1），說明指向的是後繼
		return cur->rightChild;
	return First(cur->rightChild);//如果目前結點的左右線索是0，如B，D的位置，就需要先找到B的右子樹中序周遊的第一個節點（即E），E就是B的後繼
}
           

擷取目前結點的父結點

BinTreeNode* Parent(BinTree *bt, BinTreeNode *cur)
{
	return Parent(bt->root,cur);
}
BinTreeNode* Parent(BinTreeNode *t, BinTreeNode *cur)
{
	if(t==NULL || cur==NULL)
		return NULL;
	if(t == cur)
		return NULL;
/**************如果目前結點有線索，那父節點可能存在于  前驅的右孩子  或   後繼的左孩子******************/
	BinTreeNode *p;
	//如E的後繼D就是E的父結點， G的前驅A就是G的的父節點
	if(cur->ltag == THREAD)
	{
		p = cur->leftChild;//若目前結點是E，p就是B                              若目前結點是G，p就是A
		if(p->rightChild == cur)//若B的右子樹是E，直接傳回，但是并不是。            顯然A的右子樹就是G，直接傳回
			return p;
	}
	if(cur->rtag == THREAD)
	{
		p = cur->rightChild;//目前結點是E，p就是D
		if(p->leftChild == cur)//p的左子樹是目前結點E，直接傳回p（即D）
			return p;
	}
/*************如果目前結點沒有線索如B，D結點***************************************/
	p = First(cur->leftChild);//若目前結點是D，p就是D左孩子中的第一個結點（即E）        //若目前結點是B，p就是C
	p = p->leftChild;//第一個結點可定有前驅，此時E的前驅就是B，p=B						//C的前驅是NULL，不執行面的if
	if(p!=NULL && p->rightChild == cur)//B的右孩子就是D，直接傳回
		return p;

	p = Last(cur->rightChild);                                                   //找到B的右子樹的最後一個結點，即F
	return p->rightChild;                                                         //傳回找到F的後繼A，顯然A就是B的父節點
}
           

線索二叉樹的中序周遊

在樹的結點上增加了線索，不能按照左孩子右孩子的遞歸周遊了。

思路是根據依次找到p的前驅和後繼，讓p=p的後繼，循環輸出。例如先找到了C，根據C找到後繼B，此時讓p=B，開始找到B的後繼E……

void InOrder(BinTree *bt)
{
	InOrder(bt->root);
}
void InOrder(BinTreeNode *t)
{
	BinTreeNode *p;
	for(p=First(t); p!=NULL; p=Next(t,p))//p=Next(t,p)，讓p=目前結點的後繼
	{
		printf("%c ",p->data);
	}
	printf("\n");
}
           

查找指定的元素

BinTreeNode* Search(BinTree *bt, ElemType key)
{
	return Search(bt->root,key);
}
BinTreeNode* Search(BinTreeNode *t, ElemType key)
{
	if(t == NULL)
		return NULL;
	if(t->data == key)//如果剛好查找的是樹根，直接傳回。如果這個if不加，當然下面的循環也會查找到根，有利有弊
		return t;

	BinTreeNode *p;
	for(p=First(t); p!=NULL; p=Next(t,p))//根據周遊為線性結構，循環查找
	{
		if(p->data == key)
			return p;
	}
	return NULL;

}
           

測試

void main()
{
	char *str = "ABC##DE##F##G#H##";
	BinTree mytree;
	InitBinTree(&mytree,'#');
	CreateBinTree(&mytree,str);

	CreateInThread(&mytree);

	//BinTreeNode *p = Search(&mytree,'B');
	//BinTreeNode *parent = Parent(&mytree,p);
	//BinTreeNode *q = Prio(&mytree,p);
	//InOrder(&mytree);
}