이 진 트 리 기본 조작 c 구현

헤더 파일:

/*
  Name:        
  Author: Unimen
  Date: 2011/10/6 23:42:57
*/

#ifndef _BITREE_H_
#define _BITREE_H_

const int maxn = 100;   //       
typedef char ElemType;

typedef struct node
{
	ElemType value;
	struct node *pLChild, *pRChild;
}BiTNode, *PBiTNode;

//       
void CreateBiTree(PBiTNode &root);
//         
void RecurPreOrder(PBiTNode root);
//          
void PreOrder(PBiTNode root); 
//         
void RecurInOrder(PBiTNode root); 
//           
void InOrder(PBiTNode root); 
//         
void RecurPostOrder(PBiTNode root);
//          
void PostOrder(PBiTNode root); 
//       
void bfs(PBiTNode root); 


#endif

함수 구현 파일

/*
  Name:        
  Author: Unimen
  Date: 2011/10/6 23:42:57
*/

#include <iostream>
#include <cassert>
#include "BiTree.h"
using namespace std;

void CreateBiTree(PBiTNode &root)
{
	char ch;
	ch = cin.get();
	if (' ' == ch)
	{
		while ((ch=cin.get()) != '
');
		root = NULL;
	}
	else
	{
		root = new BiTNode;
		root->value = ch;
		while ((ch=cin.get()) != '
');
		CreateBiTree(root->pLChild);
		CreateBiTree(root->pRChild);
	}
}

void RecurPreOrder(PBiTNode root)
{
	if (root != NULL)
	{
		cout<<root->value<<" ";
		PreOrder(root->pLChild);
		PreOrder(root->pRChild);
	}
}

void PreOrder(PBiTNode root)
{
	assert(root);
	
	PBiTNode stack[maxn];
	int top = 0;
	++top;
	stack[top] = root;
	while (top > 0)
	{
		root = stack[top];
		--top;
		cout<<root->value<<" ";
		
		if (root->pRChild != NULL)
		{
			++top;
			stack[top] = root->pRChild;
		}
		if (root->pLChild != NULL)
		{
			++top;
			stack[top] = root->pLChild;
		}
	}
}

void RecurInOrder(PBiTNode root)
{
	if (root != NULL)
	{
		RecurInOrder(root->pLChild);
		cout<<root->value<<" ";
		RecurInOrder(root->pRChild);
	}
}

void InOrder(PBiTNode root)
{
	assert(root);
	
	PBiTNode stack[maxn];
	int top = 0;
	PBiTNode temp = NULL;
	while (root!=NULL || top>0)
	{
		if (root != NULL)
		{
			++top;
			stack[top] = root;
			root = root->pLChild;
		}
		else
		{
			temp = stack[top];
			--top;
			cout<<temp->value<<" ";
			root = temp->pRChild;
		}
	}
}

void RecurPostOrder(PBiTNode root)
{
	if (root != NULL)
	{
		RecurPostOrder(root->pLChild);
		RecurPostOrder(root->pRChild);
		cout<<root->value<<" ";
	}
}

//     ，     ，      ，      
void PostOrder(PBiTNode root)
{
	assert(root);

	bool bVisitedRight[maxn] = {false};
	PBiTNode stack[maxn];
	int top = 0;
	PBiTNode temp = NULL;
	
	while (root!=NULL || top>0)
	{
		if (root != NULL)
		{
			++top;
			stack[top] = root;
			root = root->pLChild;
			bVisitedRight[top] = false;
		}	
		else
		{
			temp = stack[top];
			if (bVisitedRight[top] == true)
			{
				cout<<temp->value<<" ";
				--top;
			}
			else
			{
				bVisitedRight[top] = true;
				root = temp->pRChild;	
			}	
		}
	}
}

void bfs(PBiTNode root)
{
	assert(root);
	
	PBiTNode queue[maxn];
	PBiTNode temp = NULL;
	int front, near;
	near = front = 0;
	
	++near;
	queue[near] = root;
	while (front < near)
	{
		front = (front + 1) % maxn;
		temp = queue[front];
		cout<<temp->value<<" ";
		if (temp->pLChild != NULL)
		{
			near = (near + 1) % maxn;
			queue[near] = temp->pLChild;
		}
		if (temp->pRChild != NULL)
		{
			near = (near + 1) % maxn;
			queue[near] = temp->pRChild;
		}
	}
}

기능 테스트:

/*
  Name:        
  Author: Unimen
  Date: 2011/10/6 23:42:57
*/

#include <iostream>
#include "BiTree.h"
using namespace std;

int main()
{
	PBiTNode root;
	CreateBiTree(root);
	
	cout<<"      ：  ";
	RecurPreOrder(root);
	cout<<endl;
	cout<<"       ：";
	PreOrder(root);
	cout<<endl;
	
	cout<<"      ：  ";
	RecurInOrder(root);
	cout<<endl;
	cout<<"       ：";
	InOrder(root);
	cout<<endl;
	
	cout<<"      ：  ";
	RecurPostOrder(root);
	cout<<endl;
	cout<<"       ：";
	PostOrder(root);
	cout<<endl;
	
	cout<<"    ：";
	bfs(root);
	cout<<endl;

	return 0;
}