_23Threaded BinaryTree

可編譯運(yùn)行代碼見：GIithub::Data-Structures-Algorithms-and-Applications/_24Threaded_BinaryTree

線索二叉樹定義

在普通二叉樹中，有很多nullptr指針被浪費(fèi)了，可以將其利用起來。

首先我們要來看看這空指針有多少個呢？對于一個有n個結(jié)點(diǎn)的二叉鏈表，每個結(jié)點(diǎn)有指向左右孩子的兩個指針域，所以一共是2n個指針域。而n個結(jié)點(diǎn)的二叉樹一共有n-1條分支線數(shù)，也就是說，其實(shí)是存在2n-（n-1）=n+1個空指針域。

對上圖**(參考：《大話數(shù)據(jù)結(jié)構(gòu) 溢彩加強(qiáng)版 程杰》160頁圖)**做中序遍歷，得到了HDIBJEAFCG這樣的字符序列，遍歷過后，我們可以知道，結(jié)點(diǎn)I的前驅(qū)是D，后繼是B，結(jié)點(diǎn)F的前驅(qū)是A，后繼是C。也就是說，我們可以很清楚地知道任意一個結(jié)點(diǎn)，它的前驅(qū)和后繼是哪一個結(jié)點(diǎn)。

可是這是建立在已經(jīng)遍歷過的基礎(chǔ)之上的。在二叉鏈表上，我們只能知道每個結(jié)點(diǎn)指向其左右孩子結(jié)點(diǎn)的地址，而不知道某個結(jié)點(diǎn)的前驅(qū)是誰，后繼是誰。要想知道，必須遍歷一次。以后每次需要知道時，都必須先遍歷一次。這樣比較浪費(fèi)時間。

我們可以考慮利用那些空地址，存放指向結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的地址。我們把這種指向前驅(qū)和后繼的指針稱為線索，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹就稱為線索二叉樹（Threaded Binary Tree）。

我們把二叉樹進(jìn)行中序遍歷后，將所有的空指針域中的rchild，改為指向它的后繼結(jié)點(diǎn)。將所有空指針域中的lchild，改為指向當(dāng)前結(jié)點(diǎn)的前驅(qū)。由此得出，經(jīng)過線索化的二叉樹變成了一個雙向鏈表。雙向鏈表相比于二叉樹更容易找到某節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)。因此，如果所用的二叉樹需經(jīng)常遍歷或查找結(jié)點(diǎn)時需要某種遍歷序列中的前驅(qū)和后繼，那么采用線索二叉鏈表的存儲結(jié)構(gòu)就是非常不錯的選擇。

但是還有一個問題，如果將這些空指針作為線索后無法區(qū)分該指針是線索還是指向孩子節(jié)點(diǎn)，因此需要標(biāo)志位LTag為True表示該節(jié)點(diǎn)的左指針是索引，RLag為true表示該節(jié)點(diǎn)的右指針是索引，反之不是索引。

代碼

main.cpp

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17點(diǎn)06分
Last Version:			V1.0
Descriptions:			線索二叉樹
*/
#include "inThreadedBinaryTreeChains.h"
int main() {inThreadedBinaryTreeChainsTest();return 0;
}

