Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1436499
  • 博文数量: 241
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-11 22:27
个人简介

--

文章分类

全部博文(241)

文章存档

2021年(3)

2019年(6)

2018年(1)

2017年(9)

2016年(21)

2015年(50)

2014年(125)

2013年(26)

我的朋友

分类: C/C++

2014-03-05 17:57:36

题目:给定一个二叉树,获取该二叉树的宽度深度。
代码:

点击(此处)折叠或打开

  1. #include "OJ.h"
  2. #include <string.h>
  3. #include <stdio.h>

  4. /*
  5. Description
  6.          给定一个二叉树,获取该二叉树的宽度深度。
  7. Prototype
  8.          int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)
  9. Input Param
  10.          head 需要获取深度的二叉树头结点
  11. Output Param
  12.          pulWidth 宽度
  13.          pulHeight 高度
  14. Return Value
  15.          0 成功
  16.          1 失败或其他异常
  17. */

  18. int TreeDepth(BiNode* pTop)
  19. {
  20.     if (pTop == NULL)
  21.     {
  22.         return 0;
  23.     }
  24.     else
  25.     {
  26.         int left = TreeDepth(pTop->left);
  27.         int right = TreeDepth(pTop->right);
  28.         return (left>right? left+1:right+1);
  29.     }
  30. }

  31. void bt_level_num(BiNode* tree, int a[], int h) {
  32.     if (tree == NULL)
  33.     {
  34.         h = 0;
  35.     }
  36.     else
  37.     {
  38.         a[h] += 1;
  39.         bt_level_num(tree->left, a, h + 1);
  40.         bt_level_num(tree->right, a, h + 1);
  41.     }
  42. }

  43. int bt_width(BiNode* tree) {
  44.     int a[N]={0}, h = 0, max=0, i;

  45.     bt_level_num(tree, a, h);
  46.  
  47.     for (i = 0; i < N; i++)
  48.     {
  49.         if (a[i] > max)
  50.         {
  51.             max = a[i];
  52.         }
  53.     }
  54.     return max;
  55. }


  56. int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)
  57. {
  58.     /*在这里实现功能*/
  59.     BiNode* pTop = &head;
  60.     if (pTop == NULL)
  61.     {
  62.         *pulWidth = 0;
  63.         *pulHeight = 0;
  64.         return -1;
  65.     }

  66.     unsigned int depth = TreeDepth(pTop);
  67.     *pulHeight = depth;

  68.     unsigned int wd = bt_width(pTop);
  69.     *pulWidth = wd;
  70.     return 0;
  71. }

阅读(1069) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~