正文
go语言实现二叉搜索树 leetcode 二叉搜索树
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
利用二叉搜索树进行数据搜索 C++语言实现
程序写好了。
算是基本能实现你的功能了吧。
VC下测试通过。
#include iostream
#include cstring
using namespace std;
class node
{
public:
node(int i):data(i),left(NULL),right(NULL){}
void inorder(node *root) //中序遍历，符合升序输出
{
if(root!=NULL)
{
inorder(root-left);
coutroot-data' ';
inorder(root-right);
}
}
void insert(node *ptr,int item) //在查找树中插入元素
{
if(ptr==NULL)
ptr=new node(item);
else if(itemptr-data)
insert(ptr-left,item);
else insert(ptr-right,item);
}
node *find(node *ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。
{
if(ptr==NULL)
return NULL;
if(ptr-data==item)
return ptr;
else if(itemptr-data)
find(ptr-left,item);
else find(ptr-right,item);
}
node *findy(node *ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用
{
if(ptr-data==item)
return ptr;
else if(itemptr-data)
findy(ptr-left,item);
else findy(ptr-right,item);
}
void printfind(node *ptr,int item) //在查找树中查找元素,并输出经过路径
{
if(ptr-data==item){
coutitemendl;
return;
}
else if(itemptr-data){
coutptr-data' 'endl;
printfind(ptr-left,item);
}
else
{
coutptr-data' 'endl;
printfind(ptr-right,item);
}
}
node* rl(){return left;}
node* rr(){return right;}
void dele(node *ptr) //删除值为item所在结点
{
if(ptr-rl()==NULLptr-rr()==NULL)
ptr=NULL;
else if(ptr-rr()==NULL)
ptr=ptr-rl();
else if(ptr-rl()==NULL)
ptr=ptr-rr();
else
{
node *temp=ptr-rl();
ptr=ptr-rr();
node *temp2=ptr;
while(temp2-rl()!=NULL)
temp2=temp2-rl();
temp2-setl(temp);
}
}
void setl(node *l){left=l;}
private:
int data;
node *left; //左孩子结点
node *right; //右孩子结点
};
int main()
{
char a[10];
int t,i=0,j;
cout"输入数字个数:";
cint;
cout"输入"t"个数字，数字之间用空格隔开:";
cinj;
node *x=new node(j);
for(;it-1;i++)
{
cinj;
x-insert(x,j);
}
cout"输入操作(当输入串为(0 0)时结束程序):"endl;
cinaj;
while(strcmp(a,"0")!=0)
{
if(strcmp(a,"S")==0)
{
if(x-find(x,j)==NULL)
cout"-1"endl;
else
x-printfind(x,j);
}
else if(strcmp(a,"D")==0)
{
node *t=x-find(x,j); //定位结点
if(t!=NULL)
{
node *y=x-findy(x,j);
x-dele(y);
}
x-inorder(x);
}
cout"\n输入操作(当输入串为0时结束程序):"endl;
cinaj;
}
return 0;
}
附测试数据一组。
5
23 55 33 5 14
S 4
S 5
D 4
D 5
D 33
D 44
0 0
经测试均正确。
相关问答
Q1: 二叉树的实现（定义，创建，遍历），求救
这是我学习二叉树时用过的例子，运行没有问题，你自己按照上面弄下吧。由于图贴不了，实在抱歉。
学生会组织机构管理问题的设计方案
1． 问题描述
学生会组织机构管理问题中的数据元素具有如下形式：
firstchild data rightbrother
firstchild: 指向第一个孩子结点
rightbrother: 指向右兄弟结点
data: 学生会成员信息，其自然情况包括：职位，姓名，性别，年级，班级。
2． 功能需求
要求完成以下功能：
(1) 插入：将某学生插入到某部门；
(2) 删除：将某学生在某个部门删除；
(3) 修改：修改某个部门的组成情况；
(4) 查询：查询学生会的组织机构状况；
(5) 输出：按部门输出学生会全体成员。
3． 实现要点
(1) 为方便对学生会组织机构的各项操作，学生会的组织机构用孩子兄弟表示法进行存储。为该存储结构设计一个模板类，设计成员函数完成上述功能。
(2) 为树的孩子兄弟表示法设计一个结点类，将结点的数据部分作为私有成员隐藏在类的内部，并提供查找右兄弟、查找第一个孩子等操作。
(3) 简单起见，学生会成员的自然情况包括职位、姓名、性别、年级、班级，为其设计一个学生类，将各自然情况作为私有成员隐藏在类的内部，并提供相应成员函数实现对数据进行访问。
(4) 在主函数中提供操作菜单，先对该组织机构进行初始化，即根据实验数据建立一棵树，再根据用户的输入完成相应功能并输出结果。
4． 类定义
为树的孩子兄弟表示法建立结点类(Node)，其类定义如下：
template class T
class Node
{
public:
Node(T* data) { _data = data; _firstChild = NULL; _brother = NULL;}//有参构造函数
~Node() {} //无参析构函数
NodeT* getFirstChild() { return _firstChild; } //访问结点第一个孩子
NodeT* getBrother() { return _brother; } //访问结点的右兄弟
T* getData() { return _data; } //取结点数据域的值
void setFirstChild(NodeT* node) { _firstChild = node; } //为结点的第一个孩子赋值
void setBrother(NodeT* node) { _brother = node; } //为结点的右兄弟赋值
void setData(T* data) { _data = data; } //为结点的数据域赋值
private:
T* _data; //结点的数据域
NodeT* _firstChild; //结点的头孩子指针
NodeT* _brother; //结点的右兄弟指针
};
在结点类中，提供了如下成员函数：
（1） 函数的声明：Node(T* data)；
完成的功能：初始化一个新结点
（2） 函数的声明：NodeT* getFirstChild()；
完成的功能：返回指向结点的第一个孩子结点的指针
（3） 函数的声明：NodeT* getBrother()；
完成的功能：返回指向结点的右兄弟结点的指针；
（4） 函数的声明：T* getData()；
完成的功能：返回结点数据域的值
（5） 函数的声明：void setFirstChild(NodeT* node)；
完成的功能：为结点的第一个孩子赋值
（6） 函数的声明：void setBrother(NodeT* node)；
完成的功能：为结点的右兄弟赋值
（7） 函数的声明：void setData(T* data)；
完成的功能：为结点的数据域赋值
为数据域的学生会成员建立成员类（Member）,其类定义如下：
class Member
{
public:
Member(string position, string name, string sex, string grade, int classes); //有参构造函数
void print(void); //打印数据
string getPosition() const { return _position; }//获取学生职务
string getName() const { return _name; } //获取学生姓名
string getSex() const { return _sex; } //获取学生性别
string getGrade() const { return _grade; }//获取学生所在年级
int getClasses() const { return _classes; }//获取学生所在班级
//操作符重载用来判断结点中数据是否相等，若相等则返回1否则返回0
int operator==(Member stu) const
{
return _name == stu.getName()
_sex == stu.getSex()
_grade == stu.getGrade()
_classes == stu.getClasses()
_position == stu.getPosition();
}
private: //学生会成员属性
string _position; //职位
string _name; //姓名
string _sex; //性别
string _grade; //年级
int _classes; //班级
};
在成员类中，提供了如下成员函数：
（1） 函数的声明：Member(string position, string name, string sex, string grade, int classes);
完成的功能：初始化一个新的数据成员
（2） 函数的声明：void print(void);
完成的功能：打印出数据成员信息
（3） 函数的声明：string getPosition() const；
完成的功能：返回学生会成员的职务
（4） 函数的功能：string getName() const；
完成的功能：返回学生会成员的姓名
（5） 函数的声明：string getSex() const；
完成的功能：返回学生会成员的性别
（6） 函数的声明：string getGrade() const；
完成的功能：返回学生会成员的年级
（7） 函数的声明：int getClasses() const；
完成的功能：返回学生会成员的班级
（8） 函数的声明：int operator==(Member stu) const；
完成的功能：比较数据域的值（即学生会成员的所有属性）是否相等，若相等返回1，否则返回0
为学生会组织机构的管理建立树类（Tree）,其类的定义如下：
template class T
class Tree
{
NodeT* _root; //指向根结点的头指针
T* _tempDate; //结点数据域中的数据
public:
Tree(T* data) {_root = new NodeT(data);} //有参构造函数，初始化一棵树//的根结点
~Tree(void) {Release(_root);} //析构函数，释放树中各结点的存储空间
void Insert(T* oldData, T* newData); //插入函数
void DeleteNode(T* date); //删除树中某结点及其孩子
void Update(T* oldData, T* newData); //修改函数
NodeT* FindNode(std::string position,Function function); //查询函数
void LeverOrder(Function function); //层序遍历树
private:
void Release(NodeT* node); //析构函数调用
NodeT* FindNode(T* data); //插入函数调用
void InsertBrother(NodeT* node,T* data); //插入兄弟结点
void InsertChild(NodeT* node, T* data); //插入第一个孩子结点
};
在树类中，提供了如下成员函数：
（1） 函数的声明：Tree(T* data)；
完成的功能：初始化一棵树
（2） 函数的声明：~Tree(void)；
完成的功能：释放树的存储空间
（3） 函数的声明：void Insert(T* oldData, T* newData);
完成的功能：将新结点插入到合适的位置
下面是演示结果：
例如将（文艺部员，刘琳，女，一，3 ）插入到（文艺部长，王一，女，一，5）的孩子结点中：
（5） 函数的声明：void DeleteNode(T* date);
完成的功能：释放要删除结点及其孩子结点的存储空间
如下将演示删除的过程：
例如：删除（秘书长，李四，女，一，4）这个结点：
（6） 函数的声明：void Update(T* oldData, T* newData);
完成的功能：修改结点的数据信息
例如要将（学习部长，刘一，女，二，4）修改为
（学习部长，周瑜，男，二，5）
（7） 函数的声明：NodeT* FindNode(std::string position,Function function);
完成的功能：查询树中的结点信息，并输出符合条件的结点的数据信息
例如查询副主席的所有成员显示如下：
（8） 函数的声明：void LeverOrder(Function function);
完成的功能：层序遍历一棵树，输出树中所有结点的数据信息
未进行任何操作前的学生会所有成员如下：
插入后显示树中的所有成员如下：
删除后显示树中的所有成员：
修改后显示如下：
Q2: 怎么建立一棵7个结点的二叉搜索树，结点的数据值是一个字符
#include stdio.h
#include stdlib.h
#include conio.h
#define maxsize 100
typedef char datatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;//*parent;
int l,r;
} bitree;
bitree *root;
bitree *pre;
bitree *Q[maxsize];
bitree *creatree()
{
char ch;
int j,flag;
int front,rear;//队头、队尾指针
bitree *root,*s;
root=NULL;//置空二叉树
front=1;rear=0;//置空队列
int temp=-1;
char Array[50];
printf("请输入数组(以'#'结束)：\n");
while(Array[temp]!='#')
{
temp++;
scanf("%c",Array[temp]);
}
int i=0;
bitree *loc,*p;
ch=Array[i];
while(temp!=0)//不是结束符时重复做
{
s=(bitree *)malloc(sizeof(bitree));
s-data=ch;
s-lchild=NULL;
s-rchild=NULL;
rear++;
Q[rear]=s;//新结点地址入队
loc=Q[front];
if(rear==1)
{
root=s;
}//输入的第一个结点为根结点
else
{
while(!loc)//扫描位置不为空时，做循环
if(s-dataloc-data)//判断当前结点值与要插入结点的值大小
{
p=loc;loc=loc-lchild;flag=0;//当前结点值要插入结点的值大小,将指针指向当前节点的左孩子
}
else
{
p=loc;loc=loc-rchild;flag=1;//当前结点值要插入结点的值大小,将指针指向当前节点的右孩子
}
for(j=1;j=rear;j++)
{
if(Q[j]==pflag==0)
Q[j]-lchild=s;//将结点插入到其左孩子
if(Q[j]==pflag==1)
Q[j]-rchild=s;//将结点插入到其右孩子
}
loc=s;
}
temp--;
ch=Array[++i];//输入下一个字符
}
return root;//返回根指针
}
void main()
{
bitree *p;
p=creatree();//创建二叉树
//getch();
}
Q3: Go语言实现二叉树遍历
图例如下:
结果应该是分别是：
广度优先: a - b - c - d - f - e - g
先序遍历: a - b - d - e - f - g - c
中序遍历: e - d - b - g - f - a - c
后序遍历: e - d - g - f - b - c - a
结果存在result里面，如果不存可以少一层变量
这个地方强烈建议读一下下面的第一个链接，我遵照着那篇文章实现的，只是用Go改写了而已。
首先定义一个数据结构，用来存储一些Node的信息。
这里是可以运行的，但是总会抛出一个数组越界的错误，我看了半天也没看出来哪里有问题，Mac版的devel我这边又有bug，没用起来。至少思路对了，我后面再看一下哪里的问题。(感谢 @RiXu 指正)
go语言实现二叉搜索树的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于leetcode 二叉搜索树、go语言实现二叉搜索树的信息别忘了在本站进行查找喔。
