2023年二叉排序树与二叉平衡树的实现-二叉判定树和二叉排序树.docx

《2023年二叉排序树与二叉平衡树的实现-二叉判定树和二叉排序树.docx》由会员分享，可在线阅读，更多相关《2023年二叉排序树与二叉平衡树的实现-二叉判定树和二叉排序树.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023年二叉排序树与二叉平衡树的实现|二叉判定树和二叉排序树 试验一 二叉排序树与平衡二叉树的实现 一：题目内容 1.问题描述 分别采纳二叉链表和依次表作存储结构，实现对二叉排序树或平衡 二叉树的操作。 2.基本要求 (1)用二叉链表作存储结构实现二叉排序树。 1)构建二叉排序树：以回车符(n)为输入结束标记，输入数列L，生成一棵二叉排序树T； 2)对二叉排序树T作中序遍历，输出结果； 3)计算二叉排序树T查找胜利的平均查找长度，输出结果； 4)删除元素：输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则，输出信息“无x”； 5）插入元素：输入元素

2、x，查找二叉排序树T，若存在含x的结点，则输出信息“x已存在”，否则插入该元素，并作中序遍历(执行操作2)； 2)用依次表(一维数组)作存储结构-静态链表 1)构建二叉排序树：以回车符(n)为输入结束标记，输入数列L，生成一棵二叉排序树T； 2)对二叉排序树T作中序遍历，输出结果； 3)计算二叉排序树T查找胜利的平均查找长度，输出结果； 4)删除元素：输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则，输出信息“无x”； 5）插入元素：输入元素x，查找二叉排序树T，若存在含x的结点，则输出信息“x已存在”，否则插入该元素，并作中序遍历(执行操作2)；

3、 (3)*用二叉链表作存储结构实平衡的二叉排序树。 1)用数列L，生成平衡的二叉排序树BT：当插入新元素之后，发觉 当前的二叉排序树BT不是平衡的二叉排序树，则马上将它转换成新的平 衡的二叉排序树BT； 2)计算平衡的二叉排序树BT的平均查找长度，输出结果。 *该功能可选做。 二：问题分析： 这是一个有关二叉树的基本操作的问题。涉及到二叉树的生成，遍历，查找，以及节点的插入和删除操作。 三：程序设计 #include stdio.h #include iostream using namespace std; int i=0; int n=0; typedef struct TreeNode

4、int key; struct TreeNode *left; struct TreeNode *right; treeNode; class BiSortTree public: BiSortTree(void); BiSortTree(); void desplayTree(void); void insertTree(int key); void deleteTree(int key); treeNode* searchTree(int key); private: treeNode* buildTree(treeNode* head,int number); treeNode* sea

5、rch(treeNode* head ,int key); treeNode* head,treeNode* p); BiSortTree:searchParent(treeNode* treeNode* BiSortTree:searchMinRight(treeNode* head); void showTree(treeNode* head); void destroyTree(treeNode* head); treeNode *Head; ; BiSortTree:BiSortTree() cout 有数(以/n作为结束标记!): Head=NULL; int number; cin

6、>>number; while(number!=-1) Head=buildTree(Head,number); n+; cin>>number; treeNode* BiSortTree:buildTree(treeNode /head 为父结点 treeNode *p; p=new treeNode; p->key=number; p->left=p->right=NULL; if(head=NULL) i+; return p; else if(p->keykey) number) *head,int i+; else return hea

7、d; head->right=buildTree(head->right,number); i+; void BiSortTree:insertTree(int key) treeNode* BiSortTree:searchTree(int key) return search(Head,key); Head=buildTree(Head,key); treeNode* BiSortTree:search(treeNode* head ,int key) void BiSortTree:deleteTree(int key) treeNode *p; if(head=NULL)

8、return NULL; if(head->key=key) return head; else if(keykey ) return search(head->left,key); else return search(head->right,key); p=NULL; p=search(Head,key); if(p=NULL) cout else treeNode* parent; parent=searchParent(Head,p); if(p->left=NULL&&p->right=NULL) else if(p->right=

9、NULL) if(parent->left=p) else parent->right=NULL; parent->left=NULL; else treeNode *rightMinSon, *secondParent; if(parent->left=p) else parent->right=p->left; parent->left=p->left ; rightMinSon=searchMinRight(p->right); secondParent=searchParent(p->right ,rightMinSon);

10、secondParent->left=rightMinSon->right; if(p->right=rightMinSon) p->right=rightMinSon->right ; treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p) if(head->left=p|head->right=p|head=p|head=NULL) return head; else treeNode* BiSortTree:searchMinRight(treeNode* head) if(p-

11、>keykey) return searchParent(head->left,p); else return searchParent(head->right,p); else return searchMinRight(head->left); return head; void BiSortTree:desplayTree(void) cout cout void BiSortTree:showTree(treeNode* Head) if(Head!=NULL) showTree(Head->left ); coutkeyright) ; BiSortTr

12、ee:BiSortTree() void BiSortTree:destroyTree(treeNode* head) if(head!=NULL) destroyTree(head->left ); destroyTree(head->right ); delete head; cout int main() BiSortTree tree; int number,set; tree.desplayTree(); cout cout if(set=2) cout>set) cin>>number; tree.deleteTree(number); cout cin>>number; tree.insertTree(number); cout 四：结果