编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释

编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间

编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为

根的子树，并释放相应的空间。

[解答]多种方法：（5种）

1：

Status Del-subtree(Bitree bt){

//删除bt所指二叉树，并释放相应的空间

if (bt) {

Del-subtree(bt->lchild);

Del-subtree(bt->rchild);

free(bt);

}

return OK;

}//Del-subtree

Status Search-del(Bitree bt, TelemType x){

//在bt所指的二叉树中，查找所有元素值为x的结点，并删除以它为根的子树

if (bt){

if (bt->data=x) Del-subtree(bt);

else {

Search-Del(bt->lchild, x);

Search-Del(bt->rchild, x);

}

编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间

}

return OK;

}//Search-Del

2：编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。

void Del_Sub(BiTree T)

{ if(T->lchild) Del_Sub(T->lchild);

if(T->rchild) Del_Sub(T->rchild);

free(T);

}

void

{ if(T->data==x) Del_Sub(T);

else

{if(T->lchild) Del_Sub_x(T->lchild,x);

if(T->rchild) Del_Sub_x(T->rchild,x);

}

}

编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间

3．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

[提示]：

（1）按先序查找；（2）超前查看子结点（3）按后序释放；

void DelSubTree(BiTree *bt, DataType x)

{

if ( *bt != NULL && (*bt) ->data==x )

{ FreeTree(*bt);

*bt =NULL;

}

else DelTree( *bt, x)

void DelTree(BiTree bt, DataType x)

{ if ( bt )

{ if (bt->LChild && bt->LChild->data==x)

{ FreeTree(bt->LChild);

bt->LChild=NULL;

}

if (bt->RChild && bt->RChild->data==x)

{ FreeTree(bt->RChild);

bt->RChild=NULL;

}

编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间

DelTree(bt->LChild, x);

DelTree(bt->RChild, x);

}

}

4：

//结点定义

template<class T>

class BstTree;

template<class T>

class BstNode

{

friend class BstTree<T>;

private:

int Level;

T data;

BstNode<T>* LeftPtr;

BstNode<T>* RightPtr;

public:

BstNode(const T& info=0,BstNode<T>* left=0,BstNode<T>* right=0,int lev=0)

{

data=info;LeftPtr=left;RightPtr=right;Level=lev;

}

};

//释放子树空间，注意传递一个二维指针（即searchTree函数返回的结点的地址），即指针的地址，以此来释放空间

template<class T>

void BstTree<T>::releaseHelper(BstNode<T>** root)

{

if(*(root)!=0)

{

BstNode<T>* tempt=(*root);

releaseHelper(&((*root)->LeftPtr));

releaseHelper(&((*root)->RightPtr));

cout<<tempt->data<<" ";

编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间

delete tempt;

}

}

//查找要删除的子树的根结点

template<class T>

BstNode<T>* BstTree<T>::serchTree(const T& value) {

BstNode<T>* tempt=Root;

bool found=false;

for(; ;)

{

if(found || tempt==0) break;

if(value<tempt->data)

tempt=tempt->LeftPtr;

else if(value>tempt->data)

tempt=tempt->RightPtr;

else

found=true;

}

if(found)

return tempt;//查找到要删除子树的根节点 else

return NULL;//否则返回NULL

}