wex13_5a.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "queue.h"

// traverse the array based tree by level and visit each node
template <class T>
void LevelScan(T A[], int n, void visit(T& item))
{
	// store siblings of each node in a queue so that they are
	// visited in order at the next level of the tree
	Queue<int> Q;
	// keep track of last index in current level
	int i = 0, endLevel = 0;

	// initialize the queue by inserting the root in the queue
	Q.QInsert(i);
   
	// continue the iterative process until the queue is empty
	while(!Q.QEmpty())
	{
		// delete front node from queue and execute visit function
		i = Q.QDelete();
		visit(A[i]); 
            
		// if a left child exists, insert it in the queue
		if(2*i+1 < n)
			Q.QInsert(2*i+1);
		// if a right child exists, insert next to its sibling
		if(2*i+2 < n)
			Q.QInsert(2*i+2);
		if (i == endLevel)
		{
			// visited the last node at the current level.
			// output a newline and determine the last node at
			// the next level
			cout << endl;
			endLevel = 2*endLevel + 2;
		}
	}
	// output a final newline if the tree is not full.
   // the tree is full if the parent of endLevel is i
	if (i != (endLevel-1)/2)
		cout << endl;
}

void print(int& item)
{
	cout << item << "  ";
}

void main(void)
{
	int a[63], n;
	
	cout << "Enter the number of nodes (1 <= n <= 63): ";
	cin >> n;

	for (int i=0;i < n;i++)
		a[i] = i+1;
	LevelScan(a,n,print);
}

/*
<Run>

Enter the number of nodes (1 <= n <= 63): 35
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  
*/