本文共 6195 字,大约阅读时间需要 20 分钟。
6-12 二叉搜索树的操作集 (30 point(s))
本题要求实现给定二叉搜索树的5种常用操作。
BinTree Insert( BinTree BST, ElementType X );BinTree Delete( BinTree BST, ElementType X );Position Find( BinTree BST, ElementType X );Position FindMin( BinTree BST );Position FindMax( BinTree BST );
其中BinTree
结构定义如下:
typedef struct TNode *Position;typedef Position BinTree;struct TNode{ ElementType Data; BinTree Left; BinTree Right;};
Insert
将X
插入二叉搜索树BST
并返回结果树的根结点指针;Delete
将X
从二叉搜索树BST
中删除,并返回结果树的根结点指针;如果X
不在树中,则打印一行Not Found
并返回原树的根结点指针;Find
在二叉搜索树BST
中找到X
,返回该结点的指针;如果找不到则返回空指针;FindMin
返回二叉搜索树BST
中最小元结点的指针;FindMax
返回二叉搜索树BST
中最大元结点的指针。#include#include typedef int ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{ ElementType Data; BinTree Left; BinTree Right;};void PreorderTraversal( BinTree BT ); /* 先序遍历,由裁判实现,细节不表 */void InorderTraversal( BinTree BT ); /* 中序遍历,由裁判实现,细节不表 */BinTree Insert( BinTree BST, ElementType X );BinTree Delete( BinTree BST, ElementType X );Position Find( BinTree BST, ElementType X );Position FindMin( BinTree BST );Position FindMax( BinTree BST );int main(){ BinTree BST, MinP, MaxP, Tmp; ElementType X; int N, i; BST = NULL; scanf("%d", &N); for ( i=0; i Data); if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data); if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data); } } scanf("%d", &N); for( i=0; i
105 8 6 2 4 1 0 10 9 756 3 10 0 555 7 0 10 3
Preorder: 5 2 1 0 4 8 6 7 10 96 is found3 is not found10 is found10 is the largest key0 is found0 is the smallest key5 is foundNot FoundInorder: 1 2 4 6 8 9
二叉搜索树是这样的数据结构:如果一个树的值比根大,则放在右儿子,比根小就放在左儿子
查找函数是很容易写的
递归形式(尾递归):
Position Find(BinTree BST, ElementType X){ if (!BST) return NULL; if (X > BST->Data) return Find(BST->Right, X); else if (X < BST->Data) return Find(BST->Right, X); else return BST;}
非递归形式:
Position Find(BinTree BST, ElementType X){ while (BST) { if (X > BST->Data) BST = BST->Right; else if (X < BST->Data) BST = BST->Left; else return BST; } return NULL;}
最大值必在最右边叶节点,最小值必在最右边叶子节点,所以可以写出找最大和最小数的函数
Position FindMin(BinTree BST){ while (BST) { if (!BST->Left) { return BST; } else { BST = BST->Left; } } return NULL;}Position FindMax(BinTree BST){ while (BST) { if (!BST->Right) { return BST; } else { BST = BST->Right; } } return NULL;}
二叉搜索树的插入总是插到叶节点的后面,用了递归的思想
BinTree Insert(BinTree BST, ElementType X){ if (!BST) { BinTree BST = (BinTree)malloc(sizeof(struct TNode)); BST->Data = X; BST->Left = NULL; BST->Right = NULL; } else { if (X < BST->Data) { BST->Left = Insert(BST->Left, X); // 递归插入左子数 } else if (X > BST->Data) { BST->Right = Insert(BST->Right, X); // 递归插入右子数 } } return BST;}
二叉搜索树的删除有三种情况
1.被删除的是叶子节点,无左右儿子,直接删除,并把根节点设为空
2.被删除的有一个儿子,让这个点的父亲指向这个点儿子就行了
3.被删除的有左右儿子,用左子数的最大值或右子数的最小值来替代该节点,因为二叉搜索树左子数值都要小于这个根,右子数的值都大于这个根,这样替代之后是没有影响的,再删除这个节点就行了
BinTree Delete(BinTree BST, ElementType X){ Position Tmp; if (!BST) { printf("Not Found\n"); } else if (X < BST->Data) { BST->Left = Delete(BST->Left, X); // 递归删除左子树 } else if (X > BST->Data) { BST->Right = Delete(BST->Right, X); // 递归删除右子树 } // 找到要删除的节点 else { // 如果被删除节点有子数,寻找下一个节点填充删除节点 if (BST->Left && BST->Right) { Tmp = FindMin(BST->Right); // 在被删除节点的右子数中找最小的元素填充删除节点 BST->Data = Tmp->Data; BST->Right = Delete(BST->Right, BST->Data); // 递归删除右子树最大值 } else { // 如果被删除结点有一个或者没有儿子 Tmp = BST; if (!BST->Left) { BST = BST->Right; // 如果这个子数没有左儿子,将右儿子的指针赋给它,Free它 } else if (!BST->Right) { BST = BST->Left; // 如果这个子数没有右儿子,将左儿子的指针赋给它,Free它 } free(Tmp); // 这两种写法已经包括了有一个子数 } } return BST;}
完整代码
#include#include typedef int ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode { ElementType Data; BinTree Left; BinTree Right;};void PreorderTraversal(BinTree BT); /* 先序遍历,由裁判实现,细节不表 */void InorderTraversal(BinTree BT); /* 中序遍历,由裁判实现,细节不表 */BinTree Insert(BinTree BST, ElementType X);BinTree Delete(BinTree BST, ElementType X);Position Find(BinTree BST, ElementType X);Position FindMin(BinTree BST);Position FindMax(BinTree BST);int main(){ BinTree BST, MinP, MaxP, Tmp; ElementType X; int N, i; BST = NULL; scanf_s("%d", &N); for (i = 0; i Data); if (Tmp == MinP) printf("%d is the smallest key\n", Tmp->Data); if (Tmp == MaxP) printf("%d is the largest key\n", Tmp->Data); } } scanf_s("%d", &N); for (i = 0; i Data = X; BST->Left = BST->Right = NULL; } else { if (X < BST->Data) { BST->Left = Insert(BST->Left, X); // 递归插入左子树 } else if (X > BST->Data) { BST->Right = Insert(BST->Right, X); // 递归插入右子树 } } return BST;}Position Find(BinTree BST, ElementType X){ while (BST) { if (X > BST->Data) { BST = BST->Right; } else if (X < BST->Data) { BST = BST->Left; } else { return BST; } } return NULL;}Position FindMin(BinTree BST){ while (BST) { if (!BST->Left) { return BST; } else { BST = BST->Left; } } return NULL;}Position FindMax(BinTree BST){ while (BST) { if (!BST->Right) { return BST; } else { BST = BST->Right; } } return NULL;}BinTree Delete(BinTree BST, ElementType X){ Position Tmp; if (!BST) { printf("Not Found\n"); } else if (X < BST->Data) { BST->Left = Delete(BST->Left, X); // 递归删除左子树 } else if (X > BST->Data) { BST->Right = Delete(BST->Right, X); // 递归删除右子树 } // 找到要删除的节点 else { // 如果被删除节点有子数,寻找下一个节点填充删除节点 if (BST->Left && BST->Right) { Tmp = FindMin(BST->Right); // 在被删除节点的右子数中找最小的元素填充删除节点 BST->Data = Tmp->Data; BST->Right = Delete(BST->Right, BST->Data); // 递归删除右子树最大值 } else { // 如果被删除结点有一个或者没有儿子 Tmp = BST; if (!BST->Left) { BST = BST->Right; // 如果这个子数没有左儿子,将右儿子的指针赋给它,Free它 } else if (!BST->Right) { BST = BST->Left; // 如果这个子数没有右儿子,将左儿子的指针赋给它,Free它 } free(Tmp); // 这两种写法已经包括了有一个子数 } } return BST;}void PreorderTraversal(BinTree BT){ if (!BT) return; printf(" %d", BT->Data); PreorderTraversal(BT->Left); PreorderTraversal(BT->Right);}void InorderTraversal(BinTree BT){ if (!BT) return; InorderTraversal(BT->Left); printf(" %d", BT->Data); InorderTraversal(BT->Right);}
转载地址:http://gxhv.baihongyu.com/