# include
# include
# define ElemType int
# define MAX_SIZE 50
typedef struct BSTreeNode{
ElemType data;
struct BSTreeNode * lchild;
struct BSTreeNode * rchild;
}Node, *pNode;
void InOrderTree(pNode root);//中序遍历二叉排序树
void LevelOrder(pNode root);//层序遍历二叉排序树
pNode CreateTreeNode(ElemType data);//创建二叉排序树的一个节点
void InsertTreeNode(pNode * proot, ElemType data);//向二叉排序树中依序插入一个节点
int TreeHeight(pNode root);//二叉排序树的高度
pNode FindTree(pNode root, ElemType data);//二叉排序树的查找
pNode FindParent(pNode root, ElemType data);//二叉排序树查找父节点
void DeleteTree(pNode * proot, ElemType data);//删除二叉排序树节点
void DestoryTree(pNode * proot);//销毁二叉排序树
int main(void)
{
pNode root = NULL;
ElemType test[] = {20, 14, 5, 15, 25, 35, 30, 17, 10, 19, 6, 4 ,40, 18, 2, 9, 1, 7};
//ElemType test[] = {3,4,2};
int len = sizeof(test)/sizeof(ElemType);
for(int i = 0; i < len; i++)
{
InsertTreeNode(&root, test[i]);
}
printf("中序遍历:");
InOrderTree(root);
printf("n");
printf("层序遍历:");
LevelOrder(root);
printf("n");
printf("Treeheight = %dn", TreeHeight(root));
printf("请输入待寻找的数字:");
ElemType x;
scanf("%d", &x);
pNode find = FindTree(root, x);
if(find)
printf("找到了%d.n", find->data);
else
printf("没找到.n");
printf("请输入待寻找父节点的数字:");
ElemType y;
scanf("%d", &y);
pNode findparent = FindParent(root, y);
if(findparent)
printf("%d的父节点值为%dn", y, findparent->data);
else
printf("没有父节点.n");
ElemType elem;
for(int i = 0; i < len; i++)
{
printf("请输入要删除的节点值:");
scanf("%d", &elem);
DeleteTree(&root, elem);
printf("删除后root = %d proot = %pn", root->data, &root);
printf("中序遍历:");
InOrderTree(root);
printf("n");
printf("层序遍历:");
LevelOrder(root);
printf("n");
}
DestoryTree(&root);
system("pause");
return 0;
}
//创建二叉排序树的一个节点
pNode CreateTreeNode(ElemType data)
{
pNode pNew = (pNode)malloc(sizeof(Node));
if(NULL == pNew)
exit(-1);
pNew->data = data;
pNew->lchild = NULL;
pNew->rchild = NULL;
return pNew;
}
//中序遍历二叉排序树
void InOrderTree(pNode root)
{
//递归
if(NULL == root)
return;
InOrderTree(root->lchild);
printf("%-4d", root->data);
InOrderTree(root->rchild);
//非递归-栈
}
//层序遍历二叉排序树
void LevelOrder(pNode root)
{
if(root != NULL)
{
pNode Queue[MAX_SIZE];//存放树节点地址的队列
int front = 0, rear = 0;
pNode pTemp = NULL;
//根指针入队
rear = (rear+1) % MAX_SIZE;
Queue[rear] = root;
while(front != rear)//当队列不为空时一直循环
{
front = (front+1) % MAX_SIZE;//出队
pTemp = Queue[front];
printf("%-4d",pTemp->data);
if(pTemp->lchild != NULL)//左节点指针若不为空则入队
{
rear = (rear+1) % MAX_SIZE;
Queue[rear] = pTemp->lchild;
}
if(pTemp->rchild != NULL)//右节点指针若不为空则入队
{
rear = (rear+1) % MAX_SIZE;
Queue[rear] = pTemp->rchild;
}
}
}
}
//向二叉排序树中依序插入一个节点
void InsertTreeNode(pNode * proot, ElemType data)
{
//递归插入
{
if(NULL == proot)
return;
if(NULL == *proot)
{
*proot = CreateTreeNode(data);
return;
}
if(data < (*proot)->data)
InsertTreeNode(&(*proot)->lchild, data);
else if(data > (*proot)->data)
InsertTreeNode(&(*proot)->rchild, data);
else
(*proot)->data = data;
}
//非递归插入
}
//二叉排序树的高度
int TreeHeight(pNode root)
{
if(NULL == root)
return 0;
int lh = TreeHeight(root->lchild);
int rh = TreeHeight(root->rchild);
if(lh > rh)
return lh + 1;
else
return rh + 1;
}
//二叉排序树的查找
pNode FindTree(pNode root, ElemType data)
{
//递归查找
if(NULL == root || data == root->data)
return root;
if(data < root->data)
return FindTree(root->lchild, data);
else
return FindTree(root->rchild, data);
//非递归查找
}
//二叉排序树查找父节点
pNode FindParent(pNode root, ElemType data)
{
if(NULL == root)
return NULL;
pNode pMove = root;
pNode parent = NULL;
while(pMove)
{
if(data == pMove->data)
{
return parent;
}
else if(data < pMove->data)
{
parent = pMove;
pMove = pMove->lchild;
}
else
{
parent = pMove;
pMove = pMove->rchild;
}
}
return NULL;
}
//删除二叉排序树节点
void DeleteTree(pNode * proot, ElemType data)
{
if(NULL == *proot)
return;
//找到待删除节点的位置pFind
pNode pFind = FindTree(*proot, data);//找到待删除节点位置
pNode parent = FindParent(*proot, data);//找到待删除节点的父节点位置
//1.删除的节点无左右子节点即叶子节点
if(NULL == pFind->lchild && NULL == pFind->rchild)
{
if(NULL == parent)//如果父节点为空，则删除节点为根节点
{
free(pFind);
pFind = NULL;
*proot = NULL;
}
else
{
if(pFind == parent->lchild)
parent->lchild = NULL;
if(pFind == parent->rchild)
parent->rchild = NULL;
free(pFind);
pFind = NULL;
}
}
//2.删除的节点只有左节点
//判断pFind和其父节点的关系后直接删除，并连接其子节点
else if(pFind->lchild != NULL && pFind->rchild == NULL)
{
if(NULL == parent)//如果父节点为空，则删除节点为根节点
{
*proot = pFind->lchild;
free(pFind);
pFind = NULL;
}
else
{
if(pFind == parent->lchild)//判断pFind是其父节点的左子节点还是右子节点好建立联系
parent->lchild = pFind->lchild;
else
parent->rchild = pFind->lchild;
free(pFind);
pFind = NULL;
}
}
//3.删除的节点只有右节点
//判断pFind和其父节点的关系后直接删除，并连接其子节点
else if(pFind->rchild != NULL && pFind->lchild == NULL)
{
if(NULL == parent)//如果父节点为空，则删除节点为根节点
{
*proot = pFind->rchild;
free(pFind);
pFind = NULL;
}
else
{
if(pFind == parent->lchild)//判断pFind是其父节点的左子节点还是右子节点好建立联系
parent->lchild = pFind->rchild;
else
parent->rchild = pFind->rchild;
free(pFind);
pFind = NULL;
}
}
//4.删除的节点左右节点都有
//不需要判断父节点为空，即删除节点为根节点为空情况，只需找pFind左子树中的最大值替换,或者右子树的最小值替换,而不是直接删除该节点
else
{
pNode pDelete = pFind->lchild;//pDelet为左子树中的最大节点
if(NULL == pDelete->rchild)//如果找到的节点pFind的左子树的根节点的右子节点为空，则其为待删除节点左子树中的最大节点
{
pFind->data = pDelete->data;
pFind->lchild = pDelete->lchild;
free(pDelete);
pDelete = NULL;
}
else//如果找到的节点pFind的左子树的根节点的右子节点不为空，则需要一直向右找到pFind的左子树中的最大节点pDelet
{
pNode pMove = pFind;//临时移动父节点指针
while(pDelete->rchild)//当pDelet的右子节点为空时则找到最大节点
{
pMove = pDelete;
pDelete = pDelete->rchild;
}
pFind->data = pDelete->data;
pMove->rchild = pDelete->lchild;
free(pDelete);
pDelete = NULL;
}
}
}
//销毁二叉排序树
void DestoryTree(pNode * proot)
{
if(NULL == proot || NULL == *proot)
return;
DestoryTree(&(*proot)->lchild);
DestoryTree(&(*proot)->rchild);
free(*proot);
*proot = NULL;
}
