求 构建树的代码优化
我要构建一棵树，大约有100+的分组，总够有7000个模型。遍历模型构建树时效率特别慢，求一个优化算法。源代码大意：
for(i=0;i<组数;i++)
{
//获取组内物体个数
for(j=0;j<组内物体个数；j++)
{
//增加树节点
}
}
怎么优化能提高效率？？？
1、二叉树
template<class T>
struct TreeNode
{
T data;
TreeNode<T> *left, *right;
};
template<class T>
class BinaryTree
{
public:
BinaryTree(){ root = NULL; }
BinaryTree(const TreeNode<T>& tree);
~BinaryTree(){ destroy(root); }
bool IsEmpty() const { return root==NULL; }
void PreOrder(){ PreOrder(root); }
void InOrder(){ InOrder(root); }
void PostOrder(){ PostOrder(root); }
void LevelOrder();
int Height() { return Height(root); } //二叉树高度
int Leaf() { return Leaf(root); } //叶子结点数
int Size() { return Size(root); } //结点数
void Create(T x) { Create(root, x); } //建立二叉树
BinaryTree<T>& operator=(const BinaryTree<T>&);
private:
TreeNode<T> *root;
void PreOrder(TreeNode<T> *t);
void InOrder(TreeNode<T> *t);
void PostOrder(TreeNode<T> *t);
void destroy(TreeNode<T> *t);
int Height(TreeNode<T> *t);
int Leaf(TreeNode<T> *t);
int Size(TreeNode<T> *t);
void Create(TreeNode<T>* &t, T x);
void copyTree(TreeNode<T>* &t, TreeNode<T>* t1);
};
template <class T>
BinaryTree<T>::BinaryTree(const TreeNode<T>& tree)
{
if(tree.root == NULL)
root = NULL;
else
copyTree(root, tree.root);
}
template<class T>
void BinaryTree<T>::PreOrder(TreeNode<T> *t)
{
if(t)
{
cout<<t->data<<" ";
PreOrder(t->left);
PreOrder(t->right);
}
}
template<class T>
void BinaryTree<T>::InOrder(TreeNode<T> *t)
{
if(t)
{
InOrder(t->left);
cout<<t->data<<" ";
InOrder(t->right);
}
}
template<class T>
void BinaryTree<T>::PostOrder(TreeNode<T> *t)
{
if(t)
{
PostOrder(t->left);
PostOrder(t->right);
cout<<t->data<<" ";
}
}
template<class T>
void BinaryTree<T>::destroy(TreeNode<T> *t)
{
if(t)
{
destroy(t->left);
destroy(t->right);
delete t;
}
}
template<class T>
int BinaryTree<T>::Height(TreeNode<T> *t)
{
if(t==NULL) return 0;
int l = Height(t->left);
int r = Height(t->right);
return l>r ? l+1 : r+1;
}
template<class T>
int BinaryTree<T>::Leaf(TreeNode<T> *t)
{
if(t==NULL) return 0;
if(t->left==NULL && t->right==NULL) return 1;
return Leaf(t->left) + Leaf(t->right);
}
template<class T>
int BinaryTree<T>::Size(TreeNode<T> *t)
{
if(t==NULL) return 0;
else return Size(t->left) + Size(t->right) +1;
}
template<class T>
void BinaryTree<T>::Create(TreeNode<T>* &t, T x)
{ // 以先序序列输入各结点的数据，某结点的左子树或右子树为空时输入一个特定的值x。
T d;
cin >> d;
if (d == x) t=NULL;
else
{ t = new TreeNode<T> ;
t->data = d;
Create(t->left, x);
Create(t->right, x);
}
}
template<class T>
void BinaryTree<T>::LevelOrder()
{
Queue<TreeNode<T>*> q;
TreeNode<T> *p;
if(root==NULL) return;
q.Add(root);
while(!q.IsEmpty())
{
q.Delete(p);
cout << p->data;
if(p->left) q.Add(p->left);
if(p->right) q.Add(p->right);
}
}
前序、中序、后序的非递归算法
template<class T>
void BinaryTree<T>::PreOrder()
{
if(root==NULL) return;
SeqStack<TreeNode<T>*> stack;
TreeNode<T> *p = root;
while(p || !stack.IsEmpty())
{
while(p)
{ cout << p->data << " ";
stack.Push(p);
p = p->left;
}
stack.Pop(p);
p = p->right;
}
}
//上面while循环也可写为如下形式：
/*
while(p || !stack.IsEmpty())
if(p)
{ cout << p->data << " ";
stack.Push(p);
p = p->left;
}
else
{ stack.Pop(p);
p = p->right;
}
} //*/
template<class T>
void BinaryTree<T>::InOrder()
{
if(root==NULL) return;
SeqStack<TreeNode<T>*> stack;
TreeNode<T> *p = root;
while(p || !stack.IsEmpty())
{
while(p)
{ stack.Push(p);
p = p->left;
}
stack.Pop(p);
cout << p->data << " ";
p = p->right;
}
}
template<class T>
void BinaryTree<T>::PostOrder()
{
if(root==NULL) return;
SeqStack<TreeNode<T>*> s1;
SeqStack<int> s2;
int f;
TreeNode<T> *p = root;
while(p || !s1.IsEmpty())
{
while(p)
{ s1.Push(p);
s2.Push(1);
p = p->left;
}
s1.Pop(p);
s2.Pop(f);
if(f==1)
{ s1.Push(p);
s2.Push(2);
p = p->right;
}
else
{ cout << p->data << " ";
p = NULL;
}
}
}
template <class T>
void BinaryTree<T>::copyTree(TreeNode<T>* &t, TreeNode<T>* t1)
{
if(t1 == NULL)
t = NULL;
else
{
t = new TreeNode<T>;
t->data = t1->data;
copyTree(t->left, t1->left);
copyTree(t->right, t1->right);
}
}
template<class T>
BinaryTree<T>& BinaryTree<T>::operator=(const BinaryTree<T>& tree)
{
if(this != &tree)
{
if(root != NULL) destroy(root);
if(tree.root == NULL)
root = NULL;
else
copyTree(root, tree.root);
}
return *this;
}
2、堆
template<class T>class MaxHeap
{ private:
T *heap;
int MaxSize;
int size;
void FilterUp(int i);
void FilterDown(int i);
public:
MaxHeap(int heapSize = 10);
MaxHeap(T arr[],int n);
~MaxHeap(){ delete[]heap; }
void Insert(const T &item);
T Delete();
T GetHeapTop()const{ return heap[0];}
int HeapSize()const{ return size;}
int HeapEmpty()const{ return size==0;}
int HeapFull()const{ return MaxSize==size;}
};
template<class T>
MaxHeap<T>::MaxHeap(int heapSize)
{ if(heapSize<=0)
{ cerr<<"参数错误"<<endl; exit(1); }
MaxSize = heapSize;
heap=new T[MaxSize];
size=0;
}
template<class T>
void MaxHeap<T>::FilterUp(int i)
{ int current = i, parent = (i-1)/2;
T target=heap[i];
while(currentPos!=0 && target>heap[parentPos])
{
heap[current] = heap[parent];
current = parent;
parent = (current-1)/2;
}
heap[current] = target;
}
template <class T>
void MaxHeap<T>::Insert(const T &x)
{ if(size==MaxSize)
{ cerr<<"堆已满!"<<endl; exit(1); }
heap[size] = x;
FilterUp(size);
size++;
}
template<class T>
void MaxHeap<T>::FilterDown(int i)
{ int current= i, child = 2*i+1;
T target = heap[i];
while( child < size )
{ if( (child+1<size) && (heap[child+1] > heap[child]) ) child++;
if( target>=heap[child] ) break;
else
{ heap[current] = heap[child];
current = child;
child = 2*current + 1;
}
}
heap[current] = target;
}
template<class T>
T MaxHeap<T>::Delete()
{ if(size==0)
{ cerr<<"堆空!"<<endl; exit(1); }
T temp = heap[0];
heap[0] = heap[size-1];
size--;
FilterDown(0);
return temp;
}
template<class T>
MaxHeap<T>::MaxHeap(T arr[],int n)
{
MaxSize = n;
size = n;
heap = arr;
int current = (n-2)/2;
while(current >= 0)
{ FilterDown(current);
current--;
}
}
