用C语言递归创建二叉排序树的探究

天津高等学校联合学报!"#$%&’"()*&%+*%c语言 二叉排序树,-#’。/*012$32&$%*%0 语言仅有单向的"值传递#$所以多年来数据结构教课书中$皆使用指针函数来编程$进而提高了教师在讲述中的复杂性!构造一个用递归函数建立 二叉树的 语言教课书中没有解决的问题!关键词! 数据构架%二叉树%递归%遍历%值传递中图分类号! E9(00!! 文献标识码! 文章编号!0##23"$24 收稿日期!"##%3#43#0 作者简介!杜有威& 02$53 $天津市人$天津职工科学技术大学计算机系副教授 $理学学士$主要探究 应用数学与计算机应用! 一$二叉树的构建是数据结构和算法设计中不可缺少的内容 在电子计算机今天发明时!人们主要使用其迭代"判断用途进行方程式中根的求精计算!所用到的数据仅为整型 或实型即能满足规定!计算求精课程称作数值步骤!而以前的数据结构被称作表处理# 随着电子计算机向非数值计算的管控领域发展!所涵盖到的难题越来越复杂$若解决同一个问题!构造不同的数 据结构会对应复杂程度不同的算法!而设计一个合适的数据结构能使算法的复杂程度大大降低#编程人员在实践中 体会到%学好一种高级语言仅能解决三成所见到的难题!而学好数据结构却能缓解八成所遭遇的难题!因此!在硬件 设计中选取一个合适的数据结构越发显得重要# 在管理科学领域中!很多难题都可以转换为树 E。

77 型结构!而多叉树又都可以转换为一棵等价的二叉树 E。77#在这里二叉树的定义为%或者为空"或者由根与两棵互不相交!称为根结点左子树和右子树的二杈树组成!即二 叉树本身还是由二叉树组成$由此可见二杈树的定义是数组的 G7?H。I>J7 #二叉树具有结构简洁"操作便捷的缺点!能 够在数组 过程中构建二杈树的链式存储结构$使一个非线性结构的管控难题线性化#从而使众多管理领域中的弊端!都可以在二叉树的构建与数组过程中给与解决!因此!二叉树的构建一直为数据结构进而为算法设计课程 中的重点内容# 二$最初是用 9-I?-+ 语言数组描述二叉树的构建过程 上面提到二叉树是数组定义的!如同解递归函数的典型解法&汉诺塔’一样!二叉树的构建过程只有使用递归算 法能够超过最完美#在 9-I?-+ 语言中的方式参数有数组和函数两种!其中变参传递的是地址!而二叉树中根指针的内 容(即根地址)从空二叉树到有一个根节点的二叉树是差异的!必须使用函数参数传递地址功能来设置这个根节点的 地址值#在 9-I?-+ 语言中数组参数可以很自然地编写使用递归函数建立二叉树的程序#而这个源程序比较简单"易 于静态阅读和进行教学分析!因此使用递归函数建立与数组二叉树是数据结构课程的经典算法#本文第五部分 言源程序E。

