typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType* x)
{
	BTNode* NewNode = (BTNode*)malloc(sizeof(BTNode));
	assert(NewNode);
	NewNode->data = x;
	NewNode->left = NULL;
	NewNode->right = NULL;
	return NewNode;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

void Preorder(BTNode* root)
{
	if (root == NULL)
	{
		printf("* ");//空樹(shù)打印 * 
		return ;
	}
	printf("%d ", root->data);//先訪問(wèn) 根
	Preorder(root->left);//再訪問(wèn)左子樹(shù)
	Preorder(root->right);//最后訪問(wèn)右子樹(shù)
}

void Inorder(BTNode* root)//中序遍歷
{
	if (root == NULL)
	{
		printf("* ");//空樹(shù)打印 * 
		return;
	}
	Preorder(root->left);//先訪問(wèn)左子樹(shù)
	printf("%d ", root->data);//再訪問(wèn) 根
	Preorder(root->right);//最后訪問(wèn)右子樹(shù)
}
void Postorder(BTNode* root)//后序遍歷
{
	if (root == NULL)
	{
		printf("* ");//空樹(shù)打印 * 
		return;
	}
	Preorder(root->left);//先訪問(wèn)左子樹(shù)
	Preorder(root->right);//再訪問(wèn)右子樹(shù)
	printf("%d ", root->data);//最后訪問(wèn) 根
}

int size；
void TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	size++;//計(jì)數(shù)器
	TreeSize(root->left);//訪問(wèn)左子樹(shù)
	TreeSize(root->right);//訪問(wèn)右子樹(shù)
}
int main()
{
	BTNode* root = CreatBinaryTree();
	size = 0;
	TreeSize(root);
	printf("TreeSize = %d\n", size);
	return 0;
}

int TreeSize2(BTNode* root)
{
	if (root == NULL)//為NULL返回0
	{
		return 0;
	}
	return TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

int TreeLeafSize(BTNode* root)//求葉子節(jié)點(diǎn)
{
	if (root == NULL)//空樹(shù)返回0
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)//左子樹(shù)為空并且右子樹(shù)為空返回1
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeDepth(BTNode* root)
{
	if (root == NULL)//空樹(shù)返回0
	{
		return 0;
	}
	int Leftdepth = TreeDepth(root->left);//求出左邊高度
	int Rightdepth = TreeDepth(root->right);//求出右邊高度
	return Leftdepth > Rightdepth ? Leftdepth + 1 : Rightdepth + 1;//返回時(shí)加上自身返回
}

BTNode* TreeFind(BTNode* root, BTDataType x)//查找二叉樹(shù)中值為x的節(jié)點(diǎn)
{
	if (root == NULL)//為空返回空
	{
		return NULL;
	}
	if (root->data == x)//相等就返回節(jié)點(diǎn)
	{
		return root;
	}
	BTNode* RetLeft = TreeFind(root->left, x);//保存左節(jié)點(diǎn)值，方便直接返回
	if (RetLeft)
	{
		return RetLeft;
	}
	BTNode* RetRight = TreeFind(root->right, x);//保存右節(jié)點(diǎn)值，方便直接返回
	if (RetRight)
	{
		return RetRight;
	}
	return NULL;//都找不到返回NULL
}