WHCSRL 技术网

C语言 (顺序存储) 求二叉树的深度 (利用树的长度)

//日常记录  C语言 
//顺序存储 创建树 用树的长度求深度
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MaxSize 100000
typedef char SeqTree[MaxSize];
int Init(SeqTree T)             //初始化 
{
	for( int i= 1 ; i<MaxSize ;i++ )
	{
		T[i] = '';
	 } 
}
char Creat(SeqTree T)           //创建树 
{
	char ch;
	fflush(stdin);
	for(int i= 1; i<MaxSize ; i++)
	{
		scanf("%%c",&ch);
		if(ch != '0') 
		{
			T[i] = ch;
		}
		else
		{
		 T[i] = NULL;
		}

		if(ch == '#') break; 
	}
}
void LevelOrder(SeqTree T)      //层序遍历 
{
	for(int j= 1; j<MaxSize ;j++ )
	{
		if(T[j] == '#' ) break;
		else if(T[j] == NULL) continue;
		else printf("%%c ",T[j]);
	}
 } 
 int Length(SeqTree T)         //求树的长度 
{
	int count = 0;
	for ( int i =1 ; i< MaxSize ; i ++ )
	{
		if(T[i] == '#')
			break; 
		else count ++;
	}
	return count ;
}
int High(SeqTree  T , int length )//求深度
{
	int high =0 , m = 1 ;
	while (m < length)
	{
		high++  ;
		m = m *2 ;
	}
	return high;
 } 
 int main()
{
	SeqTree T;
//初始化 
	Init(T);
	printf("请输入树的节点,无结点输入0,结束输入#
"); 
//建树 
	Creat(T);
//层序 
	printf("层序遍历为:
") ;
	LevelOrder(T);
	printf("
");
//求树的长度
	int length =Length(T);
	printf("树的长度为:%%d 
", length	 ) ;
	printf("
");
//求树的深度 
	int high = High(T,length) ;
	printf("树的深度为:%%d",high);
	printf("
");
}
//测试 
//请输入树的节点,无结点输入0,结束输入#
//abcd00e#
//层序遍历为:
//a b c d e
//树的长度为:7
//
//树的深度为:3
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
推荐阅读