#include<iostream> #include<cstdlib> using namespace std; typedef int ElemType; struct Node { ElemType data; Node *left, *right; bool rTag, lTag; }; void initThread(Node* &bt) { bt=NULL; } void insertThread(Node* &bt,const ElemType& item) { Node *child=bt,*parent=NULL; while(child!=NULL) { parent=child; if(item<child->data) if(child->lTag==false) child=child->left; else child=NULL; else if(item>child->data) if(child->rTag==false) child=child->right; else child=NULL; else return; } Node* temp=new Node; temp->data=item; temp->lTag=temp->rTag=true; if(parent==NULL) { temp->left=temp->right=NULL; bt=temp; } else if(item>parent->data) { temp->right=parent->right; parent->rTag=false; parent->right=temp; temp->left=parent; } else { temp->left=parent->left; parent->lTag=false; parent->left=temp; temp->right=parent; } } void printTree(Node* bt) { if (bt != NULL) { cout << bt->data << ' '; if (bt->lTag == false || bt->rTag == false) { cout << '('; if (bt->lTag == false) printTree(bt->left); if (bt->rTag == false) { cout << ','; printTree(bt->right); } cout << ')'; } } } Node* inorderNext(Node* bt) { if (bt->rTag == true) return bt->right; else { bt = bt->right; while (bt->lTag == false) bt = bt->left; return bt; } } void inorderThread(Node* bt) { if (bt != NULL) { while (bt->lTag == false) bt = bt->left; do { cout << bt->data << ' '; bt = inorderNext(bt); } while (bt != NULL); } } void display(Node* bt) { cout << "Tree: "; printTree(bt); cout << endl; cout << "inorder thread: "; inorderThread(bt); cout << endl; } bool deleteThread(Node* &bt,const ElemType& item) { if(bt==NULL) return false; else { if(item>bt->data) if(bt->rTag==false) return deleteThread(bt->right,item); else return false; else if(item<bt->data) if(bt->lTag==false) return deleteThread(bt->left,item); else return false; else { if(bt->lTag==true&&bt->rTag==true) { Node* temp=bt; if((bt->left!=NULL)&&(bt->left->right==temp)) { bt->left->rTag=true; bt->left->right=bt->right; } else if((bt->right!=NULL)&&(bt->right->left=temp)) { bt->right->lTag=true; bt->right->left=bt->left; } else { bt=NULL; } delete temp; return true; } else if(bt->lTag==true&&bt->rTag==false) { Node* temp=bt->right; while(temp->lTag!=true) { temp=temp->left; } bt->data=temp->data; return deleteThread(bt->right,temp->data); } else if(bt->lTag=false&&bt->rTag==true) { Node *temp=bt->left; while(temp->rTag!=true) { temp=temp->right; } bt->data=temp->data; return deleteThread(bt->left,temp->data); } else { if(bt->left->rTag==true) { bt->data=bt->left->data; return deleteThread(bt->left,bt->left->data); } else { Node *parent=bt,*child=bt->left; while(child->rTag!=true) { parent=child; child=child->right; } bt->data=child->data; return deleteThread(parent->right,child->data); } } } } } void clearThread(Node* &bt) { if(bt!=NULL) { if(bt->lTag==false) clearThread(bt->left); if(bt->rTag==false) clearThread(bt->right); delete bt; bt=NULL; } } int main() { ElemType array[] = { 36, 12, 75, 83, 54, 67, 60, 40, 92, 72 }; Node* bt; initThread(bt); for (int i = 0; i < 10; i++) insertThread(bt, array[i]); display(bt); for (int i = 0; i < 10; i++) { cout << "***************** " << array[i] << " ***************" << endl; deleteThread(bt, array[i]); display(bt); } clearThread(bt); }
相关推荐
线索二叉树的一些基本功能 遍历 二叉树线索化 等等
中序线索二叉树(建立二叉树,线索化,输出二叉树)
自己做的线索二叉树,数据结构课设的时候可以参考哦!编译过的cpp文件。欢迎下载!
线索二叉树的建立 删除 插入 恢复线索
数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏
线索二叉树的先序,中序,后序遍历完整代码,在vs2013下编译通过
此程序需要完成如下要求:建立线索二叉树,并实现线索二叉树的插入、删除和恢复线索的实现。
数据结构 树与二叉树 线索二叉树 关于树与二叉树的线索二叉树小节课件
设计算法,在先序后继线索二叉树T中,查找给定结点*p在先序序列中的后继(假设二叉树T的根结点未知)。
线索二叉树的实现 C#实现 线索二叉树的实现 C#实现
线索二叉树的存储结构、线索化和遍历,其中的代码很不错
线索二叉树 算法 建立 输出等。。。 关于二叉树 包括非栈 非递归 的算法
线索二叉树的数据结构课程设计 包括需求分析,说明书,源代码
线索二叉树的数据结构课程设计 包括需求分析,说明书,源代码
09-线索二叉树.cpp
数据结构线索二叉树严蔚敏 树方面的知识很难 但只要把递归方面的机制搞懂即可
这是用c写的线索二叉树,是数据结构书上的,然后我又实现的。