BT *CreateBiTree() //根据带空枝的二叉树先根遍历序列，成功构造返回根指针 { // 请在这里补充代码，完成本关任务 /********** Begin *********/ /********** End **********/ }

以下是根据先序遍历序列创建二叉树的代码实现：

BT *CreateBiTree() {
    char ch;
    cin >> ch;
    if (ch == '#') {
        return NULL;
    }
    BT *root = new BT;
    root->data = ch;
    root->LChild = CreateBiTree();
    root->RChild = CreateBiTree();
    return root;
}

相关问题

完善代码：#include <stdio.h> #include <malloc.h> #include <conio.h> typedef int ElemType; typedef struct BiTreeNode { ElemType data; struct BiTreeNode *lchild, *rchild; } BiTreeNode,*BiTree; void Visit(BiTree bt) { printf("%d ",bt->data); } int max(int x,int y) { if (x>y) return x; else return y; } //二叉树的先序遍历算法 void PreOrder(BiTree bt) /* bt为指向根结点的指针*/ { if (bt) /*如果bt为空，结束*/ { Visit (bt ); /*访问根结点*/ PreOrder (bt -> lchild); /*先序遍历左子树*/ PreOrder (bt -> rchild); /*先序遍历右子树*/ } } //二叉树的中序遍历递归算法 void InOrder(BiTree bt)/* bt为指向二叉树根结点的指针*/ { } //二叉树的后序遍历递归算法 void PostOrder(BiTree bt) /* bt为指向二叉树根结点的指针*/ { } //结合“扩展先序遍历序列”创建二叉树,递归 BiTree CreateBiTree(ElemType s[]) { BiTree bt; static int i=0; ElemType c = s[i++]; if( c== -1) bt = NULL; /* 创建空树 */ else { bt = (BiTree)malloc(sizeof(BiTreeNode)); bt->data = c; /* 创建根结点 */ bt->lchild = CreateBiTree(s); /* 创建左子树 */ bt->rchild = CreateBiTree(s); /* 创建右子树 */ } return bt; } //根据先序序列、中序序列建立二叉树，递归 BiTree PreInOrder(ElemType preord[],ElemType inord[],int i,int j,int k,int h) { BiTree t; //添加代码 return t; } BiTree CreateBiTree_PreIn(ElemType preord[],ElemType inord[],int n) { BiTree root; if (n<=0) root=NULL; else root=PreInOrder(preord,inord,0,n-1,0,n-1); return root; } //统计叶结点个数 int BitreeLeaf ( BiTree bt ) { if ( bt == NULL ) return 0 ; /* 空树，叶子数为0 */ if ( bt->lchild ==NULL&& bt->rchild == NULL) return 1 ; /*只有一个根结点，叶子数为1*/ return ( BitreeLeaf( bt -> lchild ) + BitreeLeaf ( bt -> rchild )) ; } //统计二叉树的深度 int BitreeDepth ( BiTree bt ) { int d = 0,depthL, depthR; /*depthL和depthR分别为左、右子树的深度*/ if ( bt == NULL ) return 0 ; /*空树，深度为0 */ if ( bt -> lchild ==NULL && bt -> rchild == NULL) return 1; /*叶子结点，深度为1 */ depthL = BitreeDepth ( bt -> lchild ) ; /*左子树深度 */ depthR = BitreeDepth ( bt -> rchild ) ; /*右子树深度 */ d = max (dept

hL, depthR) + 1; /*当前结点深度*/ return d ; } int main() { ElemType s1[] = {1,2,-1,-1,3,-1,-1}; BiTree bt1; bt1 = CreateBiTree(s1); printf("二叉树的先序遍历："); PreOrder(bt1); printf("\n"); printf("二叉树的中序遍历："); InOrder(bt1); printf("\n"); printf("二叉树的后序遍历："); PostOrder(bt1); printf("\n"); ElemType pre[] = {1,2,3}; ElemType in[] = {2,1,3}; BiTree bt2; bt2 = CreateBiTree_PreIn(pre,in,3); printf("根据先序序列、中序序列建立的二叉树的先序遍历："); PreOrder(bt2); printf("\n"); printf("根据先序序列、中序序列建立的二叉树的中序遍历："); InOrder(bt2); printf("\n"); printf("根据先序序列、中序序列建立的二叉树的后序遍历："); PostOrder(bt2); printf("\n"); printf("二叉树的叶子结点个数：%d\n",BitreeLeaf(bt2)); printf("二叉树的深度：%d\n",BitreeDepth(bt2)); return 0; }

注释已经比较详细了，只需要实现InOrder和PostOrder函数即可。InOrder函数中需要先中序遍历左子树，然后访问根结点，最后中序遍历右子树。PostOrder函数中需要先后序遍历左子树，然后后序遍历右子树，最后访问根结点。完整代码如下：

//算法5.6 统计二叉树中结点的个数 #include<iostream> using namespace std; //二叉树的二叉链表存储表示 typedef struct BiNode 1 char data; //结点数据域 struct BiNode *lchild,*rchild; //左右孩子指针 ] BiTNode,*BiTree; //用算法5.3建立二叉链表 void CreateBiTree(BiTree &T) //用算法5.3建立二叉链表 void CreateBiTree(BiTree &T) //按先序次序输入二叉树中结点的值(一个字符)，创建二叉链表表示的二叉树T char ch; cin >> ch; if(ch=='#') T=NULL; //递归结束，建空树 else T=new BiTNode; T->data=ch; //生成根结占 CreateBiTree(T->lchild). /递归创建左子树 CreateBiTree(T->rchild); /递归创建右子树 //else ) //CreateBiTree //else ) //CreateBiTree int NodeCount(BiTree T) if(T==NULL) return 0; 如果是空树，则结点个数为0，递归结束 else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1; //否则结点个数为左子树的结点个数+右子树的结点个数+1 void main() void main() BiTree tree; cout<<"请输入建立二叉链表的序列：\n"； CreateBiTree(tree); cout<<"结点个数为： "<<NodeCount(tree)<<endl; )

这段代码是用来统计二叉树中结点个数的，使用的是二叉链表存储结构。其中CreateBiTree函数用来建立二叉树，按照先序遍历的顺序输入二叉树中结点的值，如果输入的是'#'代表该节点为空。NodeCount函数用来递归计算二叉树中结点的个数，如果是空树，返回0；否则返回左子树的结点个数+右子树的结点个数+1。最后在主函数中调用CreateBiTree和NodeCount函数，并输出结果。