数据结构(7)

#include
#include
#include
using namespace std;

typedef struct TreeNode* BinTree;
struct TreeNode
{
	int data;
	BinTree Left;
	BinTree Right;
};

//数据data范围0-9，为空用*代替，两位数没有处理
//先序建立二叉树
bool creatBinTree(BinTree &BT)
{
	printf("请输入当前节点数据n");
	char ch;
	scanf(" %c", &ch);
	if (ch == '*')
		BT = NULL;
	else
	{
		BT = (BinTree)malloc(sizeof(TreeNode));
		BT->data = ch - '0';
		creatBinTree(BT->Left);
		creatBinTree(BT->Right);
	}
	return true;
}


//先序遍历
void preOrder(BinTree BT)
{
	if (BT != NULL)
	{
		printf("%dn", BT->data);
		preOrder(BT->Left);
		preOrder(BT->Right);
	}
}
//中序遍历
void inOrder(BinTree BT)
{
	if (BT != NULL)
	{
		inOrder(BT->Left);
		printf("%dn", BT->data);
		inOrder(BT->Right);
	}
}
//后序遍历
void postOrder(BinTree BT)
{
	if (BT != NULL)
	{
		postOrder(BT->Left);
		postOrder(BT->Right);
		printf("%dn", BT->data);
	}
}


//中序遍历
void inOrder2(BinTree BT)
{
	stack S;
	BinTree p = BT;
	while (p!=NULL || !S.empty())
	{
		if (p != NULL)
		{
			S.push(p);
			p = p->Left;
		}
		else
		{
			p = S.top();
			S.pop();
			printf("%dn", p->data);
			p = p->Right;
		}
	}
}
//前序遍历
void preOrder2(BinTree BT)
{
	stack S;
	BinTree p = BT;
	while (p != NULL || !S.empty())
	{
		if (p != NULL)
		{
			printf("%dn", p->data);
			S.push(p);
			p = p->Left;
		}
		else
		{
			p = S.top();
			S.pop();
			
			p = p->Right;
		}
	}
}


//利用后序遍历求二叉树高度
//H=max[hL,hR]+1
int postOrderGetHeight(BinTree BT)
{
	int hL, hR, maxH;
	if (BT != NULL)
	{
		hL = postOrderGetHeight(BT->Left);
		hR = postOrderGetHeight(BT->Right);
		maxH = hL > hR ? hL : hR;
		return maxH + 1;
	}
	else
		return 0;
}


int main()
{
	BinTree BT;
	creatBinTree(BT);
	printf("递归遍历结果n");
	inOrder(BT);
	printf("非递归遍历结果n");
	inOrder2(BT);

	return 0;
}

//二叉搜索树 递归实现 查找指定元素所在结点地址
TreeNode* find(int elem, BinTree BT)
{
	if (BT == NULL)
		return NULL;
	if (elem > BT->data)
		return find(elem, BT->Right);
	else if (elem < BT->data)
		return find(elem, BT->Left);
	else
		return BT;
}
//非递实现
TreeNode* find2(int elem, BinTree BT)
{
	while (BT!=NULL)
	{
		if (elem > BT->data)
			BT = BT->Right;
		else if (elem < BT->data)
			BT = BT->Left;
		else
			return BT;
	}
	return NULL;
}