C語言線索二叉樹結構怎么實現

這篇文章主要講解了“C語言線索二叉樹結構怎么實現”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C語言線索二叉樹結構怎么實現”吧！

線索二叉樹的意義

• 對于一個有n個節點的二叉樹，每個節點有指向左右孩子的指針域。其中會出現n+ 1個空指針域，這些空間不儲存任何事物，浪費著內存的資源。

• 對于一些需要頻繁進行二叉樹遍歷操作的場合，二叉樹的非遞歸遍歷操作過程相對比較復雜，遞歸遍歷雖然簡單明了，但是會有額外的開銷，對于操作的時間和空間都比較浪費。

• 我們可以考慮利用這些空地址，存放指向節點在某種遍歷次序下的前驅和后繼節點的地址。通過這些前驅和后繼節點的地址可以知道，從當前位置下一步應該走向哪里。

線索二叉樹的定義

• 指向前驅和后繼的指針稱為線索，加上線索的二叉鏈表稱為線索鏈表，相應的二叉樹就稱為線索二叉樹。

• 對二叉樹以某種次序遍歷使其變為線索二叉樹的過程稱為線索化。

線索二叉樹結構的實現

二叉樹的線索存儲結構

為了區分二叉樹某一節點是指向它的孩子節點還是指向前驅或者后繼節點，我們可以在每個節點增設兩個標志，Ltag，Rtag.

其中:

• Ltag為0時，代表該節點指向它的左孩子，Ltag為1時，代表該節點指向它的前驅節點。

• Rtag為0時，代表該節點指向它的右孩子，Rtag為1時，代表該節點指向它的后繼節點。

所以，線索二叉樹結構定義代碼如下：

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的前驅是空，后繼是B
  B的前驅是D，后繼是E
  E的前驅是B，后繼是A
  F的前驅是A，后繼是C
  C的前驅是F，后繼是空

線索化后：

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

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

分析：

• if (!p->left)表示如果某節點的左指針域為空，因為其前驅節點剛剛訪問過，并且賦值給了pre，所以可以將pre賦值給 l -> left，并且修改 p-> LTag = Thread，以完成前驅節點的線索化。

• pre 是 p 的前驅，那么， p 就是 pre 的后繼。當pre -> right 為空時，就可以將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)從根節點開始遍歷，如果左標記是Link讓它一直循環下去，直到找到標記為Thread的的結點，也就是要遍歷的第一個結點，然后根據后驅指針找到后繼結點

• 后面就是重復以上過程，直到遍歷完整個二叉數。

感謝各位的閱讀，以上就是“C語言線索二叉樹結構怎么實現”的內容了，經過本文的學習后，相信大家對C語言線索二叉樹結構怎么實現這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！