??本代碼主要參考了大話數據結構的思想，由于其為c語言版，所以本人對其中一些函數進行了封裝，并增加了一些新的功能。

??由于本代碼的基本思想在大話數據結構書中已經說的很清楚了，所以此處就不再進行說明代碼原理。

??并且，在每個函數的后面，都寫了其作用，本人也盡可能地在必要的地方加了注釋。并且為了省事，用了shared_ptr。

??寫此代碼的目的是為了讓簡單線索二叉樹的代碼更加規范一點（很多c代碼都是用全局變量等不規范的形式）。此代碼在vs2019上能執行，編譯器需要支持c++11以上。

文章目錄

• 一、線索二叉樹節點類~
• 二、線索二叉樹類~
• 三、完整頭文件~
• 四、測試cpp~

一、線索二叉樹節點類~

using std::cout; using std::endl; using std::shared_ptr; using std::make_shared;namespace {enum class PointerTag{Linked, Thread}; }template<typename T = int> struct ThreadNode { public:using ThreadNodePtr = shared_ptr<ThreadNode<T>>;public:T _data;ThreadNodePtr _lchild;ThreadNodePtr _rchild;PointerTag _lTag;/*左右標簽*/PointerTag _rTag;ThreadNode(const T& data) :_data(data),_lchild(nullptr),_rchild(nullptr),_lTag(PointerTag::Linked),_rTag(PointerTag::Linked) {}ThreadNode(const ThreadNode& other):_data(other._data),_lchild(other._lchild),_rchild(other._rchild),_lTag(other._lTag),_rTag(other._rTag){} };

二、線索二叉樹類~

