其实这种树实现，在并查集中使用到了，其中union操作FindEqual(),折叠算法
等都是实现在该树上的操作，所发代码为自己学习过程中编写，大家多讨论：
类的声明：
#ifndef PTREE_H
#define PTREE_H

#include<iostream.h>
#include<stdlib.h>
#include"LinkedStack.h"
#include"LinkedQueue.h"
#define defaultSize 20

////////////////////////////////////////////////
//采用父结点表示法的树的结点结构
////////////////////////////////////////////////
template<class T>
struct PTreeNode
{
    T data;                        //结点的数据域
    int parent;                    //父结点的指针
    PTreeNode(T val=-2,int par=-2) //构造函数
    {data=val;parent=par;};
};
////////////////////////////树的结点结构定义结束

////////////////////////////////////////////////
//PTree类模板用父结点表示法实现的树类
////////////////////////////////////////////////
template<class T>
class PTree
{
private:
    PTreeNode<T>* NodeList; //树的顺序存储的结点数组
    int size;               //当前树的结点的最后位置
    int current;            //当前结点的指针
    int maxSize;            //默认的最大数组空间
public:
    PTree(char* s,int n);   //构造函数,通过广义表描述字符串创建
    ~PTree()                //析构函数,释放结点数组的内存空间
    {delete [] NodeList;};  
    void Display();         //显示当前树的存储结构的内容

    int FindParent(int i)                  //找出当前结点的父结点指针
    {return NodeList[i].parent;};
    int FindFirstChild(int i);             //找出当前结点i的长子结点
    int FindNextSibling(int i);            //找出当前结点的相邻的兄弟结点
    int NearestCommonAncestor(int p,int q);//找p和q的最近公共祖先结点
};
/////////////////////////////PTree类模板声明结束

////////////////////////////////////////////////
//构造函数 通过广义表描述字符串创建树
////////////////////////////////////////////////
template<class T>
PTree<T>::PTree(char* s,int n)
{
    //计算要开辟的内存空间的个数
    maxSize=n>defaultSize?n:defaultSize;
    //为结点数组开辟内存空间,需要结点结构默认构造函数
    NodeList=new PTreeNode<T>[maxSize];
    //初始化数据成员
    current=0;
    size=-1;
    //标志
    int flag=0;
    //结点指针堆栈
    LinkedStack<int> LS;
    //用于存放栈顶的指针
    int top;

    //通过描述字符串建立一棵树
    int i=0;
    while(s[i]!='#')
    {
        switch(s[i])
        {
        case '(':
            //进入子树,把父结点的指针入栈
            LS.Push(size);
            flag=1;
            break;
        case ',':
            //表示是从栈顶获取的父结点指针
            flag=1;
            break;
        case ')':
            //退栈
            LS.Pop(top);
            flag=1;
            break;
        default:
            {
            //数组指针向后推进一格
            size++;
            //送入数据域
            NodeList[size].data=s[i];
            //如果是根结点,则父结点为-1
            if(flag==0)
                NodeList[size].parent=-1;
            //如果是分支结点,从堆栈中获取父结点指针
            else if(flag==1)
            {
                LS.getTop(top);
                NodeList[size].parent=top;
            }
            break;
            }
        }
        i++;
    }
};
//////////////////////通过广义表描述字符串创建树

////////////////////////////////////////////////
//Display()公有成员函数
////////////////////////////////////////////////
template<class T>
void PTree<T>::Display()
{
    for(int i=0;i<=size;i++)
        cout<<i<<":"<<NodeList[i].data<<" "
            <<NodeList[i].parent<<endl;
};
///////////////////////////Display()公有成员函数

////////////////////////////////////////////////
//FindFirstChild()公有成员函数
//找出当前结点i的长子结点的指针,如果没有就返回-1
////////////////////////////////////////////////
template<class T>
int PTree<T>::FindFirstChild(int i)
{
    //因为结点的顺序是前序序列,所以如果有长子结点
    //那肯定就在i结点的下个相邻结点
    //如果该结点没有子结点
    if(NodeList[i+1].parent!=i)
        return -1;
    else
        //否则下个结点就是其长子结点
        return i+1;
};
////////////////////////FindFirstChild()函数结束

////////////////////////////////////////////////
//FindNextSibling()公有成员函数
//找出当前结点i的下个兄弟结点,如果没有就返回-1
////////////////////////////////////////////////
template<class T>
int PTree<T>::FindNextSibling(int i)
{
    //寻找第一个和当前结点i有相同父结点的结点
    for(int j=i+1;j<=size;j++)
        if(NodeList[j].parent==NodeList[i].parent)
            return j;
    //没有找到
    return -1;
};
///////////////////////FindNextSibling()函数结束

////////////////////////////////////////////////
//NearestCommonAncestor()公有成员函数
//找结点p和结点q的最近公共祖先结点
////////////////////////////////////////////////
template<class T>
int PTree<T>::NearestCommonAncestor(int p,int q)
{
    //定义两个堆栈,存放p,q两个结点的所有祖先结点
    LinkedStack<int> S1,S2;
    //保证p在前
    if(p>q)
    {
        int t;t=p;p=q;q=t;
    };
    //寻找结点p和q的最近公共祖先结点
    //首先找出p的所有祖先结点
    while(p!=-1)
    {
        //p指针向上指向其父结点
        p=NodeList[p].parent;
        //把每次的父结点指针压入队列Q1
        S1.Push(p);
    }
    //再找出q的所有的祖先结点
    cout<<endl;
    while(q!=-1)
    {
        //q指指针向上指向其父结点
        q=NodeList[q].parent;
        //把每次的父结点压入队列Q2
        S2.Push(q);
    };
    //从队列Q1和Q2头部开始找最先相同的结点指针
    do
    {
        //分别从对头取两个指针
        S1.Pop(p);
        S2.Pop(q);
    }
    while(p==q && !S1.IsEmpty() && !S2.IsEmpty());
    //最后得到的是两者的最近公共祖先
    return p;
};
/////////////////NearestCommonAncestor()函数结束

#endif

你真的很厉害！！看来以后还得请多多指点呀