首页 > 其他 > 详细

981统计利用二叉树存储的森林中树的棵数

时间:2018-05-23 12:56:01      阅读:305      评论:0      收藏:0      [点我收藏+]

 技术分享图片

 求用二叉树存储的森林中树的棵数,我们首先需要的是将二叉树转换为森林。

  那么如何计算二叉树存储的森林中树的棵数?

  有这么一个森林与二叉树转换规则:

    从二叉树根开始一直往右子树走,一共路过几个节点,对应的森林就有几个根,

  也就是说,对应的森林有几棵树 高度为h的满二叉树最右边一路有h个节点(就是  

  高度为n),因此对应的森林有h棵树.  

 下面给出二叉树转换成森林的示意图:

技术分享图片

    (没找到作图工具,强行ps做的,线没有对齐,别介意)

 

#include <iostream>
using namespace std;
typedef struct BTNode
{
    char data;
    BTNode *lchild, *rchild;
}BTNode;

void CreatTree(BTNode *&tree)
{
    char ch;
    cin >> ch;
    tree = new BTNode;
    if (ch == #)
        tree = NULL;
    else
    {
        tree->data = ch;
        CreatTree(tree->lchild);
        CreatTree(tree->rchild);
    }
}
void Forest(BTNode *tree, int &treeCount)
{
    while (tree != NULL)
    {
        treeCount++;
        tree = tree->rchild;
    }
}
void DestoryTree(BTNode *&tree)
{
    if (tree != NULL)
    {
        DestoryTree(tree->lchild);
        DestoryTree(tree->rchild);
        delete tree;
    }
}
int main()
{
    BTNode *tree;
    CreatTree(tree);
    int treeCount = 0;
    Forest(tree, treeCount);
    cout << treeCount;
    DestoryTree(tree);
    system("pause");
    return 0;
}

 

981统计利用二叉树存储的森林中树的棵数

原文:https://www.cnblogs.com/nianliwanshao/p/9071508.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!