题目描述:
采用先序法建立一棵二叉树，然后建立这棵二叉树的中序线索二叉树，线索二叉树的描述如下：
每个结点包括5个域，分别存储结点的值、标记位、结点的左右子树指针或者结点的前趋和后继（取决于标记位的值）。
如果ltag值为0，表示lchild指向结点的左...题目描述:
采用先序法建立一棵二叉树，然后建立这棵二叉树的中序线索二叉树，线索二叉树的描述如下：
每个结点包括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
{
char data;
Node *lchild;
Node *rchild;
int ltag;
int rtag;
};
class Tree
{
public:
Tree();
~Tree(){}
Node *Next(Node *p);
void Inorder();
private:
Node *root;
Node *Creat(Node *bt);
void ThrBi(Node *bt, Node *pre);
};
Tree::Tree()
{
Node *pre;
root = Creat(root);
pre = NULL;
ThrBi(root, pre);
}
Node *Tree::Creat(Node *bt)
{
char x;
cin >> x;
if(x=='#')
{
bt = NULL;
}
else
{
bt = new Node;
bt->data = x;
bt->ltag = 0;
bt->rtag = 0;
bt->lchild = Creat(bt->lchild);
bt->rchild = Creat(bt->rchild);
}
return bt;
}
void Tree::ThrBi(Node *bt, Node *pre)
{
if(bt==NULL)
{
return;
}
ThrBi(bt->lchild, pre);
if(bt->lchild==NULL)
{
bt->ltag = 1;
bt->lchild = pre;
}
if(bt->rchild==NULL)
{
bt->rtag = 1;
}
if((pre!=NULL)&&(pre->rtag==1))
{
pre->rchild = bt;
}
pre = bt;
ThrBi(bt->rchild, pre);
}
Node *Tree::Next(Node *p)
{
Node *q;
if(p->rtag==1)
{
q = p->rchild;
}
else
{
q = p->rchild;
while(q->ltag==0)
{
q = q->lchild;
}
}
return q;
}
void Tree::Inorder()
{
Node *p;
if(root==NULL)
{
return;
}
else
{
p = root;
while(p->ltag==0)
{
p = p->lchild;
}
cout ltag |
|
转播
