站长工具是什么意思,抖音推广平台入口,网站域名如何使用,梵客家装口碑怎么样_23Threaded BinaryTree
可编译运行代码见#xff1a;GIithub::Data-Structures-Algorithms-and-Applications/_24Threaded_BinaryTree
线索二叉树定义
在普通二叉树中#xff0c;有很多nullptr指针被浪费了#xff0c;可以将其利用起来。 首先我们要来看看这空指针有多少…_23Threaded BinaryTree
可编译运行代码见GIithub::Data-Structures-Algorithms-and-Applications/_24Threaded_BinaryTree
线索二叉树定义
在普通二叉树中有很多nullptr指针被浪费了可以将其利用起来。 首先我们要来看看这空指针有多少个呢对于一个有n个结点的二叉链表每个结点有指向左右孩子的两个指针域所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线数也就是说其实是存在2n-n-1n1个空指针域。
对上图**(参考《大话数据结构 溢彩加强版 程杰》160页图)**做中序遍历得到了HDIBJEAFCG这样的字符序列遍历过后我们可以知道结点I的前驱是D后继是B结点F的前驱是A后继是C。也就是说我们可以很清楚地知道任意一个结点它的前驱和后继是哪一个结点。
可是这是建立在已经遍历过的基础之上的。在二叉链表上我们只能知道每个结点指向其左右孩子结点的地址而不知道某个结点的前驱是谁后继是谁。要想知道必须遍历一次。以后每次需要知道时都必须先遍历一次。这样比较浪费时间。
我们可以考虑利用那些空地址存放指向结点在某种遍历次序下的前驱和后继结点的地址。我们把这种指向前驱和后继的指针称为线索加上线索的二叉链表称为线索链表相应的二叉树就称为线索二叉树Threaded Binary Tree。
我们把二叉树进行中序遍历后将所有的空指针域中的rchild改为指向它的后继结点。将所有空指针域中的lchild改为指向当前结点的前驱。由此得出经过线索化的二叉树变成了一个双向链表。双向链表相比于二叉树更容易找到某节点的前驱和后继节点。因此如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继那么采用线索二叉链表的存储结构就是非常不错的选择。
但是还有一个问题如果将这些空指针作为线索后无法区分该指针是线索还是指向孩子节点因此需要标志位LTag为True表示该节点的左指针是索引RLag为true表示该节点的右指针是索引反之不是索引。
代码
main.cpp
/*
Project name : _24Threaded_BinaryTree
Last modified Date: 2023年11月28日17点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点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;
/*二叉树基础测试函数*/
void inThreadedBinaryTreeChainsTest();
templateclass E
class inThreadedBinaryTreeChains : public binaryTreeinThreadedBinaryTreeNodeE
{
public:/*二叉树的基础成员函数*//*构造函数函数*/inThreadedBinaryTreeChains() {root nullptr; treeSize 0;}/*析构函数*/~inThreadedBinaryTreeChains() { erase(); }/*当树为空时返回true否则返回false*/bool empty() const { return treeSize 0; }/*返回元素个数*/int size() const { return treeSize; }void inOrderThreaded() // 中序遍历索引就是中序遍历的时候添加索引{pre nullptr;inOrderThreaded(root);}/*中序遍历二叉树使用函数指针的目的是是的本函数可以实现多种目的*/void inOrder(void(*theVisit)(inThreadedBinaryTreeNodeE*)){visit theVisit;/*是因为递归所以才要这样的*/inOrder(root);/*这里调用的是静态成员函数inOrder()*/}/*中序遍历---输出endl*/void inOrderOutput() { inOrder(output); cout endl; }/*后续遍历二叉树使用函数指针的目的是是的本函数可以实现多种目的*/void postOrder(void(*theVisit)(inThreadedBinaryTreeNodeE*)){visit theVisit;/*是因为递归所以才要这样的*/postOrder(root);/*这里调用的是静态成员函数inOrder()*/}/*后序遍历---输出endl*/void postOrderOutput() { postOrder(output); cout endl; }/*清空二叉树 这里必须使用后序遍历 不然会出错*/void erase(){postOrder(dispose);root nullptr;treeSize 0;}/*输入时为了将root根节点传递给createBiTree()函数*/void input(void){createBiTree(root);}
private:
/*二叉树基础私有成员*/inThreadedBinaryTreeNodeE* root;//指向根的指针int treeSize;//树的结点个数static inThreadedBinaryTreeNodeE* pre;// 在线索化时使用的前驱tempstatic void (*visit)(inThreadedBinaryTreeNodeE*);//是一个函数指针,返回值为void 函数参数为binaryTreeNodeE*static void inOrder(inThreadedBinaryTreeNodeE* t);static void inOrderThreaded(inThreadedBinaryTreeNodeE* t);// 中序遍历索引就是中序遍历的时候添加索引static void postOrder(inThreadedBinaryTreeNodeE* t);static void dispose(inThreadedBinaryTreeNodeE* t) { delete t; }static void output(inThreadedBinaryTreeNodeE* t) { cout t-element ; }/*创建二叉树---递归---作为私有成员只能被成员函数调用*/void createBiTree(inThreadedBinaryTreeNodeE* tree);
};
/*私有静态成员初始化*/
/*这里是静态函数指针成员的初始化不初始化会引发LINK错误*/
templateclass E
void (*inThreadedBinaryTreeChainsE::visit)(inThreadedBinaryTreeNodeE*) 0; // visit function
// 这个地方需要做一个初始化不做的话就会bug
templateclass E
inThreadedBinaryTreeNodeE* inThreadedBinaryTreeChainsE:: pre nullptr;
/*中序遍历 递归*/
/*不受索引影响的中序遍历*/
templateclass E
void inThreadedBinaryTreeChainsE::inOrder(inThreadedBinaryTreeNodeE* t)
{if (t ! nullptr){// 在其左孩子不是索引时遍历if(!t-LTag)inOrder(t-leftChild);/*中序遍历左子树*/visit(t);/*访问树根*/// 在其右孩子不是索引时遍历if(!t-RTag)inOrder(t-rightChild);/*中序遍历右子树*/}
}
/*中序遍历索引 递归*/
/*本文写法可以保证在多次调用此函数下依然能正常执行当插入新元素后再执行本函数可更新节点的索引*/
templateclass E
void inThreadedBinaryTreeChainsE::inOrderThreaded(inThreadedBinaryTreeNodeE* t)
{if (t ! nullptr){if(!t-LTag)inOrderThreaded(t-leftChild);/*中序遍历左子树*/if(!t-leftChild || t-LTag) // 没有左孩子或者是第二次遍历即左孩子指向了他的前驱{t-LTag true;t-leftChild pre;}if(pre){if(!pre-rightChild || t-RTag) // 如果前驱没有右孩子或者是第二次遍历即右孩子指向了它的后继{pre-RTag true;pre-rightChild t;}}pre t;if(!t-RTag)inOrderThreaded(t-rightChild);/*中序遍历右子树*/}
}
/*后序遍历 递归*/
/*不受索引影响的后序遍历*/
templateclass E
void inThreadedBinaryTreeChainsE::postOrder(inThreadedBinaryTreeNodeE* t)
{if (t ! nullptr){// 在其左孩子不是索引时遍历if(!t-LTag)postOrder(t-leftChild);/*后序遍历左子树*/// 在其右孩子不是索引时遍历if(!t-LTag)postOrder(t-rightChild);/*后序遍历右子树*/visit(t);/*访问树根*/}
}/*创建二叉树---递归---模板的实现*/
templateclass E
void inThreadedBinaryTreeChainsE::createBiTree(inThreadedBinaryTreeNodeE* tree)
{E data;cout Please enter the tree element:;while (!(cin data)){cin.clear();//清空标志位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 inThreadedBinaryTreeNodeE(data);createBiTree(tree-leftChild);createBiTree(tree-rightChild);}}else/*针对其他类型*/{if (data 999)tree nullptr;//当遇到999时令树的根节点为nullptr,从而结束该分支的递归else{treeSize;tree new inThreadedBinaryTreeNodeE(data);createBiTree(tree-leftChild);createBiTree(tree-rightChild);}}
}
#endif //_24THREADED_BINARYTREE_INTHREADEDBINARYTREE_HinThreadedBinaryTreeChains.cpp
/*
Project name : _24Threaded_BinaryTree
Last modified Date: 2023年11月28日17点06分
Last Version: V1.0
Descriptions: 线索二叉树测试函数
*/
#include inThreadedBinaryTreeChains.h
void inThreadedBinaryTreeChainsTest(){cout endl ******************************inThreadedBinaryTreeChains()函数开始********************************** endl;cout endl 测试成员函数******************************************* endl;cout 输入**************************** endl;cout 默认构造函数******************** endl;inThreadedBinaryTreeChainsint 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()函数结束********************************** endl;
}binaryTree.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月27日09点43分
Last Version: V1.0
Descriptions: 二叉树的抽象类
*/#ifndef _24THREADED_BINARYTREE_BINARYTREE_H
#define _24THREADED_BINARYTREE_BINARYTREE_H
templateclass 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_HinThreadedBinaryTreeNode.h
/*
Project name : _24Threaded_BinaryTree
Last modified Date: 2023年11月28日17点06分
Last Version: V1.0
Descriptions: 线索二叉树节点结构体
*/#ifndef _24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H
#define _24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H
templateclass T
struct inThreadedBinaryTreeNode
{T element;inThreadedBinaryTreeNodeT* leftChild,//左子树*rightChild;//右子树bool LTag, RTag;// 左右子树指针是否为索引为True则是索引否则不是索引/*默认构造函数*/inThreadedBinaryTreeNode() { leftChild rightChild nullptr; LTag RTag false;}/*只初始化element*/inThreadedBinaryTreeNode(T melement){element melement;leftChild rightChild nullptr;LTag RTag false;}/*三个元素都初始化*/inThreadedBinaryTreeNode(T melement, inThreadedBinaryTreeNodeT* mleftChild, inThreadedBinaryTreeNodeT* 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()函数开始**********************************测试成员函数*******************************************
输入****************************
默认构造函数********************
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()函数结束**********************************Process finished with exit code 0