template<typename T = int>class ThreadTree {public:using ThreadNodePtr = shared_ptr<ThreadNode<T>>;private:ThreadNodePtr _root;/*根節點*/ThreadNodePtr _hot;//剛被訪問過的節點ThreadNodePtr _head;//線索二叉樹頭節點哨兵public:ThreadTree() :_root(nullptr), _hot(nullptr), _head(nullptr) {}ThreadTree(T* PrevOrder, T* InOrder, const int& num) :_hot(nullptr), _head(nullptr) {//以前序和中序序列創建二叉樹_root = buildTree(PrevOrder, InOrder, num);}void InThread();//從根節點開始，線索化二叉樹void InOrderTrav_Thread()const;//以線索二叉樹的方式進行遍歷private:ThreadNodePtr buildTree(T* PrevOrder, T* InOrder, const int& num);//以前序和中序序列創建二叉樹void InThreading(ThreadNodePtr); /*對根節點進行中序線索化*/};

三、完整頭文件~

#pragma once using std::cout; using std::endl; using std::shared_ptr; using std::make_shared;namespace my_thread_tree {namespace {enum class PointerTag{Linked, Thread};}template<typename T = int>struct ThreadNode {public:using ThreadNodePtr = shared_ptr<ThreadNode<T>>;public:T _data;ThreadNodePtr _lchild;ThreadNodePtr _rchild;PointerTag _lTag;/*左右標簽*/PointerTag _rTag;ThreadNode(const T& data) :_data(data),_lchild(nullptr),_rchild(nullptr),_lTag(PointerTag::Linked),_rTag(PointerTag::Linked) {}ThreadNode(const ThreadNode& other):_data(other._data),_lchild(other._lchild),_rchild(other._rchild),_lTag(other._lTag),_rTag(other._rTag){}};template<typename T = int>class ThreadTree {public:using ThreadNodePtr = shared_ptr<ThreadNode<T>>;private:ThreadNodePtr _root;/*根節點*/ThreadNodePtr _hot;//剛被訪問過的節點ThreadNodePtr _head;//線索二叉樹頭節點哨兵public:ThreadTree() :_root(nullptr), _hot(nullptr), _head(nullptr) {}ThreadTree(T* PrevOrder, T* InOrder, const int& num) :_hot(nullptr), _head(nullptr) {//以前序和中序序列創建二叉樹_root = buildTree(PrevOrder, InOrder, num);}void InThread();//從根節點開始，線索化二叉樹void InOrderTrav_Thread()const;//以線索二叉樹的方式進行遍歷private:ThreadNodePtr buildTree(T* PrevOrder, T* InOrder, const int& num);//以前序和中序序列創建二叉樹void InThreading(ThreadNodePtr); /*對根節點進行中序線索化*/};template<typename T>void ThreadTree<T>::InOrderTrav_Thread()const{ThreadNodePtr p = _root;//指向根節點while (p != _head) {//當沒有遍歷到頭節點哨兵時while (p->_lTag == PointerTag::Linked)//一直往左，直到左孩子記錄的為前驅而不是左孩子時p = p->_lchild;cout << "數據為:\t" << p->_data << "\t引用計數為:\t" << p.use_count() << endl;while (p->_rTag == PointerTag::Thread && p->_rchild != _head) {//遍歷到直到p的右孩子為右孩子而不是后繼時p = p->_rchild;cout << "數據為:\t" << p->_data << "\t引用計數為:\t" << p.use_count() << endl;}p = p->_rchild;//p進入右子樹根}cout << endl;}template<typename T>shared_ptr<ThreadNode<T>> ThreadTree<T>::buildTree(T* PrevOrder, T* InOrder, const int& num){if (PrevOrder == nullptr || InOrder == nullptr || num <= 0){return nullptr;}ThreadNodePtr root =make_shared<ThreadNode<T>>(PrevOrder[0]);// 前序遍歷的第一個數據就是根節點數據 //中序遍歷，根節點左為左子樹，右為右子樹 int rootposition = -1;for (int i = 0; i < num; i++){if (InOrder[i] == root->_data){rootposition = i;}}if (rootposition == -1)return nullptr;//重建左子樹(根節點)遞歸 int LeftNum = rootposition;T* PrevOrderLeft = PrevOrder + 1; //前序第二個即為根節點的左子樹 T* InOrderLeft = InOrder; //中序第一個 即為其左子樹。 root->_lchild = buildTree(PrevOrderLeft, InOrderLeft, LeftNum);//重建右子樹(根節點)遞歸 int RightNum = num - LeftNum - 1;//右半邊子樹T* PrevOrderRight = PrevOrder + 1 + LeftNum;T* InOrderRight = InOrder + LeftNum + 1;root->_rchild = buildTree(PrevOrderRight, InOrderRight, RightNum);return root;}template<typename T>void ThreadTree<T>::InThreading(ThreadNodePtr p){if (p != nullptr) {InThreading(p->_lchild);if (p->_lchild == nullptr) {p->_lTag = PointerTag::Thread;p->_lchild = _hot;//p的左孩子設為前驅}if (_hot != nullptr && _hot->_rchild == nullptr) {//前驅的右孩子為空時_hot->_rTag = PointerTag::Thread;_hot->_rchild = p;//將前驅的右孩子設為p}_hot = p;InThreading(p->_rchild);}}template<typename T>void ThreadTree<T>::InThread() {//從根節點開始，線索化二叉樹if (_root == nullptr)return;//頭哨兵節點初始化_head = make_shared<ThreadNode<T>>(0);//反正不會訪問這個，所以初值不妨就設成0_head->_rTag = PointerTag::Thread;_head->_lchild = _root;_head->_rchild = _head;_hot = _head;//將_hot設定為_headInThreading(_root);//線索化二叉樹//遍歷之后，_hot必然為中序遍歷最右邊那個節點_hot->_rTag = PointerTag::Thread;_hot->_rchild = _head;//就將頭哨兵作為_hot的右孩子_head->_rchild = _hot;//并且將_hot作為頭哨兵的右孩子}}//namespace my_thread_tree

四、測試cpp~

#include <iostream> #include "ThreadTree.h" using namespace std; using namespace my_thread_tree;int main() {//int a[] = { 3,1,0,2,5,4,6 };//int b[] = { 0,1,2,3,4,5,6 };char a[] = { 'A','B','D','H','I','E','J','C','F','G'};char b[] = { 'H','D','I','B','J','E','A','F','C','G' };ThreadTree<char> TT(a, b, 10);//傳參時傳入兩個數組，分別為樹的前序和中序遍歷序列TT.InThread();TT.InOrderTrav_Thread();return 0; }

引用計數這個可以忽略，主要是玩下看有多少個指針指向這個對象

數據為: H 引用計數為: 2 數據為: D 引用計數為: 4 數據為: I 引用計數為: 2 數據為: B 引用計數為: 4 數據為: J 引用計數為: 2 數據為: E 引用計數為: 3 數據為: A 引用計數為: 5 數據為: F 引用計數為: 2 數據為: C 引用計數為: 4 數據為: G 引用計數為: 4

總結

以上是生活随笔為你收集整理的c++ 实现线索二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。