树的孩子兄弟表示法

typedef struct DataType 
{

}DataType;
typedef struct Node 
{
    DataType element;
    struct Node * pFirstChild;
    struct Node * pNextSibling;
}*Tree,*Queue;

树的先序递归遍历：

void TraverseTree(Tree p)
{
    if(p==NULL) return;
    cout<<p->element<<endl;
    TraverseTree(p->pFirstChild);
    TraverseTree(p->pNextSibling);
}

上面输出结果：访问顺序 A B E C F I G H J K L D

数的先序非递归遍历：

void TraverseTree(Tree p)
{
    if(p==NULL) return;
    cout<<p->element<<endl;
    TraverseTree(p->pNextSibling);
    TraverseTree(p->pFirstChild);
}

上面输出结果：A B C D F G H J K L I E

void AddTree(Tree p,DataType parent,DataType element)
{
    Queue queue;
    BOOL flag=FALSE;
    Tree tree;
    while (p||!Empty(queue)&&!flag)
    {
        while (p)
        {
            EnQueue(queue,p);
            p=p->pNextSibling;
        }
        if (!Empty(queue))
        {
            p=Dequeue(queue);
            if (p->element==parent)
            {
                flag=TRUE;
                tree=p;
                break;
            }
        }
    }
    Tree temp1=tree->pFirstChild;
    Tree temp2=(Tree)malloc(sizeof(struct Node));
    temp2->element=element;
    temp2->pFirstChild=NULL;
    temp2->pNextSibling=temp1;
    tree->pFirstChild=temp2;
    while (!Empty(queue))
    {
        DeQueue(queue);
    }
}

//删除节点：

（1）找到父节点

（2）修改父节点及兄弟节点的指向

（3）析构该节点所对应的树

析构一棵树：

（1）层次遍历树的节点，出队的时候free，把访问变成free，同时注意free之前保存其第一个孩子

//按层次遍历
void TraverseLayer(Tree p)
{
    Queue queue;
    while (p||!empty(queue))
    {
        while (p)
        {
            EnQueue(queue,p);
            p=p->pNextSibling;
        }
        if(!empty(queue))
        {
            p=DeQueue(queue);
            cout<<p->element<<endl;
            p=p->pFirstChild;
        }
        else
        {
            return;
        }
    }
}

输出结果 A B C D E F G H  I JK L

Tree FindParent(Tree tree,DataType element)
{
    Tree p=tree;
    BOOL flag=FALSE;
    Tree parent;
    Queue queue;
    while (p||!Empty(queue)&&!flag)
    {
        while (p)
        {
            EnQueue(queue,p);
            p=p->pNextSibling;
        }
        if (!EmptyQueue(queue))
        {
            p=DeQueue(queue);
            Tree temp=p->pFirstChild;
            while (temp)
            {
                if (temp->element==element)
                {
                    parent=p;
                    flag=true;
                    break;
                }
            }
            p=p->pFirstChild;
        }
    }
    while (!empty(queue))
    {
        Dequeue(queue);
    }
    return parent;
}
int  TreeDepth(Tree p)
{
    if (p==NULL)
    {
        return 0;
    }
    p=p->pFirstChild;
    int max=0;
    while (p)
    {
        int depth=TreeDepth(p);
        if (max<depth)
        {
            max=depth;
        }
        p=p->pNextSibling;
    }
    return max+1;
}