TElemType data;
struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/
int Depthx(BiTree T, TElemType x)
/* 求二叉树中以值为x的结点为根的子树深度 */ {
BiTree A;
DepthxH( T, x , A) ; T = A;
return DepthxF( T); }
/****40***********************
void DepthxH(BiTree &T,char x , BiTree &A){ if(T==NULL)return ; if(T->data == x) { A = T;
T = NULL; return ;}
DepthxH(T->lchild,x , A); DepthxH(T->rchild,x , A); }
void DestroyBiTree(BiTree &T) { if(T!= NULL){
DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); free(T); } }
/**********
【题目】编写递归算法：对于二叉树中每一个元素值为x 的结点，删去以它为根的子树，并释放相应的空间。 二叉链表类型定义： typedef struct BiTNode { TElemType data;
struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/
void ReleaseX(BiTree &T, char x)
/* 对于二叉树T中每一个元素值为x的结点， */ /* 删去以它为根的子树，并释放相应的空间 */ {
BiTree A,TT;
DepthxH( T, x , A); TT = A;
DestroyBiTree(TT); }
/***43*******
【题目】编写复制一棵二叉树的递归算法。 二叉链表类型定义：
typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode { TElemType data;
struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/
void CopyBiTree(BiTree T, BiTree &TT) /* 递归复制二叉树T得到TT */ {
BiTree t;
t = (BiTree)malloc(sizeof(BiTNode)); t->lchild = NULL; t->rchild = NULL; if(T ==NULL) return ; t->data = T->data ; TT = t;
CopyBiTree(T->lchild, TT->lchild); CopyBiTree(T->rchild, TT->rchild); }
/**47********
【题目】试写一非递归算法，在二叉查找树T中插入元素e。 二叉查找树的类型BSTree定义如下： typedef struct { KeyType key;
... ... // 其他数据域 } TElemType;
typedef struct BSTNode { TElemType data;
struct BSTNode *lchild,*rchild; } BSTNode, *BSTree; **********/
Status InsertBST_I(BSTree &T, TElemType k)
/* 在二叉查找树T中插入元素e的非递归算法 */ {
BSTree p,L,q = T ;
p = (BSTree)malloc(sizeof(BSTNode)); if(p == NULL) return FALSE;
p->data = k; p->lchild = NULL; p->rchild = NULL; while(q!=NULL) {
if(q->data.key == k.key) return FALSE; if(q->data.key > k.key) {
if(q->lchild!=NULL) q = q->lchild; else q->lchild = p; }
if(q->data.key < k.key) {
if(q->rchild!=NULL) q = q->rchild; else q->rchild = p; } } }
/**50********
【题目】试编写一个二叉排序树的判定算法。 二叉排序树的类型BSTree定义如下： typedef struct { KeyType key;
... ... // 其他数据域 } TElemType;
typedef struct BiTNode { TElemType data;
struct BSTNode *lchild, *rchild; }BSTNode, *BSTree; **********/
Status IsBSTree(BSTree T)
/* 判别二叉树T是否为二叉排序树。*/ /* 若是，则返回TRUE，否则FALSE */ {
if(T->lchild==NULL&&T->rchild==NULL) return TRUE; if(T->lchild->data.key < T->data.key && T->rchild->data.key > T->data.key && (T->lchild!=NULL&&T->rchild!=NULL) ) {
return IsBSTree(T->lchild)&&IsBSTree(T->rchild); }
if(T->lchild==NULL&&T->rchild!=NULL) return IsBSTree(T->rchild);
if(T->lchild!=NULL&&T->rchild==NULL) return IsBSTree(T->lchild); return FALSE; }
/***53*******
【题目】编写递归算法，从大到小输出给定二叉排序树 中所有关键字不小于x的数据元素。 二叉排序树的类型BSTree定义如下： typedef struct {
KeyType key;
... ... // 其他数据域 } TElemType;
typedef struct BSTNode { TElemType data;
struct BSTNode *lchild,*rchild; }BSTNode, *BSTree; **********/
void OrderOut(BSTree T, KeyType k, void(*visit)(TElemType)) /* 调用visit(T->data)输出 */ {
BSTree p = T; if(p!=NULL) {
if(p->rchild == NULL&&p->lchild == NULL&&p->data.key>=k) visit(p->data); if(p->rchild != NULL) {
OrderOut(p->rchild ,k , visit);
if(p->data.key >= k) visit(p->data);
}
if(p->lchild != NULL&&p->rchild != NULL) {
OrderOut(p->lchild ,k , visit); }
if(p->lchild != NULL&&p->rchild == NULL) {
if(p->data.key >= k) visit(p->data); OrderOut(p->lchild ,k , visit); } } return ; }
/***60*******
【题目】试写一非递归算法，在二叉查找树T中插入元素e。 二叉查找树的类型BSTree定义如下： typedef struct { KeyType key;
... ... // 其他数据域 } TElemType;
typedef struct BSTNode { TElemType data;
struct BSTNode *lchild,*rchild; } BSTNode, *BSTree; **********/
Status InsertBST_I(BSTree &T, TElemType k)
/* 在二叉查找树T中插入元素e的非递归算法 */ {
BSTree p,L,q = T ;
p = (BSTree)malloc(sizeof(BSTNode)); if(p == NULL) return FALSE;
p->data = k; p->lchild = NULL; p->rchild = NULL; while(q!=NULL) {
if(q->data.key == k.key) return FALSE; if(q->data.key > k.key) {
if(q->lchild!=NULL) q = q->lchild; else q->lchild = p; }
if(q->data.key < k.key) {
if(q->rchild!=NULL) q = q->rchild;