/*	_递归的精髓在二叉树的各种问题上体现的淋漓尽致！！！*/#include<stdio.h>#include<iostream>#include <stack>#include<vector>#include <assert.h>using namespace std;typedef struct node				//二叉树结点的结构体表示形式{	int data;	node *left,*right;}BTree;//---------------------------------_创建二叉树（前序方式）---------------------------BTree *Create(){	int data;	scanf("%d",&data);	if(data=http://www.mamicode.com/=0)	return 0;		//_输入0表示没有子节点"%d  ",tree->data);	Preorder(tree->left);	Preorder(tree->right);}void Preorder2(BTree *tree)		//堆栈方式{	if(tree==0)	return;	stack <BTree*> s;	s.push(tree);	BTree *temp=0;	while(!s.empty())	{		temp=s.top();		printf("%d ",temp->data);		s.pop();		if(temp->right)	s.push(temp->right);		if(temp->left)	s.push(temp->left);	}}//-------------_遍历二叉树（中序方式）-------------void Inorder(BTree *tree){	if(tree==0)	return;	Inorder(tree->left);	printf("%d  ",tree->data);	Inorder(tree->right);}void Inorder2(BTree *tree){	if(tree==0)	return;	stack<BTree *> s;	BTree *temp=0;	s.push(tree);	while(!s.empty())	{		temp=s.top();s.pop();		//_弹出节点		while(temp)					//_至最左端		{			s.push(temp);			temp=temp->left;		}		if(!s.empty())		{			temp=s.top();s.pop();		//_取出最左端节点			printf("%d ",temp->data);			s.push(temp->right);		//_存入最左端节点的右兄弟,必须要压入右边的，无论有无节点		}	}}//-------------_遍历二叉树（后序方式）-------------void Posorder(BTree *tree){	if(tree==0)	{return;}	Posorder(tree->left);	Posorder(tree->right);	printf("%d  ",tree->data);}void Posorder2(BTree *tree){	if(!tree)	return;	stack<BTree *> s;	BTree *temp=0,*lastvisit=0;	s.push(tree);	while(!s.empty())	{		temp=s.top();		s.pop();		while(temp)		{			s.push(temp);			temp=temp->left;		}		temp=s.top();		if(temp->right&&(temp->right!=lastvisit))		{			s.push(temp->right);		}		else		{			lastvisit=temp;			printf("%d ",lastvisit->data);			s.pop();		}	}}//-------------------------------------_二叉树的镜像--------------------------------void GetImage(BTree *tree)					//_求二叉树镜像{	if(tree==0)	return;	GetImage(tree->left);	GetImage(tree->right);	//互换left_和right	BTree *tmp=tree->left;tree->left =tree->right;tree->right=tmp;}bool IsImage(BTree *tree1,BTree *tree2)		//_判断二叉树是否是镜像的{	if(tree1==0&&tree2==0)	return true;	if(!tree1||!tree2)		return false;	if(tree1->data!=tree2->data)	return false;	bool same1=IsImage(tree1->left,tree2->right);	bool same2=IsImage(tree1->right,tree2->left);	return same1&&same2;}//--------------------------------------_与路径相关的问题---------------------------BTree * findnode(BTree *tree ,int key)												//_寻找key为某个值的节点,没找到返回0{	if(!tree)	return 0;	if(tree->data=http://www.mamicode.com/=key)	return tree;"前序遍历：");Preorder(tree);printf("\n");	//GetImage(tree);	//printf("前序遍历：");Preorder(tree);printf("\n");	//printf("中序遍历：");Inorder2(tree);printf("\n");	//printf("后序遍历：");Posorder(tree);printf("\n");/* 测试：从根节点到某一节点的路径	BTree *node;findnode1(tree,7,node);	stack<BTree *> st;	findpath(tree,node,st);	while(!st.empty())	{		cout<<st.top()->data<<" ";st.pop();	}** 测试：和为某一值的路径	int currentSum=0;vector<BTree *> v;	findsumpath(tree,10,currentSum,v);** 测试：_最近公共父节点	BTree *A,*B,*C;findnode1(tree,4,A);findnode1(tree,2,B);	C=LowestCommonAncestor(tree,A,B);	cout<<C->data<<endl;** 测试：_树的深度	cout<<depth(tree)<<endl;	return;** 测试：_输出树的某一层	levelnum(tree,4,1);*/	}