C++ 数据结构基础：树与二叉树的定义及代码实现

树与二叉树的核心概念

树是一种非线性的层次数据结构，由 n 个节点组成，具有明确的层次关系。理解树的结构需从以下几个关键定义入手：

1. 基础结构与节点属性

• 根节点：树中唯一的顶层节点，没有前驱（父节点），只有后继。
• 叶子节点：没有后继（子节点）的节点，即最外层节点，其度为 0。
• 节点的度：该节点拥有的子树（子节点）的数量。分支结点指度不为 0 的节点。
• 树的度：树中所有节点度的最大值。

2. 树的层级度量

树的“高度”与“深度”通常被视为同一维度的度量，但在具体语境中需注意区分：

• 树的高度/深度：指从根节点到最远叶子节点的路径长度或层数。例如，若某树的最远叶子位于第 4 层，则其高度和深度均为 4。

3. 二叉树及其分类

二叉树是每个节点最多只有两个子树（左子树和右子树）的树结构，具有五种基本形态（包括空树）。常见的特殊二叉树类型如下：

满二叉树与完全二叉树

• 满二叉树：高度为 h 且节点总数为 2^h - 1 的二叉树，每一层都充满节点。
• 完全二叉树：除最下面两层外，其余各层节点数均达到最大；最下层的叶子节点集中在左侧。

二叉查找树 (BST)

又称二叉搜索树，满足以下关键特性：

1. 若左子树不空，则左子树上所有节点的值均小于根节点的值。
2. 若右子树不空，则右子树上所有节点的值均大于根节点的值。
3. 左右子树也分别为二叉查找树。
4. 不存在键值相等的节点。

4. 二叉树的数学性质

在分析复杂度时，常涉及以下公式（设 i 为层数，k 为深度，n 为节点数）：

• 第 i 层最多有 2^(i-1) 个节点。
• 深度为 k 的二叉树至多有 2^k - 1 个节点。
• 包含 n 个节点的二叉树高度至少为 ⌊log₂n⌋ + 1。

C++ 代码实现：构建与遍历

以下代码演示如何在 C++ 中通过类封装树的结构，并实现手动构造特定二叉树、前序遍历、统计叶子节点、获取树深度及总节点数的功能。

第 1 步：定义树结构

使用结构体 MyTree 表示节点，包含数据域和左右指针。外部类 Tree 提供操作方法。

#pragma once
typedef struct MYTREE {
	char data;
	struct MYTREE* lChild;
	struct MYTREE* rChild;
}MyTree;
class Tree
{
public:
	Tree();
	~Tree();
	void CreateTree();
	void TraverseTree(MyTree *root);
	void GetLeafNode(MyTree *root,int &num);
	int GetTreeDepth(MyTree *root);
	void GetTreeNode(MyTree *root, int &num);
};

第 2 步：实现树的构建与核心算法

在 Tree.cpp 中，首先通过硬编码指针连接的方式初始化一个特定的树结构，随后执行遍历与统计操作。注意：GetTreeDepth 采用递归方式返回左右子树深度的较大值加 1。

#include "Tree.h"
#include <iostream>
#include<algorithm>//max,min
using namespace std;

Tree::Tree(){}
Tree::~Tree(){}

void Tree::CreateTree()
{
	// 初始化各个节点
	MyTree t1 = {'A',nullptr,nullptr};
	MyTree t2 = { 'B',nullptr,nullptr };
	MyTree t3 = { 'C',nullptr,nullptr };
	MyTree t4 = { 'D',nullptr,nullptr };
	MyTree t5 = { 'E',nullptr,nullptr };
	MyTree t6 = { 'F',nullptr,nullptr };
	MyTree t7 = { 'G',nullptr,nullptr };
	MyTree t8 = { 'H',nullptr,nullptr };
	
	// 建立父子关系
	t1.lChild = &t2;   t1.rChild = &t6;
	t2.rChild = &t3;
	t3.lChild = &t4;   t3.rChild = &t5;
	t6.rChild = &t7;
	t7.lChild = &t8;
	
	// 执行操作
	TraverseTree(&t1); // 前序遍历输出
	cout << endl;
	
	int leafNum = 0;
	GetLeafNode(&t1,leafNum);
	cout << "leaf num: " << leafNum << endl;
	
	int treeDepth = GetTreeDepth(&t1);
	cout << "depth:" << treeDepth << endl;
	
	int nodeNum = 0;
	GetTreeNode(&t1,nodeNum);
	cout << "node num; " << nodeNum << endl;
}

// 前序遍历：左 -> 根 -> 右
void Tree::TraverseTree(MyTree *root)
{
	if (root == nullptr) return;
	TraverseTree(root->lChild);
	cout << root->data;
	TraverseTree(root->rChild);
}

// 统计叶子节点数
void Tree::GetLeafNode(MyTree *root,int &num)
{
	if (root == nullptr) return;
	if (root->lChild == nullptr && root->rChild == nullptr)
	{
		num++;
	}
	GetLeafNode(root->lChild,num);
	GetLeafNode(root->rChild,num);
}

// 获取树深度（高度）
int Tree::GetTreeDepth(MyTree * root)
{
	if (root == nullptr) return 0;
	int lNum = GetTreeDepth(root->lChild);
	int rNum = GetTreeDepth(root->rChild);
	return max(lNum,rNum)+1;
}

// 统计总结点数
void Tree::GetTreeNode(MyTree * root, int & num)
{
	if (root == nullptr) return;
	++num;
	GetTreeNode(root->lChild,num);
	GetTreeNode(root->rChild,num);
}

第 3 步：程序入口与运行验证

主函数调用测试类即可在控制台查看结果。开发环境建议为支持 C++11 标准的编译器（如 Visual Studio 2017+）。

#include <iostream>
#include "Tree.h"
using namespace std;

void test() {
	Tree t;
	t.CreateTree();
}

int main()
{
	test();
	return 0;
}

运行结果说明

上述代码构建的树结构中，叶子节点为 D、E、H、I（根据指针关联逻辑），最终输出的统计信息如下：

• 遍历序列：按前序（根左右）输出字符序列。
• Leaf Num：统计出的叶子节点数量。
• Depth：树的垂直高度。
• Node Num：树中节点的总数。

以上就是C++关于树的定义全面梳理及代码实现的详细内容，更多关于C++数据结构树操作的资料请关注本站其它相关文章！