77(? 是通过经典的 9-I?-+ 语言构建二叉树源程序清单逐句翻译过来!由于可以依据不同编程语言的句型 规则逐句进行对照和参考!故以下省略了 9-I?-+ 语言的源程序清单# 三$当前中国改用 年代随编写KB>L 操作系统而共同演进成熟的!在设计 语言编译程序时!将变量中数据释放全部采取双向的*值传递+方式!这种设计为今后完善二叉树的过程带来麻烦#二叉树的根节点应该变化后的返回 语言的单向传递指针方式只能使数组和变量共同占用一个单元!即仅能改变共占变量单元的数值!不能改变根指针的数值$无奈之中!在众多用 语言表述建立二叉树的书籍中都使用返回指针值的变量!即指针函数#MBI7。A )带出这个变化后的根结点值#9-I?-+ 语言编译严谨"不易出错!现在国内大部分高校在表述算法的书籍中还都采取 9-I?-+ 语言!国内教学改革中 开始使用 万方数据身固有的递归特征编程!只能构造一个含糊不清"不易讲述的二叉树建立程序!这降低了静态分析和学生讲述中的复 杂性#经典丛书由清华大学严蔚敏"吴伟民编著的$数据结构%& 语言中的引用类型数组!引用是 源程序E。770(? 是按现行通用教课书中指针函数构思编写的构建与中序遍历一棵二叉树*其输 入为一串字符!建立二叉树后!经过中序线性数组搜索"输出为按字典大小排序排列的字符串#由于这不是一个递归 程序!我们在静态阅读和比较后!就会感觉到不如本文第五部分的递归函数程序 E。

77(? 构思清晰# 定义节点的数据类别=>BV# B7UR-A-%W3$R-A- Y&B&AEG1D^E_^EG^^M&,MO’GO^G 四!不同于现存的数据结构教课书!类似9-I?-+ 一样使用 语言递归表述建立二叉树过程上世纪 年代中期!笔者就用9-I?-+ 语言讲授数据结构课程!上世纪 言不能使用递归函数描述创建二叉树的过程!在课堂讲述过程中觉得有些含糊不清!许多讲授过这门课程的同学对这部分内容亦有同感#因此!笔者多年来一直注意诸多版本用 语言表述(数据结构)的书籍!看能否有类似9-I?-+ 万方数据著者不同!出版社不同"但在建立二叉树的之后"大都使用#指针函数$来表述"没有类似 9-I?-+ 语言链表描述建立递归 语言程序%由于 语言仅有单向的#值传递$"而采取指针来释放数组"仅能差异这个指针指向的值"不会影响原始指针的值%鉴于以下状况"笔者猜测若要释放指针本身"能否类似指针变量 的方法(即指向指针的指针"这里 变量中的内容若当数组的实参(根地址 )为一个指向指针的指针时"实!形参数间的数据释放后就可以设置原始根节点的指针数值 "这样能够够类似9-I?-+ 程序一样递归创建二叉树的程序%笔者用以上设想编写链表创建二叉树的 源程序E。

77(? 如前面第五部分所示%程序输入!输出的状况与上面第三部分所述相同% 这里先对 源程序E。77(? 作一些解释+主控程序 开始赋为空指针"主调函数MBI7。A 是一个指向根地址的指针%而变量MBI7。A ##E。77接收这个二级间址"将根地址 给指针#E。77 #E。77为带有根地址值的一个指针变量"这样释放参数就可以设置二叉树根节点的指针数值%下面分 两种状况讨论根指针读取时差异的数值+ #E。77(语句 #E。77

77 E。77"结构变量 ##E。77是包括一个字符域和左右两个指针域的叁个域结点% 五"递归函数的 ">B?+HR7%IAR>*(@$">B?+HR7%IAR+>C(@$ "R7Q>B7=7BI>X7*Q 可以双向传递的根地址#E。77# 将新建立二叉树的根地址赋给#E。77# B7UR-A-%PA。3$R-A- 注(以上的程序E。770(? E。77(?均是在 EH。C*3D"(# (7L7文件大小为 2aC 左右"和 )>IH-+3 (7L7文件在 O7CH 子文件夹中大小为0!$VC "环境下编译安装通过&保证无法运行) 六!小结 通过下面两个 语言源程序E。770(? E。77(?的讨论与对比&可以发现由于二叉树是数组定义的&使用泛型函 数描述的源程序 E。77(? 比较自然*简洁)符合二叉树的定义&学习者易于理解程序的静态运行过程)递归程序 E。77( 语言仅能进行单向数值传递的表述%使 语言教课书中对二叉树建立的表述)古人张潮曰+发前人未发之论*方是奇书,)希望这篇文章才能对用 语言构建二叉树&起到抛砖引玉*共同提升教学品质的功用)若本文的编程模式才能引起同仁的一些愉快思考&亦是笔者最大的心愿) 参考文献" _7。

C7。A‘?@>+RA(D语言大全 北京#电子工业出版社$ 022#( 北京#清华大学出版社 022"(［责任编辑：刘金冷］ 81%1"2)$+,9%*, 1#+:21"#1"*#$81)(2%*71?(,)#*+, @#A03 %&,。;6%40&-%&-012。-。,-+34D-3+%=E/&4%F6。& +0;6%8-)。-)。,&0-;%%&+%c语言 二叉排序树,065%2; %-%G-;00?,10+8。&77

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-120511-1.html