二叉树遍历.cpp

遍历二叉树 是指以一定的次序访问二叉树中的每个结点

#include<iostream>
using namespace std;
int c, k;

struct tree    // 声明树的结构
{
	struct tree *left;
	int data;
	struct tree *right;
};

typedef struct tree treenode;  // 声明新类型树结构
typedef treenode *b_tree;


//-----------------------------------------------
//                插入二叉树的节点
//-----------------------------------------------
b_tree insert_node( b_tree root, int node )
{
	b_tree newnode;    // 声明树根指针
	b_tree currentnode;
	b_tree parentnode;

	newnode = (b_tree) malloc (sizeof(treenode)); // 建立新节点的内存空间

	newnode->data = node;   // 存入节点内容
	newnode->right = NULL;  // 设置右指针初值
	newnode->left = NULL;   // 设置左指针初值

	if ( root == NULL )
		return newnode; // 返回新节点的位置
	else
	{
		currentnode = root; // 存储目前节点指针
		while ( currentnode != NULL )
		{
			parentnode = currentnode;  // 存储父节点指针
			if ( currentnode->data > node )
				currentnode = currentnode->left;  // 左子树
			else 
                currentnode = currentnode->right;  // 右子树
		}
		if ( parentnode->data > node )
			parentnode->left = newnode;  // 子节点为父节点的左子树
		else 
            parentnode->right = newnode;  // 子节点为父节点的右子树
	}
	return root;
}


//------------------------------------------------
//                 建立二叉树
//------------------------------------------------
b_tree create_btree( int *data, int len)
{
	b_tree root = NULL;  //根节点指针

	for ( int i = 0; i < len; i++)
	    root = insert_node( root, data[ i ] );
	return root;
}

//-----------------------------------------------
//                二叉树前序遍历
//-----------------------------------------------
void preorder( b_tree point )
{
	if ( point != NULL)
	{
		cout << point->data << "  ";
		preorder( point->left );
		preorder( point->right );
	}
}

//-----------------------------------------------
//                二叉树中序遍历
//-----------------------------------------------
void inorder( b_tree point )
{
	if ( point != NULL)
	{
		
		inorder( point->left );
		cout << point->data << "  ";
		inorder( point->right );
	}
}


//-----------------------------------------------
//                二叉树后序遍历
//-----------------------------------------------
void postorder( b_tree point )
{
	if ( point != NULL)
	{
		
		postorder( point->left );
        postorder( point->right );
		cout << point->data << "  ";
		
	}
}

//-------------------------------------------------
//  在二叉树中求位于先序序列中第k个位置节点的值
//-------------------------------------------------
void Get_PreSeq( b_tree point )
{
	if ( point )
	{
		c++;
		if ( c == k )
		{
			cout <<"The value is " << point->data << endl;
			exit(1);
		}
		else
		{
			Get_PreSeq( point->left ); // 在左子树中查找
            Get_PreSeq( point->right ); // 在右子树中查找
		}
	}
}

//-------------------------------------------------
//         计算二叉树中叶子节点的数目
//-------------------------------------------------
int LeafCout_btree( b_tree point)
{
	if ( !point )  // 空数没有叶子  
		return 0;
	else if( !point->left && !point->right) 
		return 1;
	else
		return  LeafCout_btree( point->left) + LeafCout_btree( point->right);  //左子树的叶子数加上右子树的叶子数 
}

//-------------------------------------------------
//     交换二叉树中所有结点的左右子树
//-------------------------------------------------
void Bitree_Revolute( b_tree point )
{
	b_tree temp;

	temp = point->letf;
	poin->left = point->right;
	point->right = temp;

	if ( point->left )  
        Bitree_Revolute( point->left);
	if ( point->right )
		Bitree_Revolute( point->right);
}

//-------------------------------------------------
//                      主程序
//-------------------------------------------------
int main()
{
	b_tree root = NULL;
	int index = 0;
	int value;            //  读入输入值所使用的暂存变量
	int nodelist[ 20 ];   //  声明存储输入数据的数组
	
	cout << "\n please input the elemnts of binary tree(Exit for 0)" << endl;
    
	cin >> value;

	while ( value != 0 )
	{
         nodelist[ index++ ] = value;
		 cin >> value;
	}

	root = create_btree( nodelist, index);   // 建立二叉树
	 
	cout << "The preorder traverasal result is  :";
	preorder( root );

	cout << "\nThe inorder traverasal result is   :";
	inorder( root );

	cout << "\nThe postorder traverasal result is :";
	postorder( root );
	cout << endl;
    
	  
	c = LeafCout_btree( root );
	cout << "叶子结点的数目为: " << c << endl;

	Bitree_Revolute( root);  // 交换左右子树
	cout <<"左右子树交换后的遍历结果为: " << endl;
    cout << "The preorder traverasal result is  :";
	preorder( root );

	cout << "\nThe inorder traverasal result is   :";
	inorder( root );

	cout << "\nThe postorder traverasal result is :";
	postorder( root );
	cout << endl;


	c = 0;
	cout << "请输入在二叉树中位于先序序列中的第k个位置: ";
	cin >> k;
	Get_PreSeq( root );



}