鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c语言 > >

已知有序数组求最小深度二叉树

来源:互联网 作者:佚名 时间:2013-09-27 08:23
#includestdio.h #includeassert.h #includestdlib.h typedef struct _tree_node { int m_nValue; struct _tree_node *m_pLeft; struct _tree_node *m_pRight; }TreeNode; TreeNode* createNode(int value) { TreeNode* pNode=(TreeNode *)malloc(sizeof(Tre

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef struct _tree_node
{
    int m_nValue;
    struct _tree_node *m_pLeft;
    struct _tree_node *m_pRight;
}TreeNode;


TreeNode* createNode(int value)
{
     TreeNode* pNode=(TreeNode *)malloc(sizeof(TreeNode));
     assert(pNode!=NULL);
     pNode->m_nValue=value;
     pNode->m_pLeft=NULL;
     pNode->m_pRight=NULL;
     return pNode;
}

TreeNode* arrToTree(int *arr,int start,int end)
{
     TreeNode *pHead=NULL;
     if(end>=start)
     {
          int mid=(start+end)>>1;
          pHead=createNode(arr[mid]);
          pHead->m_pLeft=arrToTree(arr,start,mid-1);
          pHead->m_pRight=arrToTree(arr,mid+1,end);
     }   
     return pHead;
}

void printTree(TreeNode *pHead)
{
     if(pHead==NULL)
     return;
     printTree(pHead->m_pLeft);
     printf("%d ",pHead->m_nValue);
     printTree(pHead->m_pRight);
}

int getTreeHeight(TreeNode *pHead)
{
    if(pHead==NULL)
    return 0;
    return getTreeHeight(pHead->m_pLeft)>getTreeHeight(pHead->m_pRight)?getTreeHeight(pHead->m_pLeft)+1:getTreeHeight(pHead->m_pRight)+1;
}

int main()
{
    int arr[]={0,1,2,3,4,5,6,7,8,9};
    int len=sizeof(arr)/sizeof(arr[0]);
    TreeNode *pHead=NULL;
    pHead=arrToTree(arr,0,len-1);
    
    printTree(pHead);
    
    int hight=getTreeHeight(pHead);
    
    printf("\n%d",hight);
    
    system("pause");
    return 0;
}

网友评论
<