删除所有与pattern匹配的子树
BinaryNode*BinaryTree::removeAll(BinaryTree& pattern)
只能删除有一个子树匹配的情况,有多个匹配子树时,无法删除所有匹配子树,无法进行删除
//删除子树
template<class T>
void BinaryTree<T>::destroy(BinaryNode<T>*p)
{
if (p != NULL)
{
destroy(p->left);
destroy(p->right);
delete p;
}
}
//查找根节点
template<class T>
BinaryNode<T>* BinaryTree<T>::searchhead(BinaryNode<T>*q, T key)
{
BinaryNode<T>*m = NULL;
if (q != NULL)
{
if (q->data == key)
{
return q;
}
if ((m = searchhead(q->left, key)) == NULL)
m = searchhead(q->right, key);
}
return m;
}
//查找子树
template<class T>
BinaryNode<T>* BinaryTree<T>::searchone(BinaryTree<T>&bintree)
{
BinaryNode<T>*p = searchhead(root, bintree.root->data);
if (p != NULL)
{
if (matchtree(p, bintree.root))
return p;
else
return NULL;
}
else
return p;
}
//匹配子树
template<class T>
bool BinaryTree<T>::matchtree(BinaryNode<T>*p, BinaryNode<T>*q)
{
if (q == NULL&&p == NULL)
return true;
if (p == NULL || q == NULL)
return false;
if (p->data != q->data)
return false;
return(matchtree(p->left, q->left) && matchtree(p->right, q->right));
}
//删除所有与pattern匹配的子树
template<class T>
BinaryNode<T>*BinaryTree<T>::removeAll(BinaryTree<T>& pattern)//BinaryNode<T>* removeAll(BinaryTree<T> & pattern)
{
BinaryNode<T>*q = searchone(pattern);
if (q != NULL)
{
if(q->left!=NULL)
{
destroy(q->left);
q->left=NULL;
}
else
{
destroy(q->right);
q->right=NULL;
}
}
else
return NULL;
}
#include "BinaryTree.h"
#include <iostream>
#include <Windows.h>
#include <string>
using namespace std;
int main(){
char lalist[]="GDBEHFCA"; //GDBGDBEGDBHFCA GDBEHFCA
char inlist[]="DGBAECHF";//GDBAGDBECGDBHF DGBAECHF
char inkey[]="DGB ";
char lakey[]="GDB";
BinaryTree<char> tree(lalist,inlist,8);
BinaryTree<char> pattern(lakey,inkey,3);
tree.preOrder() ;
cout<<endl;
cout<<"二叉关键子树"<<endl;
pattern.preOrder() ;
cout<<endl;
cout<<"删除后"<<endl;
tree.removeAll( pattern);
tree.preOrder() ;
return 0;
}
删除所有与 pattern匹配的子树