当前位置:首页(Home) >> 新闻资源(News List)

时间:2014-12-03 来源:

创建二叉查找树的完整C代码 【编程语言】

BST 基本概念

二叉查找树(Binary Search Tree),又称二叉排序树(Binary Sort Tree)。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; 简单的说就是:左孩子<双亲结点<右孩子。 因此,对查找二叉树进行中序遍历,得到的是一个从小到大排序的数列。 创建BST的完整C代码

经过调试,可以确认得到的二叉树为下图:

/* 创建BST的C代码实现 */ #include <stdio.h> #include <stdlib.h> typedef int Elemtype; typedef struct BiTNode{ Elemtype data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; //在给定的BST中插入结点,其数据域为element int BSTInsert( BiTree *t, Elemtype element ) { if( NULL == *t ) { (*t) = (BiTree)malloc(sizeof(BiTNode)); (*t)->data = element; (*t)->lchild = (*t)->rchild = NULL; return 1; } if( element == (*t)->data ) return 0; if( element < (*t)->data ) return BSTInsert( &(*t)->lchild, element ); return BSTInsert( &(*t)->rchild, element ); } //创建BST void CreateBST( BiTree *t, Elemtype *a, int n ) { (*t) = NULL; for( int i=0; i<n; i++ ) BSTInsert( t, a[i] ); } //中序遍历打印BST void PrintBST( BiTree t ) { if( t ) { PrintBST( t->lchild ); printf("%d ", t->data); PrintBST( t->rchild ); } } int main() { int n; int *a; BiTree t; printf("请输入二叉查找树的结点数:\n"); scanf("%d", &n); a = (int *)malloc(sizeof(int)*n); printf("请输入而查找树的结点:\n"); for( int i=0; i<n; i++ ) scanf("%d", &a[i]); CreateBST( &t, a, n ); printf("该BST的中序遍历结果为:\n"); PrintBST( t ); printf("\n"); return 0; } 测试数据以及测试结果

BST建立成功。

点击次数:1619
作者: