Preparing NOJ

计算二叉树的高度和结点数

1000ms 65536K

Description:

二叉树是非常重要的树形数据结构,根据该树的先序、中序或后序遍历序列可以建立一棵二叉树。例如输入先序遍历序列A B # D # # C E # # F # #可以建立图1019-1所示的二叉树,这里用#代表空树或空子树(另一种说法:若无孩子结点,则用#代替),如图1019-2

1019-1

1019-2

请实现基于遍历的二叉树运算:求高度、计算结点数目

Input:

二叉树的先序遍历序列,用#代表空树或空子树。

Output:

共五行

前三行依次输出先序、中序和后序遍历序列,

第四行输出二叉树的高度,

第五行依次输出二叉树总结点数目、叶子结点数目、度为1的结点数目。

Sample Input:

A B # D # # C E # # F # #

Sample Output:

PreOrder: A B D C E F
InOrder: B D A E C F
PostOrder: D B E F C A
3
6 3 1

Note:

//根据先序遍历序列创建一个二叉树!

template<class T>
void BinaryTree<T>::Create(BTNode<T>*& t){
    char c;
    cin>>c;
    if(c=='#')
        t=NULL;
    else{
        t=new BTNode<T>(c);
        Create(t->lChild);
        Create(t->rChild);
    }
}


本题由旧版NOJ导入,来源:CHENZ

Info

NOJ

Provider NOJ

Code NOJ1019

Tags

Submitted 100

Passed 25

AC Rate 25%

Date 04/20/2019 10:03:10

Related

Nothing Yet