2010数据结构实验指导书48

void setVal (const Object& e) { it = e; }

inline BinaryNode<Object>* left() const { return lc; } void setLeft(BinaryNode<Object>* b) { lc = (BinNode*)b; } inline BinaryNode<Object>* right() const { return rc; } void setRight(BinaryNode<Object>* b) { rc = (BinNode*)b; } bool isLeaf() { return (lc == NULL) && (rc == NULL); } };

生成二叉树

根据不同的应用规则可以有各种生成二叉树的方法，如二叉搜索树、表达式树、哈夫曼树等。我们在这里描述一个根据对二叉树各节点遍历所得序列生成二叉树的方法，一般从这样一个序列不一定能生成这棵二叉树。但如果把这二叉树的所有空指针都画出来就得到一棵满的「扩充」的树，根据对这棵「扩充树」的遍历得到的序列，可以生成那棵二叉树。例如，用'@'表示空指针，那么课题一图中那棵「扩充」二叉树的先序遍历得到的节点序列是：

char *extendedPreOrd = "ABD@F@@EG@@H@@C@@"; 用它做为下列二叉树建造函数的输入就得到前图所示的树。 BinNode<char> *BinTreeBuildFrmStr(char *& str) { }

注：把这个函数的参数类型由对二叉树节点指针的引用改为指向指针的指针，很容易把它改为C的函数。

if (*str != '@'){ }

BinNode<char>* root = new BinNode<char>(*str++); root->setLeft(BinTreeBuildFrmStr (str)); root->setRight(BinTreeBuildFrmStr (str)); return root; }

// the NULL pointer '@', just skip it str++; return NULL;

else{