C语言数据结构--二叉树​

typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一个孩子结点
    struct Node* _pNextBrother;   // 指向其下一个兄弟结点
    DataType _data;               // 结点中的数据域
};

// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* pLeft;   // 指向当前节点左孩子
    struct BinTreeNode* pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域

}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* pParent; // 指向当前节点的双亲
    struct BinTreeNode* pLeft;   // 指向当前节点左孩子
    struct BinTreeNode* pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
//前序  (根 左子树 右子树)   采用递归方法实现遍历
void PreOrder(BTNode *root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ",root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}

//中序  (左子树 根 右子树)  
void InOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->_left);
	printf("%c ",root->_data);
	InOrder(root->_right);

}

//后序  (左子树 右子树 根)  
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%c ", root->_data);

}
//层序



//求节点的个数三种方法
//int size = 0;
//int TreeSize(BTNode* root)
//{
//	if (root==NULL)
//	{
//		return 0;
//	}
//	++size;
//	TreeSize(root->_left);
//	TreeSize(root->_right);
//	return size;
//}

// 用指针，规避size累加，很miao
//void  TreeSize(BTNode* root,int *psize)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	else
//	{
//		(*psize)++;
//	}
//	TreeSize(root->_left, psize);
//	TreeSize(root->_right, psize);
//}


int  TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		return 1 + TreeSize(root->_left) + TreeSize(root->_right);
	}
}


//求叶子的节点
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if(root->_left==NULL&&root->_right==NULL)
	{
		return 1;
	}

	//A的叶子数等于左子树的叶子数+右子树的叶子数
	return TreeLeafSize(root->_left)+TreeLeafSize(root->_right);
}


BTNode* CreateNode(int x)
{
	BTNode* node =(BTNode*) malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
	return node;
}

//求第k层节点的个数

int BinaryLeveIKsize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryLeveIKsize(root->_left, k - 1)
		+ BinaryLeveIKsize(root->_right, k - 1);
}

//查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	//根
	if (root->_data == x)
	{
		return root;
	}
	//左，找不到再找右
	BTNode* node = BinaryTreeFind(root->_left,x);
	if (node)
	{
		return node;
	}
	//右，找到返回
	node = BinaryTreeFind(root->_right, x);
	if (node)
	{
		return node;
	}
	return NULL;
}
//销毁一棵树(后序方式)
void DestoryTree(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	DestoryTree(root->_left);
	DestoryTree(root->_right);
	free(root);
}

//层序遍历
/*
* 1.根先进队列
* 2.迭代，，队列不为空。出队头数据，同时把对应节点的左右孩子带进去
* 3.直到队列为空，结束
*/
void BinaryTreeLeveOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
	{
		return;
	}
	QueuePush(&q,root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}

		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
	printf("\n");
}

//判断一棵树是不是完全二叉树
//是返回1 
int BinayTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
	{
		return 1;
	}
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}

		QueuePush(&q,front->_left);
		QueuePush(&q,front->_right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return 0;
		}
	}
	return 1;
}


int main()
{
	BTNode* A = CreateNode('A');
	BTNode* B = CreateNode('B');
	BTNode* C = CreateNode('C');
	BTNode* D = CreateNode('D');
	BTNode* E = CreateNode('E');
	A->_left = B;
	A->_right = C;
	B->_left = D;
	B->_right = E;
	PreOrder(A);
	printf("\n");
	InOrder(A);
	printf("\n");
	PostOrder(A);

	/*int sizeA = 0;
	TreeSize(A, &sizeA);
	printf("\nTree Size is:%d \n", sizeA);*/



	printf("\nTree Size is:%d \n", TreeSize(A));


	printf("\nTree Leaf Size is:%d \n", TreeLeafSize(A));

	BinaryTreeLeveOrder(A);

	return 0;
}