如何建立多叉树
想了一下，感觉效率还是太低了
只知道结点id和结点所在树的层次，如何在内存中快速的建立一棵多叉树？
问题点数：100、回复次数：2Top
1 楼galois_godel（）回复于 2005-09-04 12:14:04 得分 0
不就对每个节点建个数组指向各个子节点嘛Top
2 楼chenzhichao2008（陈智超）回复于 2005-09-05 20:31:55 得分 0
用孩子兄弟表示法來建立
馬上寫一個例子
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
class TreeNode
{
public:
int ID;
int lavel;
TreeNode *firstChild;
TreeNode *brother;
public:
TreeNode(int ID=-1,int lavel=-1)
{
firstChild=NULL;
brother=NULL;
this->ID=ID;
this->lavel=lavel;
}
TreeNode(const TreeNode &other)
{
firstChild=NULL;
brother=NULL;
this->ID=other.ID;
this->lavel=other.lavel;
}
~TreeNode()
{
if(firstChild)
{
delete firstChild;
firstChild=NULL;
}
if(brother)
{
delete brother;
brother=NULL;
}
ID=-1;
lavel=-1;
}
TreeNode &operator=(const TreeNode &other)
{
this->ID=other.ID;
this->lavel=other.lavel;
return *this;
}
bool operator>(const TreeNode &other)
{
return this->lavel>other.lavel;
}
};
void dispData(TreeNode *treeArray,int num);
class Tree
{
public:
TreeNode *root;
public:
Tree()
{
root=NULL;
}
~Tree()
{
destroyTree(root);
root=NULL;
}
void sortByLavel(TreeNode array[],int num)
{
int minIndex;
for(int i=0;i<num;i++)
{
minIndex=i;
for(int j=i+1;j<num;j++)
{
if(array[minIndex]>array[j])
{
minIndex=j;
}
}
if(minIndex!=i)
{
TreeNode temp(array[minIndex]);
array[minIndex]=array[i];
array[i]=temp;
}
}
}
void createTree(TreeNode array[],int nodeNum)
{
int lavel=0;
TreeNode *newNode;
TreeNode *subRoot;
TreeNode *curNode;
root=new TreeNode(-1,-1);
subRoot=root;
sortByLavel(array,nodeNum);
//dispData(array,nodeNum);
int i;
for(i=0;i<nodeNum;)
{
lavel=array[i].lavel;
while(array[i].lavel==lavel&&i<nodeNum)
{
newNode=new TreeNode(array[i].ID,array[i].lavel);
if(!subRoot->firstChild)
{
subRoot->firstChild=newNode;
curNode=subRoot->firstChild;
}
else
{
curNode->brother=newNode;
curNode=newNode;
}
i++;
}
subRoot=subRoot->firstChild;
}
dispTree(root);
}
void destroyTree(TreeNode *root)
{
if(!root)
{
return ;
}
else
{
dispTree( root->firstChild );
TreeNode *tempNode=root;
for(;tempNode;)
{
root=tempNode;
tempNode=tempNode->brother;
delete root;
}
}
}
void dispTree()
{
dispTree(root);
}
void dispTree(TreeNode *root)
{
if(!root)
{
return ;
}
else
{
TreeNode *tempNode=root;
for(;tempNode;tempNode=tempNode->brother)
{
cout<<tempNode->ID<<","<<tempNode->lavel<<"\t";
}
cout<<endl;
dispTree( root->firstChild );
}
}
};
void randData(TreeNode *treeArray,int num)
{
int j=0;
srand(time(NULL));
for(int i=0;i<num;i++)
{
treeArray[i].ID=i;
if(rand()%2==1)
{
j++;
}
treeArray[i].lavel=j;
}
}
void dispData(TreeNode *treeArray,int num)
{
cout<<endl;
for(int i=0;i<num;i++)
{
cout<<"ID: "<<treeArray[i].ID;
cout<<"lavel: "<<treeArray[i].lavel<<"\t";
}
cout<<endl;
}
int main()
{
const int NODE_NUM=10;
TreeNode treeArray[NODE_NUM];
randData(treeArray,NODE_NUM);
dispData(treeArray,NODE_NUM);
Tree tree;
tree.createTree(treeArray,NODE_NUM);
system("pause");
return 0;
}Top
