现在的位置: 首页 > 综合 > 正文

52 二元树的深度

2018年05月02日 ⁄ 综合 ⁄ 共 1336字 ⁄ 字号 评论关闭

52.二元树的深度。
题目:输入一棵二元树的根结点,求该树的深度。
从根结点到叶结点依次经过的结点(含根、 叶结点)形成树的一条路径,最长路径的长度为
树的深度。
例如:输入二元树:
10
/    \
6    14
/    /    \
4 12    16
输出该树的深度 3。

/*
52.二元树的深度。
题目:输入一棵二元树的根结点,求该树的深度。
从根结点到叶结点依次经过的结点(含根、 叶结点)形成树的一条路径,最长路径的长度为
树的深度。
例如:输入二元树:
		  10
		/    \
	   6    14
	  /    /  \
	4    12   16
输出该树的深度 3。
*/ 
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;


struct BTreeNode{
	int data;
	BTreeNode *left,*right;
}; 

//建立二叉树 
BTreeNode * CreateTree(int data[],int pos,int len)
{
	BTreeNode *tree;
	if(pos>=len) 
	{
		return NULL;
	}
	else
	{
		tree=(BTreeNode *)malloc(sizeof(BTreeNode));
		tree->data=data[pos];
		tree->left=CreateTree(data,2*pos+1,len);//数组坐标 
		tree->right=CreateTree(data,2*pos+2,len);
		return tree;
	}
}

//最大深度 
int getMaxDepth(BTreeNode *root)
{
	if(root==NULL)
		return 0;
	if(NULL==root->left&&NULL==root->right)
		return 0;
		
	int nLeftDepth=0,nRightDepth=0;
	if(NULL!=root->left)
		nLeftDepth=getMaxDepth(root->left)+1;
	if(NULL!=root->right)
		nRightDepth=getMaxDepth(root->right)+1;
		
	return nRightDepth>=nLeftDepth?nRightDepth:nLeftDepth;
}


int main()
{
	/*
		 5
	   4   8
	 7 12 10 	
	*/
	int data[]={5,4,8,7,12,10};
	int len=sizeof(data)/sizeof(int);
	BTreeNode *tree=CreateTree(data,0,len);
	
	int nMaxDep=getMaxDepth(tree)+1;  //求的是根左右的最大深度,根本来就是1 
    cout <<"求二叉树中节点的深度:"<<nMaxDep<<endl;  
    //3
    
    
    /*
		 5
	   4   8
	 7 12 10 13
	16	
	*/
	int data2[]={5,4,8,7,12,10,13,16};
	int len2=sizeof(data2)/sizeof(int);
	BTreeNode *tree2=CreateTree(data2,0,len2);
	
	int nMaxDep2 = getMaxDepth(tree2)+1;  
    cout <<"求二叉树中节点的最大深度:"<<nMaxDep2<<endl;  
    //4
	return 0;
}

抱歉!评论已关闭.