正在阅读：C++数据结构学习:二叉树(2)C++数据结构学习:二叉树(2)

2004-02-14 09:34 出处：PConline 作者：happycock/CSDN 责任编辑：linjixiong

打印树状结构的核心是按层次遍历二叉树，但是，二叉树有许多节点缺左或右子树，连带的越到下面空隙越大。为了按照树的结构打印，必须把二叉树补成完全二叉树，这样下面的节点就知道放在什么位置了——a.push(&zero);但是这样的节点不能让它打印出来，所以对应每个节点，有一个是否打印的标志，按理说pair结构很合适，为了简单我用了并列的两个队列，一个放节点指针——a，一个放打印标志——flag。这样一来，循环结束的标志就不能是队列空——永远都不可能空，碰到NULL就补一个节点——而是变成了到了满二叉树的最后一个节点2^(height+1)-1。——黄皮书对于树高的定义是，空树为的高度为－1。　　　　对于输出格式，注意的是到了第1、2、4、8号节点要换行，并且在同一行中，第一个节点的域宽是后序节点的一半。上面的函数在树的层次少于等于5（height<=4）的时候能正常显示，再多的话就必须输出到文件中去ofstreamoutfile("out.txt");——如果层次再多的话，打印出来也没什么意义了。　　　　二叉搜索树的实现　　实际上就是在二叉树的基础上增加了插入、删除、查找。　　　　#include"BaseTree.h" 　　　　template 　　　　classBSTree:publicBTree 　　　　{ 　　　　public: 　　　　BTNode*&find(constT&data) 　　　　{ 　　　　BTNode**p=&root;current=NULL; 　　　　while(*p) 　　　　{ 　　　　if((*p)->data==data)break; 　　　　if((*p)->dataright);} 　　　　else{current=*p;p=&((*p)->left);} 　　　　} 　　　　return*p; 　　　　} 　　　　boolinsert(constT&data) 　　　　{