#include <stdio.h>
#include <stdlib.h>
#define N 10 //插入查找树数组长度
/* 二叉查找树 操作*/
typedef int Elemtype;
typedef struct BSTNode
{
Elemtype data;// 数据
struct BSTNode *lchild,*rchild;// 左右孩子结点
}BSTNode,*PNode;
PNode pn[200];// 储存叶子结点
int nn = 0;// 储存叶子结点的数量
//查找结点,树中存在结点值为data的结点返回1，否则返回0
int SearchBST(PNode T,Elemtype data)
{
if(T == NULL)
return 0;
if(data < T->data)
return SearchBST(T->lchild,data);
else if(data > T->data)
return SearchBST(T->rchild,data);
else
return 1;
}
//向树中插入节点，若此节点在不在树中则插入，已在树中则不插入
PNode insertBST(Elemtype data,PNode root)
{
if(root == NULL)
{
root = (PNode)malloc(sizeof(BSTNode));
root->data = data;
root->lchild = NULL;
root->rchild = NULL;
printf("%d插入树中\n",data);
return root;
}
if(data < root->data)
root->lchild = insertBST(data,root->lchild);
else if(data > root->data)
root->rchild = insertBST(data,root->rchild);
else
printf("%d已在树中，不能再次插入!!!\n",data);
return root;
}
//查找二叉查找树中最大、最小节点值;从根节点开始查找左儿子，
//只要存在左儿子就一直查找，终点就是最小的元素，最大的为右儿子查找终点
PNode findMin(PNode root)
{
if(root == NULL)
return NULL;
else if(root->lchild == NULL)
return root;
return findMin(root->lchild); //递归查找
}
PNode findMax(PNode root)
{
if(root != NULL) //非递归查找
while(root->rchild != NULL)
root = root->rchild;
return root;
}
void creaList(PNode root){// 用递归的方式遍历叶子结点储存到全局变量pnn中
if(!root){
return;
}
if(root->lchild == NULL && root->rchild == NULL){
pn[nn] = root;
nn++;
}
creaList(root->lchild);
creaList(root->rchild);
}
//删除一个结点：如果是叶结点则直接删除；如果结点有一个孩子，
//则直接用该结点父节点连接此结点孩子结点，删除此节点；如果结点有两个孩子结点
//则用其右子树的最小数据代替该结点的数据并递归的删除那个最小结点，因为右子树的
//最小结点不可能有左儿子因此第二次删除比较容易
PNode deleteBST(PNode root,Elemtype data)
{
if(root == NULL)
return root;
if(data < root->data)
root->lchild = deleteBST(root->lchild,data);
else if(data > root->data)
root->rchild = deleteBST(root->rchild,data);
else if(root->lchild != NULL && root->rchild != NULL)
{
root->data = findMin(root->rchild)->data;
root->rchild = deleteBST(root->rchild,root->data);
}
else
root = (root->lchild != NULL) ? root->lchild : root->rchild;
return root;
}
//中序输出:中序遍历二叉查找树可以得到原关键字有序序列
void print(PNode root)
{
if(root!=NULL)
{
print(root->lchild);
printf("%d ",root->data);
print(root->rchild);
}
}
void Exchange(PNode bt)
{
if(bt->lchild==NULL&&bt->rchild==NULL)
;
else //三种情况，1.都不为空，2.左为空，3.右为空；
{
//交换左右子树；
PNode temp=bt->lchild;
bt->lchild=bt->rchild;
bt->rchild=temp;
}
//如果交换后的这个结点左子树不为空，则继续向下寻找可以交换的结点；
if(bt->lchild)
Exchange(bt->lchild);
if(bt->rchild)
Exchange(bt->rchild);
}
int main(int argc, char *argv[]) {
Elemtype data[10];
int i;
int n;
printf("请输入10个数:\n");
for(i = 0;i < 10;i++){
scanf("%d",&data[i]);
}
PNode root = NULL;//二叉查找树根节点
PNode temp;
for(i=0;i<N;i++) //创建二叉查找树
{
root = insertBST(data[i],root);
}
printf("\n\n-------构成的树------");
print(root);
printf("\n");
printf("交换后的树:\n");
// 调用交换函数
Exchange(root);
print(root);
printf("\n");
printf("--------增加、删除操作--------\n");
printf("请输入要添加的数:");
scanf("%d",&n);
// 调用插入函数
root = insertBST(n,root);
print(root);
printf("\n");
printf("请输入要删除的数:");
scanf("%d",&n);
//调用删除函数
root = deleteBST(root,n);
print(root);
printf("\n");
creaList(root);
PNode L = (PNode)malloc(sizeof(BSTNode));
temp = L;
for(i = 0;i < nn;i++){
temp->lchild = pn[i];
temp = temp->lchild;
}
printf("叶子结点链表\n");
while(L->lchild){
printf("%d ",L->lchild->data);
L = L->lchild;
}
printf("\n");
system("pause");
}
- 1
- 2
- 3
前往页