|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
《数据结构C++描述》 清华大学出版社 任燕编著
小弟学习一下中序穿线二叉树,发现里面有很多的方法都和普通的二叉树有所不同,
比如遍历,删除结点等方法都和普通二叉树的方法有较大差异,同时小弟也是改正了书上类模板程序中一个方法的bug
还请大神指教,加油!!!- #include <iostream>
- #include <cstdlib>
- #include <assert.h>
- #include <cstdbool>
- using namespace std;
- typedef enum PointerTag{ LINK, THREAD }; //相当于LINK = 0,THREAD = 1
- template <typename elemtype>
- class ThreadTree{
- public:
- //中序穿线二叉树(二叉链表存储)结点的数据结构C++类定义
- class ThreadTNode{
- public:
- //这里的构造函数已经给赋值ltag = LINK和rtag = LINK,所以接下来
- //线索话操作只管THREAD赋值即可
- ThreadTNode() :ltag(LINK), left(NULL), rtag(LINK), right(NULL){};
- ~ThreadTNode(){};
- public:
- elemtype data; //数据域
- class ThreadTNode *left, *right; //左右指针域
- PointerTag ltag, rtag; //左右指针标记
- };
- typedef ThreadTNode* NodePointer; //指向结点的指针类型声明
- public:
- //中序穿线二叉树置空
- void clear();
- //中序穿线二叉树置空辅助函数
- void clear_aux(NodePointer p);
- //递归求中序穿线二叉树的深度
- int depth();
- //递归求中序穿线二叉树的深度的辅助函数
- int depth_aux(NodePointer p);
- //取中序穿线二叉树的根指针
- NodePointer getRoot();
- //中序遍历中序穿线二叉树
- void inOrderTraverse_ThreadTree();
- //中序遍历中序穿线二叉树的辅助函数
- void inOrderTraverse_ThreadTree_aux(NodePointer p);
- //判断是否为空
- bool isEmpty();
- //生成中序穿线二叉树
- void CreateThreadTree();
- //生成中序穿线二叉树的辅助函数
- void CreateThreadTree_aux(NodePointer &p);
- //中序穿线二叉树穿线操作
- void seqToThreadTree();
- //中序穿线二叉树穿线操作的辅助函数
- void seqToThreadTree_aux(NodePointer &p);
- //找指定结点中序的前驱
- bool searchPriorNode(elemtype key, elemtype& prior);
- //找指定结点中序的后继
- bool searchNextNode(elemtype key, elemtype& next);
- //找指定结点
- bool searchNode(elemtype key, NodePointer &p);
- //中序穿线二叉树构造函数重载
- ThreadTree();
- //析构函数
- ~ThreadTree();
- private:
- NodePointer root;
- };
- //取二叉树的根指针
- template <typename elemtype>
- typename ThreadTree<elemtype>::NodePointer ThreadTree<elemtype>::getRoot(){
- return root;
- }
- //中序穿线二叉树构造函数重载
- template <typename elemtype>
- ThreadTree<elemtype>::ThreadTree(){
- root = NULL;
- }
- //创建中序穿线二叉树
- template <typename elemtype>
- void ThreadTree<elemtype>::CreateThreadTree(){
- CreateThreadTree_aux(root);
- }
- //创建中序穿线二叉树的辅助函数
- template <typename elemtype>
- void ThreadTree<elemtype>::CreateThreadTree_aux(NodePointer &p){
- elemtype value;
- cout << "请输入结点的值(输入零代表叶子的终结):";
- cin >> value;
- if (value == 0){
- p = NULL;
- }
- else{
- p = new ThreadTNode;
- assert(p != 0);
- p->data = value;
- CreateThreadTree_aux(p->left);
- CreateThreadTree_aux(p->right);
- }
- }
- //删除中序穿线二叉树
- template <typename elemtype>
- void ThreadTree<elemtype>::clear(){
- clear_aux(root);
- }
- //删除中序穿线二叉树的辅助函数
- template <typename elemtype>
- void ThreadTree<elemtype>::clear_aux(NodePointer p){
- if (p){
- if (p->ltag == LINK){
- clear_aux(p->left);
- }
- if (p->rtag == LINK){
- clear_aux(p->right);
- }
- delete p;
- cout << "删除结点..." << endl;
- }
- }
- //析构函数
- template <typename elemtype>
- ThreadTree<elemtype>::~ThreadTree(){
- clear();
- root = NULL; //根指针置空
- }
- //中序遍历中序穿线二叉树
- template <typename elemtype>
- void ThreadTree<elemtype>::inOrderTraverse_ThreadTree(){
- inOrderTraverse_ThreadTree_aux(root);
- }
- //中序遍历中序穿线二叉树操作
- template <typename elemtype>
- void ThreadTree<elemtype>::inOrderTraverse_ThreadTree_aux(NodePointer p){
- while (p){
- //首先沿着其左子树的左指针向下滑动,直到某结点有左线索为止
- while (p->ltag == LINK){
- p = p->left;
- }
- //访问该结点
- cout << p->data << "\t";
- //如果该结点有右线索,那么沿着右线索一直往上爬,访问右线索上的每一个结点
- //直到某结点不再是右线索,而有右指针为止
- while (p->rtag == THREAD && p->right){
- p = p->right;
- cout << p->data << "\t";
- }
- //进入右子树
- p = p->right;
- }
- }
- //递归求二叉树深度
- template <typename elemtype>
- int ThreadTree<elemtype>::depth(){
- return depth_aux(root);
- }
- //求二叉树深度的辅助函数
- template <typename elemtype>
- int ThreadTree<elemtype>::depth_aux(NodePointer p){
- int lDep, rDep; //预存放左右子树的深度
- if (!p){
- return 0;
- }
- else{
- if (p->ltag == LINK){ //如果指针p不为空且所指向的结点有左指针
- lDep = depth_aux(p->left); //那么用左指针自递归求左子树的深度
- }
- else{ //如果指针p不为空且所指结点有左线索
- lDep = 0; //其左子树的深度为0
- }
- if (p->rtag == LINK){ //如果指针p不为空且所指向的结点有右指针
- rDep = depth_aux(p->right); //那么用右指针自递归求左子树的深度
- }
- else{ //如果指针p不为空且所指结点有右线索
- rDep = 0; //其右子树的深度为0
- }
- return (lDep > rDep ? lDep : rDep) + 1;
- }
- }
- //中序穿线二叉树的穿线操作
- template <typename elemtype>
- void ThreadTree<elemtype>::seqToThreadTree(){
- seqToThreadTree_aux(root);
- }
- //中序穿线二叉树穿线操作的辅助函数
- template <typename elemtype>
- void ThreadTree<elemtype>::seqToThreadTree_aux(NodePointer &p){
- //当前结点按中序遍历的前驱的指针,初始化为空
- static NodePointer pre = NULL;
- if (p){
- //如果当前结点不为空,那么对以其为根的子树进行中序穿线
- //用当前结点的left自递归,完成左子树的线索化
- seqToThreadTree_aux(p->left);
- if (!p->left){
- //如果当前结点的left为空,那将其作为中序的前驱线索
- p->ltag = THREAD;
- p->left = pre;
- }
- if (pre&&!pre->right){
- //如果当前结点按中序遍历的前驱的right为空,那么将其用作中序的后继线索
- pre->rtag = THREAD;
- pre->right = p;
- }
- pre = p; //更新当前结点按照中序遍历的前驱指针
- //用当前结点的right自递归,完成右子树的线索化
- seqToThreadTree_aux(p->right);
- }
- if (p == root){
- //如果当前结点等于根节点,那么完成了所有结点的中序穿线
- //最后一个结点的右标记标注为线索,且右线索设置为空
- //当前结点按照中序遍历前驱的指针置空,以便再次调用此函数做线索化
- if (pre){
- pre->rtag = THREAD;
- pre->right = NULL;
- }
- pre = NULL;
- }
- }
- //找指定结点
- template <typename elemtype>
- bool ThreadTree<elemtype>::searchNode(elemtype key, NodePointer &p){
- p = root;
- while (p){
- while (p->ltag == LINK){
- p = p->left;
- }
- //判断该结点的数据域是否等于要查找的值
- if (p->data == key){
- return true;
- }
- //如果该节点有右线索,则沿着右线索一直向上爬,知道某节点出现右指针为止
- //判断右结点上每个结点的数据域是否和key值相等
- while (p->rtag == THREAD && p->right){
- p = p->right;
- if (p->data == key){
- return true;
- }
- }
- //进入右子树
- p = p->right;
- }
- return false;
- }
- //找指定结点的前驱
- template <typename elemtype>
- bool ThreadTree<elemtype>::searchPriorNode(elemtype key, elemtype &prior){
- NodePointer p; //预指向待查节点的指针
- if (searchNode(key, p)){ //此时这里已经有p的地址了
- if (p->ltag == THREAD){
- if (!p->left){
- return false;
- }
- else{
- prior = p->left->data;
- }
- }
- else{
- p = p->left;
- while (p->rtag == LINK){
- p = p->right;
- }
- prior = p->data;
- }
- }
- return true;
- }
- //找指定结点中序的后继
- template <typename elemtype>
- bool ThreadTree<elemtype>::searchNextNode(elemtype key, elemtype& next){
- NodePointer p;
- if (searchNode(key, p)){
- if (p->rtag == THREAD){
- if (!p->right){
- return false;
- }
- else{
- next = p->right->data;
- }
- }
- else{
- p = p->right;
- while (p->ltag == LINK){
- p = p->left;
- }
- next = p->data;
- }
- }
- return true;
- }
- int main(void){
- ThreadTree<int> tt1;
- tt1.CreateThreadTree(); //创建中序穿线二叉树框架
- tt1.seqToThreadTree(); //穿线操作
- tt1.inOrderTraverse_ThreadTree();
- cout << endl;
- cout << "深度为:" << endl;
- cout << tt1.depth() << endl;
- cout << "请输入要查找的指定结点的值:";
- int key;
- cin >> key;
- ThreadTree<int>::NodePointer p = tt1.getRoot(); //获取root指针
- if (tt1.searchNode(key, p)){
- cout << "有这个结点" << endl;
- cout << "其中序前驱的值是:";
- int prior;
- tt1.searchPriorNode(key, prior);
- cout << prior << endl;
- cout << "其中序后继的值是:";
- int next;
- tt1.searchNextNode(key, next);
- cout << next << endl;
- }
- return 0;
- }
复制代码 |
|