如何建立中序线索二叉树,我调了很长时间了,可是不知道哪里出错了,采用先序法建立一棵二叉树,然后建立这棵二叉树的中序线索二叉树,线索二叉树的描述如下:每个结点包括5个域,分别存储

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/23 22:55:37
如何建立中序线索二叉树,我调了很长时间了,可是不知道哪里出错了,采用先序法建立一棵二叉树,然后建立这棵二叉树的中序线索二叉树,线索二叉树的描述如下:每个结点包括5个域,分别存储如何建立中序线索二叉树,

如何建立中序线索二叉树,我调了很长时间了,可是不知道哪里出错了,采用先序法建立一棵二叉树,然后建立这棵二叉树的中序线索二叉树,线索二叉树的描述如下:每个结点包括5个域,分别存储
如何建立中序线索二叉树,我调了很长时间了,可是不知道哪里出错了,
采用先序法建立一棵二叉树,然后建立这棵二叉树的中序线索二叉树,线索二叉树的描述如下:
每个结点包括5个域,分别存储结点的值、标记位、结点的左右子树指针或者结点的前趋和后继(取决于标记位的值).
如果ltag值为0,表示lchild指向结点的左孩子,如果ltag=1,表示lchild结点指向结点的前驱;如果rtag=0,表示rchild指向结点的右孩子,如果rtag=1,表示rchild指向结点的后继.
要求输入一个先序创建二叉树所需要的先序序列,按照中序方式输出该二叉树所对应的线索二叉树的每个结点,包括它的ltag,data,rtag三个域的值.二叉树的数据域类型为字符型,扩展二叉树的叶子结点用‘#’表示.--------------------------------------------------------------------------------输入样例:
A B # # C D # E # F # # G H # I K # # # #
--------------------------------------------------------------------------------
输出样例:
1 B 1
0 A 0
1 D 0
1 E 0
1 F 1
0 C 0
1 H 0
1 K 1
0 I 1
0 G 1
--------------------------------------------------------------------------------
输入描述:
输入一棵扩展二叉树的先序遍历序列,共用一行,直接输入某二叉树的加了叶子结点的扩展二叉树字符序列,以空格隔开.
--------------------------------------------------------------------------------
输出描述:
输出中序遍历的该二叉树所对应线索二叉树的每个结点,包括它的ltag,data,rtag域,输出格式为每行一个结点,数据之间以空格隔开.
我的代码:#include
using namespace std;
struct Node
{
\x05char data;
\x05Node *lchild;
\x05Node *rchild;
\x05int ltag;
\x05int rtag;
};
class Tree
{
public:
\x05Tree();
\x05~Tree(){}
\x05Node *Next(Node *p);
\x05void Inorder();
private:
\x05Node *root;
\x05Node *Creat(Node *bt);
\x05void ThrBi(Node *bt,Node *pre);
};
Tree::Tree()
{
\x05Node *pre;
\x05root = Creat(root);
\x05pre = NULL;
\x05ThrBi(root,pre);
}
Node *Tree::Creat(Node *bt)
{
\x05char x;
\x05
\x05cin >> x;
\x05if(x=='#')
\x05{
\x05\x05bt = NULL;
\x05}
\x05else
\x05{
\x05\x05bt = new Node;
\x05\x05bt->data = x;
\x05\x05bt->ltag = 0;
\x05\x05bt->rtag = 0;
\x05\x05bt->lchild = Creat(bt->lchild);
\x05\x05bt->rchild = Creat(bt->rchild);
\x05}
\x05return bt;
}
void Tree::ThrBi(Node *bt,Node *pre)
{
\x05if(bt==NULL)
\x05{
\x05\x05return;
\x05}
\x05
\x05ThrBi(bt->lchild,pre);
\x05
\x05if(bt->lchild==NULL)
\x05{
\x05\x05bt->ltag = 1;
\x05\x05bt->lchild = pre;
\x05}
\x05
\x05if(bt->rchild==NULL)
\x05{
\x05\x05bt->rtag = 1;
\x05}
\x05
\x05if((pre!=NULL)&&(pre->rtag==1))
\x05{
\x05\x05pre->rchild = bt;
\x05}
\x05
\x05pre = bt;
\x05
\x05ThrBi(bt->rchild,pre);
\x05
}
Node *Tree::Next(Node *p)
{
\x05Node *q;
\x05if(p->rtag==1)
\x05{
\x05\x05q = p->rchild;
\x05}
\x05else
\x05{
\x05\x05q = p->rchild;
\x05\x05
\x05\x05while(q->ltag==0)
\x05\x05{
\x05\x05\x05q = q->lchild;
\x05\x05}
\x05}
\x05return q;
}
void Tree::Inorder()
{
\x05Node *p;
\x05if(root==NULL)
\x05{
\x05\x05return;
\x05}
\x05else
\x05{
\x05\x05p = root;
\x05\x05while(p->ltag==0)
\x05\x05{
\x05\x05\x05p = p->lchild;
\x05\x05}
\x05\x05cout ltag

如何建立中序线索二叉树,我调了很长时间了,可是不知道哪里出错了,采用先序法建立一棵二叉树,然后建立这棵二叉树的中序线索二叉树,线索二叉树的描述如下:每个结点包括5个域,分别存储
麻烦你下个注释,ThrBi是想做什么