Question

二叉排序树与二叉平衡树的实现|二叉判定树和二叉排序树

Answer 1

实验一 二叉排序树与平衡二叉树的实现

一：题目内容

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

四：结果