二叉树

// BTree.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;
typedef struct BTree_node {
	int data ;
	BTree_node * left;
	BTree_node * right;
} BTree ;
BTree *create_node ( int data )
{
	BTree *node = new BTree();
	node->data = data ;
	node->left = node->right = NULL ;
	return node;
}
/*
·?μY1é·?ê?2?è?
*/
void insert_node ( BTree * root , int data )
{
	BTree * node = root ;	
	BTree * last = root ;
	while (node != NULL ) {
		last = node ;
		if ( data < node->data ) 
			node = node->left;
		else
			node = node->right;
	}
	if( data < last->data )
		last->left = create_node ( data );
	else
		last->right = create_node ( data );
}
/*
μY1é+??í¨????·?ê?2?è?
*/
void insert_node_recursive ( BTree *node  , int data )
{
	if ( data < node->data ) {
		if ( node->left == NULL ) {
			node->left = create_node ( data ) ;
			return ;
		}else 
			insert_node_recursive( node->left, data );
	}else {
		if (node->right == NULL ) {
			node->right = create_node ( data ) ;
			return ;
		}else {
			insert_node_recursive( node->right, data );
		}
	}		
}
/*
μY1é+?t??????·?ê?2?è?
*/
void insert_node_recursive_ptr2tptr (BTree **node  , int data ) 
{
	if( *node == NULL ){
		*node = create_node ( data ) ;
		return ;
	}
	if ( data < (*node)->data ) 
		insert_node_recursive_ptr2tptr( &((*node)->left), data );
	else
		insert_node_recursive_ptr2tptr( &((*node)->right), data );
}
/*
μY1é+????òyó?μ?·?ê?2?è?
*/
void insert_node_recursive_reference (BTree* &node  , int data ) 
{
	if( node == NULL ){
		node = create_node ( data ) ;
		return ;
	}
	if ( data < node->data ) 
		insert_node_recursive_reference( node->left, data );
	else
		insert_node_recursive_reference( node->right, data );
}
// ?è?ù±éàú(μY1é)
void traversal_DLR_recursive ( BTree * node )
{
	if( node == NULL ) return ;
	cout<< node->data <<",";
	traversal_DLR_recursive ( node->left );
	traversal_DLR_recursive ( node->right );
}
// ?è?ù±éàú(·?μY1é)
void traversal_DLR ( BTree * node )
{
	stack<BTree *> last;
	while ( node != NULL ) {
		cout<<node->data<<",";
		if ( node->left != NULL ) {
			if ( node->right != NULL ) {
				last.push(node->right);
			}
			node =  node->left;
		} else if ( node->right != NULL ) {
			node = node->right;
		} else {
			if ( last.empty() )  return;
			node = last.top();
			last.pop();
		}
	}
}
// ?D?ù±éàú(μY1é)
void traversal_LDR_recursive ( BTree * node )
{
	if( node == NULL ) return ;
	traversal_LDR_recursive ( node->left );
	cout<< node->data <<",";
	traversal_LDR_recursive ( node->right );
}
// ?D?ù±éàú(·?μY1é)
void traversal_LDR ( BTree * node )
{
	stack<BTree *> last;
	while ( node != NULL ) {
		if( !last.empty() && node == last.top() ) {
			cout<<node->data<<",";
			if ( node->right != NULL ) {
				last.pop();
				node = node->right;
			} else {
				last.pop();
				if ( last.empty() )  return;
				node = last.top();
			}
		} else if ( node->left != NULL ) {
			last.push(node);
			node =  node->left;
		} else if ( node->right != NULL ) {
			cout<<node->data<<",";
			node = node->right;
		} else {
			cout<<node->data<<",";
			if ( last.empty() )  return;
			node = last.top();
		}
	}
}
// oó?ù±éàú(μY1é)
void traversal_LRD_recursive ( BTree * node )
{
	if( node == NULL ) return ;
	traversal_LRD_recursive ( node->left );
	traversal_LRD_recursive ( node->right );
	cout<< node->data <<",";
}
// oó?ù±éàú(·?μY1é,???¨?ú)
void traversal_LRD ( BTree * node )
{
	stack<BTree *> last;
	stack<BTree *> last_left;
	stack<BTree *> last_right;
	/*
	if ( root->left != NULL ) {
		BTree * node = root->left;
		while ( node != NULL ) {
			if ( !last_left.empty() && node == last_left.top() ) {
				if  ( node->right != NULL ) {
					node = node->right;
				} else {
					cout<<node->data<<",";
					last_left.pop();
					if ( last_right.empty() )  return;
					node = last_right.top();
				}
			} else if ( node->left != NULL ) {
				last_left.push(node);
				if ( node->right != NULL ) {
					last_left.push( node->right );
				}
				node = node->left;
			} else if( node->right != NULL ) {
				node =  node->right;
			} else {
				cout<<node->data<<",";
				if ( last.empty() )  return;
				node = last.top();
			}
		}
	} else if ( root->right != NULL ) {
		BTree * node = root->right;
		while ( node != NULL ) {
			if ( !last_right.empty() && node == last_right.top() ) {
				if  ( node->right != NULL ) {
					node = node->right;
				} else {
					cout<<node->data<<",";
					last_right.pop();
					if ( last_right.empty() )  return;
					node = last_right.top();
				}
			} else if ( node->left != NULL ) {
				last_right.push(node);
				if ( node->right != NULL ) {
					last_right.push( node->right );
				}
				node = node->left;
			} else if( node->right != NULL ) {
				node =  node->right;
			} else {
				cout<<node->data<<",";
				if ( last.empty() )  return;
				node = last.top();
			}
		}
	}
	cout<<root->data<<endl;
	*/
	while ( node != NULL ) { 
		if( !last.empty() && node == last.top() ) {
			if ( node->right != NULL  ) {
				//last.push(node->left);
				node = node->right;
			}  else {
				cout<<node->data<<",";
				last.pop();
				if ( last.empty() )  return;
				node = last.top();
			}
			
		} else if ( node->left != NULL ) {
			last.push(node);
			node =  node->left;
		} else if ( node->right != NULL ) {
			//cout<<node->data<<",";
			node = node->right ;
		} else {
			cout<<node->data<<",";
			if ( last.empty() )  return;
			node = last.top();
		}
	}
	
}
int main(int argc, char* argv[])
{
	
	BTree * root =create_node ( 6 ) ;
	BTree * &node = root ;
	//2?è?(??í¨)
	insert_node ( root , 19 );
	insert_node ( root , 4 );
	//2?è?(μY1é)
	insert_node_recursive( root , 3 );
	//2?è?(?t??????)
	insert_node_recursive_ptr2tptr(&root , 5 );
	//2?è?(òyó?)
	insert_node_recursive_reference (  node , 10 );
	cout<<"?è?ù±éàú(μY1é)￡o"<<endl;
	traversal_DLR_recursive ( root );
	cout<<endl<<"=============="<<endl;
	cout<<"?è?ù±éàú(·?μY1é,???¨?ú)￡o"<<endl;
	traversal_DLR ( root );
	cout<<endl<<"=============="<<endl;
	cout<<"?D?ù±éàú(μY1é)￡o"<<endl;
	traversal_LDR_recursive ( root );
	cout<<endl<<"=============="<<endl;
	cout<<"?D?ù±éàú(·?μY1é￡????¨?ú)￡o"<<endl;
	traversal_LDR ( root );
	cout<<endl<<"=============="<<endl;
	cout<<"oó?ù±éàú(μY1é)￡o"<<endl;
	traversal_LRD_recursive ( root );
	cout<<endl<<"=============="<<endl;
	cout<<"oó?ù±éàú(·?μY1é￡????¨?ú)￡o"<<endl;
	traversal_LRD ( root );
	cout<<endl<<"=============="<<endl;
	return 0;
}