二叉树的函数实现(一)
二叉树的创建是一个递归的过程,创建过程中如果先创建根结点,再创建根结点的左子树,最后再创建根结点的右子树的方式称为先序创建.需要注意的是,创建二叉树的递归函数需要出口,我们在程序中设定 # 作为空结点的声明,即如果遇到 # 则意味着该结点为空,不为其分配内存空间:
二叉树的中序创建如上图所示,在此我们介绍两种函数实现,分别以字符串形式创建的 void PreOrderCreate_str(BiTree& root, const char*& str) 函数和以输入形式创建的 void PreOrderCreate_input(BiTree& root) 函数:
BiTree AskNode(ElemType data)
{
BiTree BiNode = (BiTree)malloc(sizeof(BiTreeNode));
if (NULL == BiNode)
exit(OVERFLOW);
BiNode->data = data;
BiNode->lchild = BiNode->rchild = NULL;
return BiNode;
}
//先序创立二叉树:先建立根结点 再建立左子树 最后建立右子树
void PreOrderCreate_str(BiTree& root, const char*& str)
{
if ('#' == *str) //以 # 作为空结点
{
str++;
root = NULL;
}
else
{
root = AskNode(*str);
str++;
PreOrderCreate_str(root->lchild, str);
PreOrderCreate_str(root->rchild, str);
}
return;
}
//每次使用一个字符 就需要使用下一个字符创建二叉树 相应的传入字符串也要改变
void PreOrderCreate_input(BiTree& root)
{
ElemType c;
printf("please enter the data(# means NULL):");
c = getchar();
getchar(); //除去换行符
if ('#' == c)
root = NULL;
else
{
root = AskNode(c);
printf("please enter the left child of %c,", c);
PreOrderCreate_input(root->lchild);
printf("please enter the right child of %c,", c);
PreOrderCreate_input(root->rchild);
}
return;
}