删除二叉树中某结点，并释放空间

simpleset / 2023-08-21 / 原文

删除某结点，要删除以该结点为根的树，释放此树中的所有结点空间。

查找结点使用层序遍历的方法，注意应使用该结点的父节点作为比较，如

　　　　　if(p->lchild)
        {
            if(p->lchild->data==x)
            {
                DeleteTreeNodeByStack(p->lchild);
                p->lchild=NULL;
            }
            else
                EnQueue(Q,p->lchild);
        }
        if(p->rchild)
        {
            if(p->rchild->data==x)
            {
                DeleteTreeNodeByStack(T->rchild);
                p->rchild=NULL;
            }
            else
                EnQueue(Q,p->rchild);
        }

删除该结点的时候应将父节点指向该结点的指针置NULL；

删除操作分为递归和非递归。

//递归删除 
void DeleteTreeNode(Tree &T)
{
    if(T)
    {
        DeleteTreeNode(T->lchild);
        DeleteTreeNode(T->rchild);
        free(T);
    }
}

//非递归删除 
void DeleteTreeNodeByStack(Tree &T)
{
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    Push(S,p);
    while(!isEmpty(S))
    {
        Pop(S,p);
        if(p->lchild)
            Push(S,p->lchild);
        if(p->rchild)
            Push(S,p->rchild);
        free(p);    
    } 
}

完整代码：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct Node{
    int data;
    struct Node *lchild,*rchild;
}TreeNode,*Tree;

typedef struct{
    TreeNode* data[MaxSize];
    int front,rear;
}Queue;

typedef struct{
    TreeNode* data[MaxSize];
    int top;
}Stack;

void InitStack(Stack &S)
{
    S.top=-1;
}

bool isEmpty(Stack S)
{
    if(S.top==-1)
        return true;
    return false;
}

int Push(Stack &S,TreeNode *p)
{
    if(S.top==MaxSize-1)
        return -1;
    S.data[++S.top]=p;
    return 0;
}

int Pop(Stack &S,TreeNode* &p)
{
    if(S.top==-1)
        return -1;
    p=S.data[S.top--];
    return 0;
}

void InitQueue(Queue &Q)
{
    Q.front=Q.rear=0;
}

bool isEmpty(Queue Q)
{
    if(Q.rear==Q.front)
        return true;
    return false;
}

bool isFull(Queue Q)
{
    if((Q.rear+1)%MaxSize==Q.front)
        return true;
    return false;
}

bool EnQueue(Queue &Q,TreeNode* p)
{
    if(isFull(Q))
        return false;
    Q.data[Q.rear]=p;
    Q.rear=(Q.rear+1)%MaxSize;
    return true; 
}

bool DeQueue(Queue &Q,TreeNode* &p)
{
    if(isEmpty(Q))
        return false;
    p=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;
    }
    else
    {
        T=(Tree)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点:",x);
        CreateTree(T->lchild); 
        printf("输入%d的右结点:",x);
        CreateTree(T->rchild); 
    } 
}

//递归删除 
void DeleteTreeNode(Tree &T)
{
    if(T)
    {
        DeleteTreeNode(T->lchild);
        DeleteTreeNode(T->rchild);
        free(T);
    }
}

//非递归删除 
void DeleteTreeNodeByStack(Tree &T)
{
    Stack S;
    InitStack(S);
    TreeNode *p=T;
    Push(S,p);
    while(!isEmpty(S))
    {
        Pop(S,p);
        if(p->lchild)
            Push(S,p->lchild);
        if(p->rchild)
            Push(S,p->rchild);
        free(p);    
    } 
}

void Search(Tree T,int x)
{
    if(T==NULL)
        return;
    if(T->data==x)        //应该是为了减少空间的使用 
    {
        DeleteTreeNodeByStack(T);
        exit(0);
    }
    Queue Q;
    InitQueue(Q);
    TreeNode* p=T;
    EnQueue(Q,p);
    while(!isEmpty(Q))
    {
        DeQueue(Q,p);
        if(p->lchild)
        {
            if(p->lchild->data==x)
            {
                DeleteTreeNodeByStack(p->lchild);
                p->lchild=NULL;
            }
            else
                EnQueue(Q,p->lchild);
        }
        if(p->rchild)
        {
            if(p->rchild->data==x)
            {
                DeleteTreeNodeByStack(T->rchild);
                p->rchild=NULL;
            }
            else
                EnQueue(Q,p->rchild);
        }
    }
}

//层次遍历(利用队列) 
void LevelOrder(Tree T)
{
    Queue Q;
    InitQueue(Q);
    TreeNode *p=T;
    EnQueue(Q,p);
    while(!isEmpty(Q))
    {
        DeQueue(Q,p);
        printf("%d  ",p->data);
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);
    }    
} 

int main()
{
    Tree T;
    CreateTree(T);
    Search(T,3);
    LevelOrder(T);
    
    return 0;
}