pex13_1.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <iomanip.h>
#pragma hdrstop

// initialized to 0 by PrintChildInfo and
// incremented by Preorder
int nochild, onechild, twochildren;

// preorder recursive scan of the nodes in array based tree 
template <class T>
void Preorder (T A[], int currindex, int n)
{ 
   // the recursive scan terminates on a empty subtree      
   if (currindex < n)
   {
      // determine the number of children and update the appropriate
      // variable
      if (2*currindex+1 < n)
      	if (2*currindex+2 < n)
      		twochildren++;
      	else
      		onechild++;
      else
      	nochild++;
      Preorder(A,2*currindex+1, n);	// descend left
      Preorder(A,2*currindex+2, n);	// descend right
   }
}
	
// call Preorder for array-based tree A and print
// information about the number of nodes with
// no children, one child and two children
void PrintChildInfo(int A[], int n)
{
	nochild = onechild = twochildren = 0;
	Preorder(A,0,n);
	cout << "Array of " << n << " elements:" << endl;
	cout << "No children" << setw(15) << "One child" << setw(15)
		 << "Two children" << endl;
	cout << setw(6) << nochild << setw(15) << onechild
		 << setw(15) << twochildren << endl;
}

void main(void)
{
	int A[50], B[100];
	
	// tree A = {0,1,2,...,49}
	for(int i=0;i < 50;i++)
		A[i] = i;
	// tree B = {0,1,2,...,99}
	for(i=0;i < 100;i++)
		B[i] = i;
		
	// print child information for each tree
	PrintChildInfo(A,50);
	cout << endl << endl;
	PrintChildInfo(B,100);
}

/*
<Run>

Array of 50 elements:
No children      One child   Two children
    25              1             24


Array of 100 elements:
No children      One child   Two children
    50              1             49
*/