数据结构之树

2018-06-27 10:06:18来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

    树型结构是一类重要的非线性数据结构。树是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;
    }
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:prufer序列笔记

下一篇:萌新的第一篇博客