数据结构 线索二叉树 中序遍历 高手们帮忙看看哪错了啊。。。

你的那个线索化二叉树中的pre参数应该是全局的，想想是吗？
下面是用c++写的代码，希望对你有用：
树结点文件：
#ifndef THREADTREENODE_H
#define THREADTREENODE_H
template
class ThreadTreeNode
{
public:
T data;
int lTag;
int rTag;
ThreadTreeNode * L_child;
ThreadTreeNode * R_child;
ThreadTreeNode()
{
lTag=0;
rTag=0;
L_child=NULL;
R_child=NULL;
}
};
#endif
穿线二叉树的文件：
#ifndef THREADTREE_H
#define THREADTREE_H
#include
#include
#include
#include"ThreadTreeNode.h"
#include"node_infor.h"
using namespace std;
template
class ThreadTree
{
public:
ThreadTree();
~ThreadTree();
void InThread();
void InThread(ThreadTreeNode * root,ThreadTreeNode * & pre);
void In_order();
void InThread_test();
ThreadTreeNode * FindNext_pre(ThreadTreeNode * pointer);
ThreadTreeNode * Find_Node(const T & ele);
void Find_Test();
void Insert_Node(ThreadTreeNode * pointer,ThreadTreeNode * newpointer);
void Insert_Test();
ThreadTreeNode * FindPre_post(ThreadTreeNode * pointer);
void Pre_order();
// void Post_order();
ThreadTreeNode * FindIn_pre(ThreadTreeNode * pointer);
private:
void creat_tree();
void dele_tree(ThreadTreeNode * root);
void visit(ThreadTreeNode* pointer);
ThreadTreeNode * root;
node_infor store_infor[20];
int count;
};
template
ThreadTree::ThreadTree()
{
cout<<"前序构造二叉树！"< count=0;
ifstream in("store_infor.txt");
while(!in.eof())
{
in>>store_infor[count].data;
in>>store_infor[count].ltag;
in>>store_infor[count].rtag;
count++;
}
in.close();
creat_tree();
}
template
void ThreadTree::creat_tree()
{
ThreadTreeNode * pointer;
ThreadTreeNode * temp_pointer;
stack*> creat_help;
root=new ThreadTreeNode;
pointer=root;
for(int i=0;i {
pointer->data=store_infor[i].data;
if(store_infor[i].rtag==1)
{
creat_help.push(pointer);
}
temp_pointer=new ThreadTreeNode;
if(store_infor[i].ltag==1)
{
pointer->L_child=temp_pointer;
}
else
{
pointer=creat_help.top();
creat_help.pop();
pointer->R_child=temp_pointer;
}
pointer=temp_pointer;
}
pointer->data=store_infor[count-1].data;
}
template
void ThreadTree::visit(ThreadTreeNode* pointer)
{
cout<data<<" ";
}
template
void ThreadTree::InThread(ThreadTreeNode * root,ThreadTreeNode * & pre)
{
if(root!=NULL)
{
InThread(root->L_child,pre);
}
else
{
return;
}
if(root->L_child==NULL && pre)
{
root->lTag=1;
root->L_child=pre;
}
if(pre && pre->R_child==NULL)
{
pre->rTag=1;
pre->R_child=root;
}
pre=root;
InThread(root->R_child,pre);
}
template
void ThreadTree::InThread()
{
ThreadTreeNode * pointer=root;
ThreadTreeNode * pre_pointer=NULL;
stack*> InThread_help;
while(true)
{
while(pointer)
{
InThread_help.push(pointer);
pointer=pointer->L_child;
}
if(InThread_help.empty())
return;
pointer=InThread_help.top();
InThread_help.pop();
if(pointer->L_child==NULL && pre_pointer)
{
pointer->lTag=1;
pointer->L_child=pre_pointer;
}
if(pre_pointer && pre_pointer->R_child==NULL)
{
pre_pointer->rTag=1;
pre_pointer->R_child=pointer;
}
pre_pointer=pointer;
pointer=pointer->R_child;
}

}
template
void ThreadTree::InThread_test()
{
ThreadTreeNode * pre=NULL;
InThread(root,pre);
//InThread();
}
template
ThreadTreeNode * ThreadTree::FindNext_pre(ThreadTreeNode * pointer)
{
if(pointer->lTag==0 && pointer->L_child!=NULL)
{
return pointer->L_child;
}
while(pointer->rTag==1)
{
pointer=pointer->R_child;
}
return pointer->R_child;
}
template
ThreadTreeNode * ThreadTree::Find_Node(const T & ele)
{
ThreadTreeNode * pointer=root;
while(pointer->L_child)
{
pointer=pointer->L_child;
}
while(true)
{
if(pointer->data==ele)
{
return pointer;
}
else if(pointer->R_child==NULL)
{
return NULL;
}
else if(pointer->rTag==1)
{
pointer=pointer->R_child;
}
else
{
pointer=pointer->R_child;
while(pointer->lTag==0)
{
pointer=pointer->L_child;
}
}
}
}
template
ThreadTreeNode * ThreadTree::FindPre_post(ThreadTreeNode * pointer)
{
if(pointer->rTag==0 && pointer->R_child!=NULL)
{
return pointer->R_child;
}
else if(pointer->lTag==0)
{
return pointer->L_child;
}
else
{
pointer=pointer->L_child;
while(pointer->lTag==1)
{
pointer=pointer->L_child;
}
return pointer;
}
}
template
ThreadTreeNode * ThreadTree::FindIn_pre(ThreadTreeNode * pointer)
{
if(pointer->lTag==1)
{
return pointer->L_child;
}
if(pointer->L_child==NULL)
{
return NULL;
}
pointer=pointer->L_child;
while(pointer->rTag==0)
{
pointer=pointer->R_child;
}
return pointer;
}
template
void ThreadTree::Find_Test()
{
cout<<"查找前序的后继！"< cout<<"请输入元素："< T ele;
cin>>ele;
if(ThreadTreeNode * pointer=FindNext_pre(Find_Node(ele)))
{
visit(pointer);
cout< }
else
{
cout<<"无此相关项！"< }
cout<<"查找后序下的前继"< cout<<"请输入元素："< cin>>ele;
if(ThreadTreeNode * pointer=FindPre_post(Find_Node(ele)))
{
visit(pointer);
cout< }
else
{
cout<<"无此相关项！"< }
cout<<"查找中序下的前继！"< cout<<"请输入元素："< cin>>ele;
if(ThreadTreeNode * pointer=FindIn_pre(Find_Node(ele)))
{
visit(pointer);
cout< }
else
{
cout<<"无此相关项！"< }
}
template
void ThreadTree::Pre_order()
{
if(root==NULL)
{
return;
}
cout<<"前序周游："< ThreadTreeNode * pointer=root;
while(true)
{
while(pointer->lTag==0)
{
visit(pointer);
if(pointer->L_child==NULL)
{
break;
}
pointer=pointer->L_child;
}
if(pointer->lTag==1)
visit(pointer);
if(pointer->R_child==NULL)
{
cout< return;
}
while(pointer->rTag==1)
{
pointer=pointer->R_child;
}
pointer=pointer->R_child;
}
}
//template
/*void ThreadTree::Post_order()
{
if(root==NULL)
return;
cout<<"后序周游："< ThreadTreeNode * pointer=root;
while(true)
{
while(pointer->lTag==0)
{
if(pointer->L_child==NULL)
break;
pointer=pointer->L_child;
}
if(pointer->rTag==1 || pointer->R_child==NULL)
{
visit(pointer);
if(pointer->rTag==1)
pointer=pointer->R_child;
}
pointer
}
}*/
template
void ThreadTree::In_order()
{
if(root==NULL)
return;
cout<<"中序周游："< ThreadTreeNode * pointer=root;
while(pointer->L_child!=NULL)
{
pointer=pointer->L_child;
}
while(true)
{
visit(pointer);
if(pointer->R_child==NULL)
{
cout< return;
}
if(pointer->rTag==1)
{
pointer=pointer->R_child;
}
else
{
pointer=pointer->R_child;
while(pointer->lTag==0)
{
pointer=pointer->L_child;
}
}
}
}
template
void ThreadTree::Insert_Node(ThreadTreeNode * pointer,ThreadTreeNode * newpointer)
{
ThreadTreeNode * temp_pointer;
if(pointer->R_child==NULL)
{
temp_pointer=NULL;
}
else if(pointer->rTag==1)
{
temp_pointer=pointer->R_child;
}
else
{
temp_pointer=pointer->R_child;
while(temp_pointer->lTag==0)
{
temp_pointer=temp_pointer->L_child;
}
}
/*pointer->R_child=newpointer;
newpointer->R_child=pointer->R_child;
newpointer->lTag=1;
newpointer->L_child=pointer;
newpointer->rTag=pointer->rTag;
pointer->rTag=0;*/
if(temp_pointer!=NULL && temp_pointer->lTag==1)
{
temp_pointer->L_child=newpointer;
}
newpointer->lTag=1;
newpointer->L_child=pointer;
newpointer->R_child=pointer->R_child;
newpointer->rTag=pointer->rTag;
pointer->R_child=newpointer;
pointer->rTag=0;
}
template
void ThreadTree::Insert_Test()
{
cout<<"结点插入，位置是指定结点在中序下的后继！"< cout<<"请输入指定结点的元素："< T ele;
cin>>ele;
cout<<"请输入新结点的元素："< T new_ele;
cin>>new_ele;
ThreadTreeNode * newpointer=new ThreadTreeNode;
newpointer->data=new_ele;
Insert_Node(Find_Node(ele),newpointer);
}
template
void ThreadTree::dele_tree(ThreadTreeNode * root)
{
if(root!=NULL && root->lTag==0 && root->rTag==0)
{
dele_tree(root->L_child);
dele_tree(root->R_child);
delete root;
}
}
template
ThreadTree::~ThreadTree()
{
dele_tree(root);
}
#endif