一、二叉排序树的定义
- 左子树所有结点的值均小于根结点的值
- 右子树所有结点的值均大于根节点的值
- 左子树和右子树也是二叉排序树
1.二叉排序树的结点结构
typedef struct BSTNode {
/*二叉排序树的结点结构*/
int value;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode, *BST;
2.二叉排序树示例
二、向二叉排序树插入一个结点
void insert(BST T, int v) {
/*二叉排序树上插入值为v的一个结点*/
if (T != NULL) {
if (T->value < v && T->right == NULL) {
/*当前结点是合适的插入位置*/
T->right = (BSTNode*)malloc(sizeof(BSTNode));
T->right->value = v;
T->right->left = NULL;
T->right->right = NULL;
} else if (T->value > v && T->left == NULL) {
/*当前结点是合适的插入位置*/
T->left = (BSTNode*)malloc(sizeof(BSTNode));
T->left->value = v;
T->left->left = NULL;
T->left->right = NULL;
} else if (T->value < v && T->right != NULL) {
/*当前结点不是合适的插入位置,继续在右子树上寻找插入位置*/
insert(T->right, v);
} else if (T->value > v && T->left != NULL) {
/*当前结点不是合适的插入位置,继续在右子树上寻找插入位置*/
insert(T->left, v);
}
}
}
三、运行结果
第一行输入节点数量
第二行输入每个节点的数据域
后三行输出先序、中序、后序遍历序列
四、完整C代码
点击查看代码
#include <stdio.h>
#include <stdlib.h>
typedef struct BSTNode {
/*二叉排序树的结点结构*/
int value;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode, *BST;
void insert(BST T, int v);
void visit(BSTNode* node);
void preOrder(BST T);
void inOrder(BST T);
void postOrder(BST T);
int main(int argc, char* argv[]) {
/*定义结点数量n和二叉排序树bst*/
int n;
BST bst;
/*向空二叉树T中插入n个结点*/
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int v;
scanf("%d", &v);
if (i != 0) {
insert(bst, v);
} else {
/*利用第一个输入的值v初始化bst的根结点*/
bst = (BST)malloc(sizeof(BSTNode));
bst->left = NULL;
bst->right = NULL;
bst->value = v;
}
}
/*先序遍历bst*/
printf("preOrder : ");
preOrder(bst);
printf("\n");
/*中序遍历bst*/
printf("inOrder : ");
inOrder(bst);
printf("\n");
/*后序遍历bst*/
printf("postOrder : ");
postOrder(bst);
printf("\n");
return 0;
}
void insert(BST T, int v) {
/*二叉排序树上插入值为v的一个结点*/
if (T != NULL) {
if (T->value < v && T->right == NULL) {
/*当前结点是合适的插入位置*/
T->right = (BSTNode*)malloc(sizeof(BSTNode));
T->right->value = v;
T->right->left = NULL;
T->right->right = NULL;
} else if (T->value > v && T->left == NULL) {
/*当前结点是合适的插入位置*/
T->left = (BSTNode*)malloc(sizeof(BSTNode));
T->left->value = v;
T->left->left = NULL;
T->left->right = NULL;
} else if (T->value < v && T->right != NULL) {
/*当前结点不是合适的插入位置,继续在右子树上寻找插入位置*/
insert(T->right, v);
} else if (T->value > v && T->left != NULL) {
/*当前结点不是合适的插入位置,继续在右子树上寻找插入位置*/
insert(T->left, v);
}
}
}
void preOrder(BST T) {
/*先序遍历BST*/
if (T != NULL) {
visit(T);
preOrder(T->left);
preOrder(T->right);
}
}
void inOrder(BST T) {
/*中序遍历BST*/
if (T != NULL) {
inOrder(T->left);
visit(T);
inOrder(T->right);
}
}
void postOrder(BST T) {
/*后序遍历BST*/
if (T != NULL) {
postOrder(T->left);
postOrder(T->right);
visit(T);
}
}
void visit(BSTNode* node) {
/*访问二叉排序树的某一个结点*/
printf("%d ", node->value);
}