二叉排序树示例
二叉排序树
收获：
要改变指针，参数就要用指针的指针。如insert (BinaryTree **current,TREE_TYPE value)。但只是输出或使用则使用指针就ok如 中序遍历函数 inOrderTraverse ( BinaryTree * root),这里的形参是指针。中序遍历伪代码
如果根结点为空 则空操作中序遍历左子树输出 根结点值中序遍历右子树貌似关于树的递归的程序 第一句话都是在判断树根是否为空。
main.c源程序
#
include <stdlib.h
>#
include <stdio.h
>#
include "binaryTree.h" /* 声明了关于二叉树函数原型的接口 */#
define N
6/* * === FUNCTION ====================================================================== * Name: main * Description: 二叉搜索树 示例主调函数 * Parameter: * Create:14:58 2012-8-14 * Lastmodify:14:58 2012-8-14 * Author: mang * Version: 1.0 * ===================================================================================== */ intmain (
int argc,
char *argv[] ){
int a[N]
={
6,
4,
5,
8,
2,
3};
int i,k; BinaryTree
*tree
=NULL;
/*新建一个指向二叉搜索树的指针 */ BinaryTree
*result
=NULL;
/* * 不断向二叉搜索树中插入结点 */ for (i
= 0; i
< N; i
++) { insert(
&tree,a[i]);
/* 注意第一个实参是&tree 是指针的指针或者指针变量所在内存单元的地址 */ } printf(
"中序遍历二叉搜索树\n"); inOrderTraverse(tree);
/* 中序遍历输出二叉搜索树 *//* * 下面是关于查找二叉排序树的代码 */ printf(
"\n输入要查找的值,输入0表示结束:"); scanf(
"%d",
&k);
while(k
!=0){
if((result
=find(tree,k))
!=NULL){ printf(
"找到啦,其地址为%d",(
int)result);
/* 返回的是指针，这里强制转换成整型 */ printf(
"其值为%d\n",result
->value); }
else { printf(
"没有找到\n"); } printf(
"\n输入要查找的值,输入0表示结束:"); scanf(
"%d",
&k); }
/* * 注意下面的写法有问题，当你输入k=0时 还会查找一遍 这里不删除，留着以后观摩 */// do {// printf("\n输入要查找的值,输入0表示结束:");// scanf("%d",&k);// if((result=find(tree,k))!=NULL){// printf("找到啦,其地址为%d",result);// printf("其值为%d\n",result->value);// }// else {// printf("没有找到\n");// }// } while (k!=0); return EXIT_SUCCESS;}
/* ---------- end of function main ---------- */
binaryTree.h 源程序
这里对二叉树用到的函数做了个声明，可以当做一个接口。具体的函数实现由binarySearchTree.c完成。
#
define TREE_TYPE
intstruct binaryTree { TREE_TYPE value;
struct biaryTree
* left;
struct biaryTree
* right;}
/* optional variable list */;
typedef struct binaryTree BinaryTree;
void insert(BinaryTree
**current,TREE_TYPE value);BinaryTree
*find(BinaryTree
* tree,TREE_TYPE value );
void inOrderTraverse(BinaryTree
*);
binarySearchTree.c源程序 关于二叉搜索树的所有函数都在这里。包括插入 中序遍历 查找
#
include <stdlib.h
>#
include <stdio.h
>#
include "binaryTree.h"/* * === FUNCTION ====================================================================== * Name: insert * Description:向二叉搜索树中插入元素。是以链表的形式表示结点，所以这里不受元素个数的限制。 * Parameter: BinaryTree **current * TREE_TYPE value 要插入的值。其中TREE_TYPE在binaryTree.h另define为int * Create:15:05 2012-8-14 * Lastmodify:15:05 2012-8-14 * Author: mang * Version: 1.0 * ===================================================================================== */ voidinsert (BinaryTree
**current,TREE_TYPE value){
/* 注意：这里为什么要用 **current 因为我们改变的是指针变量的值，所以传递的必须是指针的指针。在中序遍历函数中因不需要改变指针变量的值，所以传递的是指针。 * 提示：如果要在函数中改变指针 用两种方法。第一种：函数形参用指针的指针。第二种 函数返回指针。 *//* * 如果根结点为空，则新建结点 * 否则 如果value>根结点->value 则把该值插入其右子树 * 否则 如果value<根结点->value 则把该值插入其左子树 */ if (
*current
==NULL) {
*current
=(BinaryTree
*)malloc(
sizeof(BinaryTree));
if((
*current)
!=NULL){ (
*current)
->value
=value; (
*current)
->left
=NULL; (
*current)
->right
=NULL; }
else { printf(
"新建结点出错\n"); exit(
1); } }
else if(value
>(
*current)
->value){ insert(
&(
*current)
->right,value); }
else if(value
<(
*current)
->value){ insert(
&(
*current)
->left,value); }
return ;}
/* ----- end of function insert ----- *//* * === FUNCTION ====================================================================== * Name: inOrderTraverse * Description: 中序遍历树 * Parameter: BinaryTree *root 指向二叉搜索树的根结点 * Create:15:11 2012-8-14 * Lastmodify:15:11 2012-8-14 * Author: mang * Version: 1.0 * ===================================================================================== */ voidinOrderTraverse ( BinaryTree
* root){
/* * 如果根结点为空什么也不做 * 否则 * 先中序遍历左子树 * 再输出根结点的值 * 再中序遍历右子树 * 注意有的地方是这样写的：也是对的，但没有处理根结点为空的情况 * 如果左子树不空则中序遍历左子树 * 再输出根结点的值 * 如果右子树不空则中序遍历右子树 */ if(root
==NULL){ ; }
else { inOrderTraverse(root
->left); printf(
"%d ",root
->value); inOrderTraverse(root
->right); }
return ;}
/* ----- end of function inOrderTraverse ----- */BinaryTree
*find(BinaryTree
* tree,TREE_TYPE value );
/* * === FUNCTION ====================================================================== * Name: find * Description: * Parameter: * Create: * Lastmodify: * Author: mang * Version: 1.0 * ===================================================================================== */ BinaryTree
* find ( BinaryTree
*current,TREE_TYPE value){
if(current
==NULL){
return NULL; }
else {
if (value
==current
->value) {
return current; }
else if(value
>current
->value){ find(current
->right,value); }
else if (value
<current
->value) { find(current
->left,value); } }}
/* ----- end of function find ----- */
makefile 源程序
main.exe
:main.o binarySearchTree.o gcc
-Wall
-o main.exe main.o binarySearchTree.omain.o
:main.c gcc
-Wall
-o main.o
-c main.cbinarySearchTree.o
:binarySearchTree.c gcc
-Wall
-o binarySearchTree.o
-c binarySearchTree.cclean
: del
*.obj
*.o
*.exe
From WizNote
转载于:https://www.cnblogs.com/mang/archive/2013/02/21/2920239.html
