二叉树的操作.txt

来自「数据结构是计算机学科的一门核心课程。数据结构课程的 任务是讨论现实世界中数据的」· 文本 代码 · 共 87 行

二叉链式存储结构下二叉树的操作实现
  
    
    在二叉链式存储结构下，二叉树的结点定义以及带头结点
二叉树的初始化操作、左结点插入操作、右结点插入操作、左
子树删除操作、右子树删除操作实现算法设计如下：

typedef struct Node
{
   DataType data;                 /*数据域*/
   struct Node * leftChild;       /*左子树指针*/
   struct Node * rightChild;      /*右子树指针*/
}BiTreeNode;                      /*结点的结构体定义*/

/*初始化创建二叉树的头结点*/
void Initiate(BiTreeNode * * root)
{
   *root=(BiTreeNode *)malloc(sizeof(BiTreeNode));
   (*root)->leftChild=NULL;
   (*root)->rightChild=NULL;
}

/*若当前结点curr非空，在curr的左子书插入元素值为x的新结点*/
/*原curr所指结点的左子树成为新插入结点的左子树*/
/*若插入成功返回新插入结点的指针，否则返回空指针*/
BiTreeNode * InsertLeftNode(BiTreeNode * curr,DataType x)
{
    BiTreeNode *s, *t;

    if(curr==NULL)return NULL;
 
    t=curr->leftChild;   /*保存原curr所指结点的左子树指针*/
    s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data= x;
    s->leftChild=t       /*新插入结点的左子树未原curr的左子树*/
    s->rightChild=NULL;
 
    curr->leftChild=s;       /*新结点成为curr的左子树*/
    return curr->leftChild;  /*返回新插入结点的指针*/
}


/*若当前结点curr非空，在curr的右子书插入元素值为x的新结点*/
/*原curr所指结点的右子树成为新插入结点的左子树*/
/*若插入成功返回新插入结点的指针，否则返回空指针*/
BiTreeNode * InsertRightNode(BiTreeNode * curr,DataType x)
{
    BiTreeNode *s, *t;

    if(curr==NULL)return NULL;
 
    t=curr->rightChild;   /*保存原curr所指结点的右子树指针*/
    s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
    s->data= x;
    s->rightChild=t       /*新插入结点的右子树未原curr的右子树*/
    s->leftChild=NULL;
 
    curr->rightChild=s;       /*新结点成为curr的右子树*/
    return curr->rightChild;  /*返回新插入结点的指针*/
}


/*若curr非空，删除curr所指结点的左子树*/
/*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/
BiTreeNode * DeleteLeftTree(BiTreeNode *curr)
{
    if(curr==NULL || curr->leftChild==NULL) return NULL;

    free(curr->leftChild);
    curr->leftChild=NULL;
    return curr;
}


/*若curr非空，删除curr所指结点的右子树*/
/*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/
BiTreeNode * DeleteRightTree(BiTreeNode *curr)
{
    if(curr==NULL || curr->rightChild==NULL) return NULL;

    free(curr->rightChild);
    curr->rightChild=NULL;
    return curr;
}