大家好，又见面了，我是你们的朋友全栈君。
在计算机科学中，二叉树是一种重要的非线性的数据结构。每个结点的度均小于等于2，通常子树称为左子树和右子树。而排序二叉树是二叉树中的一种，其满足：1. 如左子树不为空，那么左子树上的结点的值都小于其根上的值；2. 如右子树不为空，那么右子树上的结点的值都大于其根上的值； 3. 其子树也是一个排序二叉树。
下面用递归的方式来插入一个结点来满足上述的要求：
代码语言：javascript复制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);
}
}首先定义了一个二叉树结点的结构体，然后采用递归的方式创建了满足上述排序二叉树要求的插入函数；
下面定义中序遍历函数，使得排序二叉树上的数据元素按照升序的方式输出打印：
代码语言：javascript复制void inOrder(LNode T1)
{
if(T1!=NULL)
{
inOrder(T1->lchild);
cout<<T1->data<<" ";
inOrder(T1->rchild);
}
}然后定义一个查找函数，以递归的方式实现，若查找的元素比根节点的元素大则在右子树中继续查找，反之在左子树中继续查找：
代码语言：javascript复制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);
}
}
}最后定义一个计算排序二叉树的深度的函数：同样适用递归的方式实现：
代码语言：javascript复制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;
}测试代码如下：
代码语言：javascript复制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.cn/160010.html原文链接：https://javaforall.cn
