大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
在计算机科学中，二叉树是一种重要的非线性的数据结构。每个结点的度均小于等于2，通常子树称为左子树和右子树。而排序二叉树是二叉树中的一种，其满足：1. 如左子树不为空，那么左子树上的结点的值都小于其根上的值；2. 如右子树不为空，那么右子树上的结点的值都大于其根上的值； 3. 其子树也是一个排序二叉树。
下面用递归的方式来插入一个结点来满足上述的要求：
typedef struct Node
{
int data;
Node *lchild;
Node *rchild;
}Node,*LNode;
void _insert1(LNode &T1,int key)
{
if(T1==NULL)
{
T1=new Node;
T1->data=key;
T1->lchild=NULL;
T1->rchild=NULL;
}
else
{
if(T1->data>key)
_insert1(T1->lchild,key);
else
_insert1(T1->rchild,key);
}
}首先定义了一个二叉树结点的结构体，然后采用递归的方式创建了满足上述排序二叉树要求的插入函数；
下面定义中序遍历函数，使得排序二叉树上的数据元素按照升序的方式输出打印：
void inOrder(LNode T1)
{
if(T1!=NULL)
{
inOrder(T1->lchild);
cout<<T1->data<<" ";
inOrder(T1->rchild);
}
}然后定义一个查找函数，以递归的方式实现，若查找的元素比根节点的元素大则在右子树中继续查找，反之在左子树中继续查找：
LNode _find(LNode T1,int key)
{
if(T1==NULL)
{
cout<<"No such element";
return NULL;
}
if(T1->data==key) return T1;
else
{
if(key>T1->data)
{
_find(T1->rchild,key);
}
else
{
_find(T1->lchild,key);
}
}
}最后定义一个计算排序二叉树的深度的函数：同样适用递归的方式实现：
int _deep(LNode T1)
{
int r=0,l=0;
if(T1==NULL) return 0;
else
{
r=_deep(T1->rchild);
l=_deep(T1->lchild);
}
if(r>l) return r+1;
else return l+1;
}测试代码如下：
void main()
{
LNode L1=NULL;
int x1=0;
while(cin>>x1)
{
_insert1(L1,x1);
}
inOrder(L1);
cout<<endl<<_deep(L1)<<endl;
LNode L2=_find(L1,3);
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/160010.html原文链接：https://javaforall.net
