删除某结点，要删除以该结点为根的树，释放此树中的所有结点空间。
查找结点使用层序遍历的方法，注意应使用该结点的父节点作为比较，如
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; }