请问这个程序添加节点后为什么输出不对?
#include<iostream>using namespace std;
struct Student
{
char number[10];
char name[8];
int grade;
}; //data数据域
typedef Student EType;
struct BinaryTreeNode
{
EType data;
BinaryTreeNode *LChild;
bool Lflag;
BinaryTreeNode *RChild;
bool Rflag;
};
EType STATUS[12]={{"200701","肖象",100},{"200702","李明明",98},{"200703","刘辉",96},{"200704","陈晓曼",95},{"200705","邓昌华",92},{"200706","方伟文",85},{"200707","曾宁新",83},{"200708","罗逸",80},{"200709","谢彤彤",77},{"200710","孙冉冉",68},{"200711","田宁梦",67},{"200712","王博涵",65}};
//关于堆栈的一些结构
struct SType
{
BinaryTreeNode *p;
};
struct Stack
{
SType *element;
int top;
int Maxsize;
};
void CreateStack(Stack &S,int maxsize)
{
S.Maxsize=maxsize;
S.top=-1;
S.element=new SType[S.Maxsize];
}
bool IsEmpty(Stack &S)
{
if(S.top==-1) return true;
else return false;
}
void Push(Stack &S,SType &x)
{
S.top++;
S.element[S.top]=x;
}
void Pop(Stack &S,SType &x)
{
x=S.element[S.top];
S.top--;
}
//构造二叉树
BinaryTreeNode *MakeNode(EType &x)
{
BinaryTreeNode *p;
p=new BinaryTreeNode;
if(!p) return NULL;
p->data=x;
p->LChild=NULL;
p->Lflag=false;
p->RChild=NULL;
p->Rflag=false;
return p;
}
void MakeBinaryTree(BinaryTreeNode *root,BinaryTreeNode *left,BinaryTreeNode *right)
{
root->LChild=left;
root->RChild=right;
}
//二叉树转化为前序二叉线索树
void PreOrderThreading (BinaryTreeNode *BT)
{//二叉树转化为前序线索树算法
SType temp;
Stack S;
BinaryTreeNode *p = BT,*q=NULL; //q始终指在p结点前驱
int MaxStackSize=50;
CreateStack(S , MaxStackSize); //产生一个空栈,这一过程函数可以不在这里进行
while ( ( p || !IsEmpty(S)))
{
while (p )
{
temp.p=p;
Push (S, temp); //根结点指针进栈,以后回朔时再退栈
if (p->RChild)
p->Rflag = false;
else
p->Rflag = true;
if (p->LChild) //如果p仍有左子树继续向左推进
{
if (!p->RChild)
p->RChild=p->LChild;
p->Lflag = false;
q = p;
p = p->LChild;
}
else
{//如果p没有左子树,p的左链接域指向前驱;并准备退栈
p->Lflag = true;
p->LChild= q;
q=p;
break;
}
}
if (!IsEmpty(S))
{
Pop(S,temp);
p=temp.p;
if (!p->Rflag)
{
q->RChild=p->RChild;
p=p->RChild; //指针指向回朔结点的右子树
}
else
p=NULL; //p设为空,进行再次退栈
}
}
q-> Rflag=true; //将二叉树的最右子孙的右链接域标志设为1
q->RChild=NULL;
}
//二叉树转化为中序二叉线索树
void InOrderThreading(BinaryTreeNode *BT)
{
Stack S;
SType x;
BinaryTreeNode *p=BT,*q=NULL;
int maxsize=50;
CreateStack(S,maxsize);
while(p||(!IsEmpty(S)))
{
while(p)
{
x.p=p;
Push(S,x);
if(p->LChild)
{
p->Lflag=false;
p=p->LChild;
}
else
{
p->LChild=q;
p->Lflag=true;
q=p;
p=NULL;
}
}
if(!IsEmpty(S))
{
Pop(S,x);
p=x.p;
p->Rflag=false;
if(!q->RChild&&q!=p)
{
q->RChild=p;
q->Rflag=false;
q=p;
}
p=p->RChild;
}
}
q->Rflag=true;
}
//中序线索树中插入T节点作为S节点的左孩子
void InOrderThreadInsertLeft(BinaryTreeNode *S,BinaryTreeNode *T)
{
BinaryTreeNode *q;
T->Rflag=true;
T->RChild=S;
T->Lflag=S->Lflag;
T->LChild=S->LChild;
S->LChild=T;
S->Lflag=false;
if(!T->Lflag)
{
q=T->LChild;
while(!q->Rflag)
{
q=q->RChild;
}
q->RChild=T;
}
}
//中序线索树中插入T节点作为S节点的右孩子
void InOrderThreadInsertRight(BinaryTreeNode *S,BinaryTreeNode *T)
{
BinaryTreeNode *q;
T->Lflag=true;
T->LChild=S;
T->Rflag=S->Rflag;
T->RChild=S->RChild;
S->Rflag=false;
S->RChild=T;
if(!T->Rflag)
{
q=T->RChild;
while(!q->Lflag)
{
q=q->LChild;
}
q->LChild=T;
}
}
void PreOrderThreadTraversalOutPut(BinaryTreeNode *BT)
{//二叉线索树的遍历
BinaryTreeNode *p=BT;
cout<<endl;
cout<<" LChild Lflag 学号 姓名 成绩 Rflag RChild "<<endl;
cout<<" ------------------====================================-------------------"<<endl;
while (p)
{
if (!p ->LChild)
cout<<" NULL";
else
cout<<" "<<p ->LChild->data.number;
if (!p ->Lflag)
cout<<"<─";
else
cout<<"<--";
cout<<" "<<p ->Lflag
<< " \t"<<p->data.number
<< " "<<p->data.name
<< " "<<p->data.grade
<<" "<<p->Rflag;
if (!p ->Rflag)
cout<<" ─>";
else
cout<<" -->";
if (!p ->RChild)
cout<<"NULL";
else
cout<<" "<<p ->RChild->data.number;
cout << endl;
if (!p ->Lflag)
p = p ->LChild;
else
p = p->RChild;
}
}
int main()
{
BinaryTreeNode *p[12];
for(int i=0;i<12;i++)
{
p[i]=MakeNode(STATUS[i]);
}
MakeBinaryTree(p[0],p[1],p[2]);
MakeBinaryTree(p[1],p[3],p[4]);
MakeBinaryTree(p[2],p[5],p[6]);
MakeBinaryTree(p[3],p[7],NULL);
MakeBinaryTree(p[4],p[8],p[9]);
PreOrderThreading(p[0]);
PreOrderThreadTraversalOutPut(p[0]);
cout<<endl<<endl;
InOrderThreadInsertLeft(p[5],p[10]);
PreOrderThreadTraversalOutPut(p[0]);
cout<<endl<<endl;
InOrderThreadInsertRight(p[7],p[11]);
PreOrderThreadTraversalOutPut(p[0]);
return 0;
}