数据结构实验之线索化二叉树

数据结构实验之线索化二叉树

//线索二叉树 (1)先确定是用先序线索化
// (2)确定顺序
// (3)按顺序依次线索化每一个指针

//可一次就线索化，提高效率 1 必须有指针指向前趋
//
// 先序线索化遍历， 中序线索化遍历，后序线索化遍历.



#include "malloc.h"
#include "iostream.h"
#define null 0

typedef struct LinkNode
{
int child;
struct LinkNode *next;
}LNode;

typedef struct TreeNode
{
char data;
int parent;
LNode *firstchild;
}TNode;

typedef struct SequenceList
{
TNode *elem;
int length;
int listsize;
}STree;

void initSTree(STree &Tree)
{
Tree.elem=(TNode *)malloc(100*sizeof(TNode));
Tree.length=0;
Tree.listsize=100;
}
int create(STree &Tree)
{
int i;
int x,y;
LNode *p,*q;
cout<<"please input node numbers of the tree.\n";
cin>>Tree.length;
cout<<"please each node of the tree.\n";
for(i=0;i<Tree.length;i++)
{
cin>>Tree.elem[i].data;
Tree.elem[i].parent=-1;
Tree.elem[i].firstchild=null;
}
cout<<"please each edge of the tree .\n";
for(i=0;i<Tree.length-1;i++)
{
cin>>x>>y;
Tree.elem[y].parent=x;
p=(LNode *)malloc(sizeof(LNode));
p->child=y;
q=Tree.elem[x].firstchild;
if(q==null)
{
p->next=Tree.elem[x].firstchild;
Tree.elem[x].firstchild=p;
}
else
{
while(q->next!=null)
{
q=q->next;
}
p->next=q->next;
q->next=p;
}
}
return Tree.length;
}
void preorder(STree Tree,int x)
{
LNode *p;
p=Tree.elem[x].firstchild;
if(p!=null)
{
cout<<Tree.elem[x].data;
while(p!=null)
{
preorder(Tree,p->child);
p=p->next;
}
}
else
{
cout<<Tree.elem[x].data;
}

}
void main()
{ int i;
S
Tree T;
initSTree(T);
i=create(T);
cout<<i;
cout<<("线索化二叉树的节点内容 \n");
preorder(T,0);
}