数据结构：树与二叉树_二叉树_二叉树的基本操作_二叉树链式存储初始化根结点为什么不用指针-CSDN博客

本文链接：https://blog.csdn.net/uxiaolang/article/details/46458721

本文介绍了二叉树的两种主要存储方式：顺序存储结构和二叉链表，并提供了二叉树节点创建、连接及打印等基本操作的实现示例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

二叉树的存储结构

1.顺序存储结构

用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点直接的逻辑关系。顺序存储结构适合存储完全二叉树，而存储普通的二叉树空间利用率较低。

2.二叉链表

由于顺序存储结构的适用性不强，考虑使用链式存储结构。二叉树每个节点最多有两个孩子，设计一个数据域和两个指针域。这样的链表称为二叉链表。

二叉树的基本操作

struct BinaryTreeNode
{
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
};

<pre name="code" class="cpp">//创建二叉树节点
BinaryTreeNode* createBinaryTreeNode(int value)
{
	BinaryTreeNode* bNode=new BinaryTreeNode();
	if(bNode=NULL)
		return NULL;
	bNode->m_nValue=value;
	bNode->m_pLeft=bNode->m_pRight=NULL;
	return bNode;
}

//连接二叉树节点
void connectTreeNodes(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight)
{
	if(pParent!=NULL)
	{
		pParent->m_pLeft=pLeft;
		pParent->m_pRight=pRight;
	}
}

//打印二叉树节点
void printTreeNode(BinaryTreeNode* pNode)
{
	if(pNode!=NULL)
	{
		cout<<"节点为: "<<pNode->m_nValue<<endl;
	    if(pNode->m_pLeft != NULL)
            cout<<"左孩子为: "<<pNode->m_pLeft->m_nValue<<endl;
        else
            cout<<"左孩子为空"<<endl;
        if(pNode->m_pRight != NULL)
            cout<<"右孩子为: "<<pNode->m_pRight->m_nValue<<endl;
        else
            cout<<"右孩子为空 null"<<endl;
	}
}

//打印二叉树(前序遍历)
void printTree(BinaryTreeNode* pRoot)
{
	printTreeNode(pRoot);
	if(pRoot!=NULL)
	{
		if(pRoot->m_pLeft!=NULL)
			printTree(pRoot->m_pLeft);
		if(pRoot->m_pRight!=NULL)
			printTree(pRoot->m_pRight);
	}
}

//销毁二叉树
void DestroyTree(BinaryTreeNode* pRoot)
{
	if(pRoot!=NULL)
	{
		BinaryTreeNode* pLeft=pRoot->m_pLeft;
		BinaryTreeNode* pRight=pRoot->m_pRight;
		delete pRoot;
		pRoot=NULL;
        DestroyTree(pLeft);
		DestroyTree(pRight);
	}
}