inThreadedBinaryTreeChains.h

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17點(diǎn)06分
Last Version:			V1.0
Descriptions:			線索二叉樹鏈表表示
*/#ifndef _24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H
#define _24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H
#include <iostream>
#include "binaryTree.h"
#include "inThreadedBinaryTreeNode.h"
using namespace std;
/*二叉樹基礎(chǔ)測試函數(shù)*/
void inThreadedBinaryTreeChainsTest();
template<class E>
class inThreadedBinaryTreeChains : public binaryTree<inThreadedBinaryTreeNode<E>>
{
public:/*二叉樹的基礎(chǔ)成員函數(shù)*//*構(gòu)造函數(shù)函數(shù)*/inThreadedBinaryTreeChains() {root = nullptr; treeSize = 0;}/*析構(gòu)函數(shù)*/~inThreadedBinaryTreeChains() { erase(); }/*當(dāng)樹為空時，返回true；否則，返回false*/bool empty() const { return treeSize == 0; }/*返回元素個數(shù)*/int size() const { return treeSize; }void inOrderThreaded()  // 中序遍歷索引，就是中序遍歷的時候添加索引{pre = nullptr;inOrderThreaded(root);}/*中序遍歷二叉樹，使用函數(shù)指針的目的是是的本函數(shù)可以實(shí)現(xiàn)多種目的*/void inOrder(void(*theVisit)(inThreadedBinaryTreeNode<E>*)){visit = theVisit;/*是因?yàn)檫f歸，所以才要這樣的*/inOrder(root);/*這里調(diào)用的是靜態(tài)成員函數(shù)inOrder()*/}/*中序遍歷---輸出endl*/void inOrderOutput() { inOrder(output); cout << endl; }/*后續(xù)遍歷二叉樹，使用函數(shù)指針的目的是是的本函數(shù)可以實(shí)現(xiàn)多種目的*/void postOrder(void(*theVisit)(inThreadedBinaryTreeNode<E>*)){visit = theVisit;/*是因?yàn)檫f歸，所以才要這樣的*/postOrder(root);/*這里調(diào)用的是靜態(tài)成員函數(shù)inOrder()*/}/*后序遍歷---輸出endl*/void postOrderOutput() { postOrder(output); cout << endl; }/*清空二叉樹 這里必須使用后序遍歷 不然會出錯*/void erase(){postOrder(dispose);root = nullptr;treeSize = 0;}/*輸入時為了將root根節(jié)點(diǎn)傳遞給createBiTree()函數(shù)*/void input(void){createBiTree(root);}
private:
/*二叉樹基礎(chǔ)私有成員*/inThreadedBinaryTreeNode<E>* root;//指向根的指針int treeSize;//樹的結(jié)點(diǎn)個數(shù)static inThreadedBinaryTreeNode<E>* pre;// 在線索化時使用的前驅(qū)tempstatic void (*visit)(inThreadedBinaryTreeNode<E>*);//是一個函數(shù)指針,返回值為void 函數(shù)參數(shù)為binaryTreeNode<E>*static void inOrder(inThreadedBinaryTreeNode<E>* t);static void inOrderThreaded(inThreadedBinaryTreeNode<E>* t);// 中序遍歷索引，就是中序遍歷的時候添加索引static void postOrder(inThreadedBinaryTreeNode<E>* t);static void dispose(inThreadedBinaryTreeNode<E>* t) { delete t; }static void output(inThreadedBinaryTreeNode<E>* t) { cout << t->element << " "; }/*創(chuàng)建二叉樹---遞歸---作為私有成員只能被成員函數(shù)調(diào)用*/void createBiTree(inThreadedBinaryTreeNode<E>*& tree);
};
/*私有靜態(tài)成員初始化*/
/*這里是靜態(tài)函數(shù)指針成員的初始化，不初始化會引發(fā)LINK錯誤*/
template<class E>
void (*inThreadedBinaryTreeChains<E>::visit)(inThreadedBinaryTreeNode<E>*) = 0;      // visit function
// 這個地方需要做一個初始化，不做的話就會bug
template<class E>
inThreadedBinaryTreeNode<E>* inThreadedBinaryTreeChains<E>:: pre = nullptr;
/*中序遍歷 遞歸*/
/*不受索引影響的中序遍歷*/
template<class E>
void inThreadedBinaryTreeChains<E>::inOrder(inThreadedBinaryTreeNode<E>* t)
{if (t != nullptr){// 在其左孩子不是索引時遍歷if(!t->LTag)inOrder(t->leftChild);/*中序遍歷左子樹*/visit(t);/*訪問樹根*/// 在其右孩子不是索引時遍歷if(!t->RTag)inOrder(t->rightChild);/*中序遍歷右子樹*/}
}
/*中序遍歷索引 遞歸*/
/*本文寫法可以保證在多次調(diào)用此函數(shù)下依然能正常執(zhí)行，當(dāng)插入新元素后再執(zhí)行本函數(shù)可更新節(jié)點(diǎn)的索引*/
template<class E>
void inThreadedBinaryTreeChains<E>::inOrderThreaded(inThreadedBinaryTreeNode<E>* t)
{if (t != nullptr){if(!t->LTag)inOrderThreaded(t->leftChild);/*中序遍歷左子樹*/if(!t->leftChild || t->LTag) // 沒有左孩子，或者是第二次遍歷即左孩子指向了他的前驅(qū){t->LTag = true;t->leftChild = pre;}if(pre){if(!pre->rightChild || t->RTag)  // 如果前驅(qū)沒有右孩子，或者是第二次遍歷即右孩子指向了它的后繼{pre->RTag = true;pre->rightChild = t;}}pre = t;if(!t->RTag)inOrderThreaded(t->rightChild);/*中序遍歷右子樹*/}
}
/*后序遍歷 遞歸*/
/*不受索引影響的后序遍歷*/
template<class E>
void inThreadedBinaryTreeChains<E>::postOrder(inThreadedBinaryTreeNode<E>* t)
{if (t != nullptr){// 在其左孩子不是索引時遍歷if(!t->LTag)postOrder(t->leftChild);/*后序遍歷左子樹*/// 在其右孩子不是索引時遍歷if(!t->LTag)postOrder(t->rightChild);/*后序遍歷右子樹*/visit(t);/*訪問樹根*/}
}/*創(chuàng)建二叉樹---遞歸---模板的實(shí)現(xiàn)*/
template<class E>
void inThreadedBinaryTreeChains<E>::createBiTree(inThreadedBinaryTreeNode<E>*& tree)
{E data;cout << "Please enter the tree element:";while (!(cin >> data)){cin.clear();//清空標(biāo)志位while (cin.get() != '\n')//刪除無效的輸入continue;cout << "Please enter the tree element:";}cin.get();/*針對char類型的特例*/if (typeid(data) == typeid(char)) {if (data == '#')tree = nullptr;else {treeSize++;tree = new inThreadedBinaryTreeNode<E>(data);createBiTree(tree->leftChild);createBiTree(tree->rightChild);}}else/*針對其他類型*/{if (data == 999)tree = nullptr;//當(dāng)遇到999時，令樹的根節(jié)點(diǎn)為nullptr,從而結(jié)束該分支的遞歸else{treeSize++;tree = new inThreadedBinaryTreeNode<E>(data);createBiTree(tree->leftChild);createBiTree(tree->rightChild);}}
}
#endif //_24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H

inThreadedBinaryTreeChains.cpp

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17點(diǎn)06分
Last Version:			V1.0
Descriptions:			線索二叉樹測試函數(shù)
*/
#include "inThreadedBinaryTreeChains.h"
void inThreadedBinaryTreeChainsTest(){cout << endl << "******************************inThreadedBinaryTreeChains()函數(shù)開始**********************************" << endl;cout << endl << "測試成員函數(shù)*******************************************" << endl;cout << "輸入****************************" << endl;cout << "默認(rèn)構(gòu)造函數(shù)********************" << endl;inThreadedBinaryTreeChains<int> a;a.input();cout << "輸出****************************" << endl;cout << "中序輸出************************" << endl;//遞歸遍歷a.inOrderThreaded();cout << "a.inOrderOutput() = ";a.inOrderOutput();cout << "后序輸出************************" << endl;a.inOrderThreaded();cout << "a.postOrderOutput() = ";a.postOrderOutput();cout << "empty()*************************" << endl;cout << "a.empty() = " << a.empty() << endl;cout << "size()**************************" << endl;cout << "a.size() = " << a.size() << endl;cout << "erase()**************************" << endl;a.erase();cout << "a.inOrderOutput() = ";a.inOrderOutput();cout << "******************************inThreadedBinaryTreeChains()函數(shù)結(jié)束**********************************" << endl;
}

binaryTree.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月27日09點(diǎn)43分
Last Version:			V1.0
Descriptions:			二叉樹的抽象類
*/#ifndef _24THREADED_BINARYTREE_BINARYTREE_H
#define _24THREADED_BINARYTREE_BINARYTREE_H
template<class T>
class binaryTree
{
public:virtual ~binaryTree() {}virtual bool empty() const = 0;virtual int size() const = 0;
//    virtual void preOrder(void (*)(T*)) = 0;virtual void inOrder(void (*)(T*)) = 0;virtual void postOrder(void (*)(T*)) = 0;
//    virtual void levelOrder(void (*)(T*)) = 0;
};
#endif //_24THREADED_BINARYTREE_BINARYTREE_H

inThreadedBinaryTreeNode.h

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17點(diǎn)06分
Last Version:			V1.0
Descriptions:			線索二叉樹節(jié)點(diǎn)結(jié)構(gòu)體
*/#ifndef _24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H
#define _24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H
template<class T>
struct inThreadedBinaryTreeNode
{T element;inThreadedBinaryTreeNode<T>* leftChild,//左子樹*rightChild;//右子樹bool LTag, RTag;// 左右子樹指針是否為索引，為True則是索引，否則不是索引/*默認(rèn)構(gòu)造函數(shù)*/inThreadedBinaryTreeNode() { leftChild = rightChild = nullptr; LTag = RTag = false;}/*只初始化element*/inThreadedBinaryTreeNode(T melement){element = melement;leftChild = rightChild = nullptr;LTag = RTag = false;}/*三個元素都初始化*/inThreadedBinaryTreeNode(T melement, inThreadedBinaryTreeNode<T>* mleftChild, inThreadedBinaryTreeNode<T>* mrightChild){element = melement;leftChild = mleftChild;rightChild = mrightChild;LTag = RTag = false;}
};
#endif //_24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H

測試

"C:\Users\15495\Documents\Jasmine\prj\_Algorithm\Data Structures, Algorithms and Applications in C++\_24Threaded BinaryTree\cmake-build-debug\_24Threaded_BinaryTree.exe"******************************inThreadedBinaryTreeChains()函數(shù)開始**********************************測試成員函數(shù)*******************************************
輸入****************************
默認(rèn)構(gòu)造函數(shù)********************
Please enter the tree element:1
Please enter the tree element:2
Please enter the tree element:999
Please enter the tree element:999
Please enter the tree element:3
Please enter the tree element:999
Please enter the tree element:999
輸出****************************
中序輸出************************
a.inOrderOutput() = 2 1 3
后序輸出************************
a.postOrderOutput() = 2 3 1
empty()*************************
a.empty() = 0
size()**************************
a.size() = 3
erase()**************************
a.inOrderOutput() =
******************************inThreadedBinaryTreeChains()函數(shù)結(jié)束**********************************Process finished with exit code 0