数据结构与算法----3.3 删除二叉排序树T中所有关键字不小于X的元素

[c++]代码库

#include <iostream>
using namespace std;
typedef int KeyType;
struct ElemType{KeyType key;};
typedef struct BiTNode
{
    ElemType data;
	BiTNode *lc,*rc;
}*BiTree;
void BiTreeLists(BiTree T, void visit(ElemType));
BiTree CreatNode(ElemType x);
bool InsertBST(BiTree &T, ElemType x) ;
void visit(ElemType data);
void CreatBST(BiTree &T, int n, ElemType a[]);
void deleteXBT(BiTree &T,KeyType x);
int main()
{
	BiTree T;int n=7;
	ElemType s[]={7,3,1,5,11,9,13};
	CreatBST(T,n,s);
	cout<<"二叉树为：";BiTreeLists(T,visit);
	KeyType x=5;
	deleteXBT(T,x);
	cout<<"\n进行操作后，二叉树为：";BiTreeLists(T,visit);
	return 0;
}
BiTree CreatNode(ElemType x)
{
	BiTree p;
	p = new BiTNode; p->data = x;
	p->lc = p->rc = NULL;
	return p;
}
void BiTreeLists(BiTree T, void visit(ElemType))
{  
	if (!T) { cout << "#"; return; }
	visit(T->data);
	if (T->lc || T->rc) {
		cout << "(";
		BiTreeLists(T->lc, visit);
		cout << ",";
		BiTreeLists(T->rc, visit);
		cout << ")";
	}
}
void CreatBST(BiTree &T, int n, ElemType a[])
{
	T = NULL;
	for (int i = 0; i < n; i++) {
		InsertBST(T, a[i]);
	}
}

void visit(ElemType data)
{
	cout << data.key;
}
bool InsertBST(BiTree &T, ElemType x) 
{
	if (!T) {
		T = CreatNode(x); return true;
	}
	else if (T->data.key == x.key) {
		return false;
	}
	else if (x.key < T->data.key) {
		return InsertBST(T->lc, x);
	}
	else {
		return InsertBST(T->rc, x);
	}
}
void deleteXBT(BiTree &T,KeyType x)
{
	if (!T) return;
	deleteXBT(T->rc, x);
	if (x<=T->data.key)
	{
		BiTree p = T;
		T = T->lc; 
		delete p;
		deleteXBT(T, x);
	}
}