二叉树最小结构(C++版本)

二叉树节点类型为ListNode

struct BinaryTreeNode
{
	BinaryTreeNode(int newData) : data(newData), pLeft(nullptr), pRight(nullptr) {}

	int data;
	BinaryTreeNode* pLeft;
	BinaryTreeNode* pRight;
};

二叉树类型为MyBinaryTree

struct MyBinaryTree
{
	MyBinaryTree() : pRoot(nullptr) {}
	BinaryTreeNode* pRoot;
};

涉及的操作为：

• 插入二叉树

void InsertBinaryTree(BinaryTreeNode* pCurNode, BinaryTreeNode* pNewNode)
{
	if (pNewNode->data <= pCurNode->data)
	{
		if (nullptr == pCurNode->pLeft)
		{
			pCurNode->pLeft = pNewNode;
			return;
		}

		InsertBinaryTree(pCurNode->pLeft, pNewNode);
	}
	else
	{
		if (nullptr == pCurNode->pRight)
		{
			pCurNode->pRight = pNewNode;
			return;
		}

		InsertBinaryTree(pCurNode->pRight, pNewNode);
	}
}

void InsertBinaryTree(MyBinaryTree& binTree, int newData)
{
	BinaryTreeNode* pNewNode = new BinaryTreeNode(newData);

	if (nullptr == binTree.pRoot)
	{
		binTree.pRoot = pNewNode;
		return;
	}

	BinaryTreeNode* pCurNode = binTree.pRoot;
	InsertBinaryTree(pCurNode, pNewNode);
}

• 遍历二叉树

void PreOrderTraverse(BinaryTreeNode* pCurNode)
{
	if (nullptr == pCurNode) return;
	std::cout << pCurNode->data << " ";
	PreOrderTraverse(pCurNode->pLeft);
	PreOrderTraverse(pCurNode->pRight);
}

void InOrderTraverse(BinaryTreeNode* pCurNode)
{
	if (nullptr == pCurNode) return;
	InOrderTraverse(pCurNode->pLeft);
	std::cout << pCurNode->data << " ";
	InOrderTraverse(pCurNode->pRight);
}

void PostOrderTraverse(BinaryTreeNode* pCurNode)
{
	if (nullptr == pCurNode) return;
	PostOrderTraverse(pCurNode->pLeft);
	PostOrderTraverse(pCurNode->pRight);
	std::cout << pCurNode->data << " ";
}

void PreOrderTraverse(MyBinaryTree& binTree)
{
	PreOrderTraverse(binTree.pRoot);
}

void InOrderTraverse(MyBinaryTree& binTree)
{
	InOrderTraverse(binTree.pRoot);
}

void PostOrderTraverse(MyBinaryTree& binTree)
{
	PostOrderTraverse(binTree.pRoot);
}