设计一个读入一串整数构成一棵二叉排序树的算法
发布网友
发布时间：2022-04-30 03:24
共1个回答
热心网友
时间：2023-10-09 14:23
此定义为递归式定义。
二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：
1、若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。
2、若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。
3、根结点的左、右子树也分别为二叉排序树。
二叉排序树建立说明：
当需要插入一个节点到二叉排序树时，需要先找到它的父节点。
其实 它就是用插入的节点不断的和每一个节点比较（第一次当然是和根节点比较啦），如果小于等于则进入左边子树，再与左边子树的根节点比较，直到找到它要放的位置，否则进入右子树，进行上述操作。
下面是我写的程序，是控制台下的程序：
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef struct node
{
int element;
struct node* left;
struct node* right;
}Node,*NodePtr;
void insertNode(NodePtr *head,int data)//插入节点，注意这用了指向指针的指针，很有意思
{
if (*head==NULL)
{
*head=new Node;
(*head)->element=data;
(*head)->left=NULL;
(*head)->right=NULL;
}
else
{
if (data<=(*head)->element)
{
insertNode(&((*head)->left),data);
}
else
{
insertNode(&((*head)->right),data);
}
}
}
NodePtr creatTree()//构造二叉排序树，控制台下输入整数，0表示结束输入
{
NodePtr head=NULL;
int data;
scanf("%d",&data);
while(data!=0)
{
insertNode(&head,data);
scanf("%d",&data);
}
return head;
}
void printTree(NodePtr head)//中序遍历二叉排序树，得到有序序列
{
if(head!=NULL)
{
printTree(head->left);
printf("%d ",head->element);
printTree(head->right);
}
}
int main()
{
NodePtr head;
printf("请输入一串整数，空格隔开，0表示输入结束\n");
head=creatTree();
printf("中序遍历二叉排序树\n");
printTree(head);
printf("\n");
return 0;
}
运行结果：
不知道符合你要求没，有问题可以hi我。
