- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构中序线索二叉树
//线索二叉树的三叉链表结点类
templateclass T
class ThreadBinaryNode
{
public:
T data;
ThreadBinaryNodeT*left,*right,*parent;
int ltag,rtag;
ThreadBinaryNode(T data,ThreadBinaryNodeT*left=NULL,ThreadBinaryNodeT*right=NULL,ThreadBinaryNodeT*parent=NULL)
{
this-data=data;
this-left=left;
this-right=right;
this-parent=parent;
this-ltag=this-rtag=0;
}
};
////ThreadBinaryNode.h
#include ThreadBinaryNode.h
template class T
class ThreadBinaryTree //中序线索二叉树类
{
public:
ThreadBinaryNodeT *root;
ThreadBinaryTree(T prelist[], int n);//以标明空子树的先根序列构造一棵中序线索二叉树
ThreadBinaryNodeT*search(T value);//查找值为value的结点,返回节点
ThreadBinaryNodeT*inpre(ThreadBinaryNodeT *p);
ThreadBinaryNodeT*insert(ThreadBinaryNodeT *p, T value, bool leftChild=true); //插入value作为p结点的孩子
ThreadBinaryNodeT*insertroot(char value,bool rootleft);
ThreadBinaryNodeT*findlast() ;
ThreadBinaryNodeT*findfirst() ;
~ThreadBinaryTree();
void inorder(); //中根次序遍历中序线索二叉
ThreadBinaryNodeT* create(T prelist[], int n, int i,ThreadBinaryNodeT*t); //以标明空子树的先根次序遍历序列创建一棵子树
void inThread(ThreadBinaryNodeT *p, ThreadBinaryNodeT *front); //中序线索化以p结点为根的子树
ThreadBinaryNodeT* search(ThreadBinaryNodeT *p, T value); //在以p为根的子树中查找首次出现的值为value的结点
ThreadBinaryNodeT* innext(ThreadBinaryNodeT *p); //返回p在中根次序下的后继结点
void destroy(ThreadBinaryNodeT *p); //撤销以p结点为根的子树
void remove(ThreadBinaryNodeT *p);//删除
};
template class T
ThreadBinaryTreeT::ThreadBinaryTree(T prelist[], int n)
{ //以标明空子树的先根序列构造一棵中序线索二叉树
int i=0;
ThreadBinaryNodeT*p=NULL;
root=create(prelist,n,i,p);
ThreadBinaryNodeT*front=NULL;
inThread(root,front); //中序线索化二叉树
}
template class T
ThreadBinaryNodeT* ThreadBinaryTreeT::create(T prelist[], int n, int i,ThreadBinaryNodeT*t)
{ //以标明空子树的先根序列创建一
文档评论(0)