二叉排序树与二叉平衡树的实现|二叉判定树和二叉排序树
实验一 二叉排序树与平衡二叉树的实现
一：题目内容
1.问题描述
分别采用二叉链表和顺序表作存储结构，实现对二叉排序树或平衡
二叉树的操作。
2.基本要求
(1)用二叉链表作存储结构实现二叉排序树。
1)构建二叉排序树：以回车符(„\n‟)为输入结束标志，输入数列L，生成一棵二叉排序树T；
2)对二叉排序树T作中序遍历，输出结果；
3)计算二叉排序树T查找成功的平均查找长度，输出结果；
4)删除元素：输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则，输出信息“无x”；
5）插入元素：输入元素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)*用二叉链表作存储结构实平衡的二叉排序树。
1)用数列L，生成平衡的二叉排序树BT：当插入新元素之后，发现
当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平
衡的二叉排序树BT；
2)计算平衡的二叉排序树BT的平均查找长度，输出结果。
*该功能可选做。
二：问题分析：
这是一个有关二叉树的基本操作的问题。涉及到二叉树的生成，遍历，查找，以及节点的插入和删除操作。
三：程序设计
#include "stdio.h"
#include "iostream"
using namespace std;
int i=0;
int n=0;
typedef struct TreeNode
{
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* search(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>>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 head; 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) 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==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);
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->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) ;
BiSortTree::~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
四：结果