數據結構之樹

樹

    樹型結構是一類重要的非線性數據結構。樹是n（n>=0）個結點的有限集。在任意一顆非空樹中，有且僅有

一個特定的稱為根的結點；當n>1時，其餘結點可分為m（m>0）個互不相交的有限集T1,T2,...,Tm，其中每一個

集合本身又是一棵樹，並且稱為根的子樹。因此樹的數據結構定義為：

#define ElemType char
typedef struct BinTreeNode
{
    ElemType data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
}BinTreeNode;

typedef struct BinTree
{
    BinTreeNode *root;
}BinTree;

       在樹型結構中可以進行以下操作：

void InitBinTree(BinTree *t);
void CreateBinTree(BinTree *t);
void CreateBinTree(BinTreeNode *&t);
int Size(BinTree *t);
int Size(BinTreeNode *t);
int Height(BinTree *t);
int Height(BinTreeNode *t);
BinTreeNode* Find(BinTree *t, ElemType key);
BinTreeNode* Find(BinTreeNode *t, ElemType key);
BinTreeNode* LeftChild(BinTreeNode *t);
BinTreeNode* RightChild(BinTreeNode *t);
BinTreeNode* Parent(BinTree *t, ElemType key);
BinTreeNode* Parent(BinTreeNode *t, ElemType key);bool Equal(BinTree *t1, BinTree *t2); 
bool Equal(BinTreeNode *t1, BinTreeNode *t2);
void Copy(BinTree *t, BinTree *t1); 
void Copy(BinTreeNode *t, BinTreeNode *&t1);
void ClearBinTree(BinTree *t);
void ClearBinTree(BinTreeNode *&t);

        上面聲明的方法有：（1）初始化一個二叉樹.（2）創建出二叉樹.（3）求二叉樹的結點個數.（4）求二叉樹

的高度.（5）在一個二叉樹中，查找出key值的結點，並返回其地址.（6）在二叉樹中，求出該結點的左子樹.(7)

在二叉樹中，求出該結點的右子樹.（8）在一個二叉樹中，查找key值的結點的父結點，並返回地址.（9）比較兩

個二叉樹是否相等.（10）根據一個二叉樹去複製出另一個二叉樹.（11）清空一個二叉樹.

    將聲明的方法進行實現有：

void InitBinTree(BinTree *t)
{
    t->root = NULL;
}

void CreateBinTree(BinTree *t)
{
    CreateBinTree(t->root);
}
void CreateBinTree(BinTreeNode *&t)
{
    ElemType item;
    cin>>item;
    if(item == '#')
        t = NULL;
    else
    {
        t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        assert(t != NULL);
        t->data = item;
        CreateBinTree(t->leftChild);
        CreateBinTree(t->rightChild);
    }
}

int Size(BinTree *t)
{
    return Size(t->root);
}
int Size(BinTreeNode *t)
{
    if(t == NULL)
        return 0;
    else
        return Size(t->leftChild) + Size(t->rightChild) + 1;
}

int Height(BinTree *t)
{
    return Height(t->root);
}
int Height(BinTreeNode *t)
{
    if(t == NULL)
        return 0;
    else
    {
        int left_height = Height(t->leftChild);
        int right_height = Height(t->rightChild);
        return (left_height > right_height ? left_height : right_height) + 1;
    }
}

BinTreeNode* Find(BinTree *t, ElemType key)
{
    return Find(t->root, key);
}
BinTreeNode* Find(BinTreeNode *t, ElemType key)
{
    if(t == NULL)
        return NULL;
    if(t->data == key)
        return t;

    BinTreeNode *r = Find(t->leftChild, key);
    if(r != NULL)
        return r;
    return Find(t->rightChild, key);
}

BinTreeNode* LeftChild(BinTreeNode *t)
{
    if(t == NULL)
        return NULL;
    return t->leftChild;
}

BinTreeNode* RightChild(BinTreeNode *t)
{
    if(t == NULL)
        return NULL;
    return t->rightChild;
}

BinTreeNode* Parent(BinTree *t, ElemType key)
{
    return Parent(t->root, key);
}
BinTreeNode* Parent(BinTreeNode *t, ElemType key)
{
    if(t==NULL || t->data==key)
        return NULL;
    BinTreeNode *p = Find(t, key);
    if(p == NULL)
        return NULL;

    if(t->leftChild==p || t->rightChild==p)
        return t;
    BinTreeNode *r = Parent(t->leftChild, key);
    if(r != NULL)
        return r;
    return Parent(t->rightChild, key);
}


bool Equal(BinTree *t1, BinTree *t2)
{
    return Equal(t1->root, t2->root);
}
bool Equal(BinTreeNode *t1, BinTreeNode *t2)
{
    if(t1==NULL && t2==NULL)
        return true;
    if(t1!=NULL && t2!=NULL 
        && t1->data==t2->data 
        && Equal(t1->leftChild,t2->leftChild) 
        && Equal(t1->rightChild, t2->rightChild))
            return true;
    else
        return false;
}

void Copy(BinTree *t, BinTree *t1)
{
    Copy(t->root, t1->root);
}
void Copy(BinTreeNode *t, BinTreeNode *&t1)
{
    if(t == NULL)
        t1 = NULL;
    else
    {
        t1 = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        assert(t1 != NULL);
        t1->data = t->data;
        Copy(t->leftChild, t1->leftChild);
        Copy(t->rightChild, t1->rightChild);
    }
}

void ClearBinTree(BinTree *t)
{
    ClearBinTree(t->root);
}
void ClearBinTree(BinTreeNode *&t)
{
    if(t != NULL)
    {
        ClearBinTree(t->leftChild);
        ClearBinTree(t->rightChild);
        free(t);
        t = NULL;
    }
}