手把手教你实现二叉树:从代码注释到实战应用

深度学习
• 阅读 3

一、简介和应用

二叉树是一种经典的数据结构,它由节点组成,每个节点最多有两个子节点(左子节点和右子节点)。这种结构因其简洁性和高效性被广泛应用于算法设计、数据存储与检索等领域。例如,文件系统目录结构、搜索算法(如二叉搜索树)以及表达式解析树等场景都离不开二叉树。对于编程新手来说,理解二叉树的基本原理和实现方式,是掌握数据结构与算法的重要一步。

二、特点和注意事项

  1. 特点:

    二叉树通过分层结构组织数据,支持快速插入、查找和删除操作。

    遍历方式多样(前序、中序、后序),便于不同场景的数据处理。

    递归实现简洁,但需注意递归深度以避免溢出。

  2. 注意事项:

    需确保树的平衡性(如通过平衡树算法),避免因节点分布不均导致性能下降。

    删除节点时需处理子节点指针,防止内存泄漏或指针悬空。

    理解递归逻辑,避免因递归调用层次过多导致程序崩溃。

三、实现步骤

  1. 定义节点结构:使用 treenode 结构体存储数据、左右子节点指针。

  2. 构建树类:通过 tree 类封装树的操作,初始化根节点。

  3. 添加节点:

    add(parent, children, data):指定父节点及子节点位置(左/右)添加新节点。

    add(node, data):递归查找空子节点位置插入。

  4. 删除节点:通过 remove(parent, children) 指定父节点和子节点位置(左/右)删除。

  5. 数据修改与查找:

    change(node, data):直接修改节点数据。

    find(data, root):递归遍历查找目标数据节点。

  6. 遍历方法:实现前序、中序、后序三种递归遍历方式,输出节点数据。

四、代码与注释

#include <iostream>
using namespace std;

// 定义二叉树节点结构体
struct treenode {
// 节点数据
int data = 0;
// 左右子节点指针
treenode* left = nullptr;
treenode* right = nullptr;

// 默认构造函数
treenode() {}

// 带参数构造函数(用于指定父节点和位置添加子节点)
treenode(int d, treenode* h, bool children) {
data = d; // 设置数据
if (!children) // 如果为左子节点
h->left = this; // 将当前节点挂载到父节点左侧
else // 如果为右子节点
h->right = this; // 挂载到右侧
}

// 仅数据初始化的构造函数
treenode(int d) {
data = d;
}
};

class tree {
public:
treenode* root; // 根节点指针

// 树构造函数,初始化根节点
tree() {
root = new treenode; // 创建根节点
}

// 在指定父节点添加子节点(左/右)
void add(treenode* parent, bool children, int data) {
treenode* newnode = new treenode(data, parent, children);
}

// 递归查找空位置添加节点
void add(treenode* node, int data) {
if (!node->left) { // 若左子节点为空
node->left = new treenode(data); // 添加左节点
return;
}
if (!node->right) { // 若右子节点为空
node->right = new treenode(data); // 添加右节点
return;
}
add(node->left, data); // 递归查找左子树
add(node->right, data); // 递归查找右子树
}

// 删除指定父节点的左/右子节点
void remove(treenode* parent, bool children) {
if (!children) // 删除左子节点
parent->left = nullptr;
else // 删除右子节点
parent->right = nullptr;
}

// 修改节点数据
void change(treenode* node, int data) {
node->data = data;
}

// 递归查找数据节点
treenode* find(int data, treenode* root) {
if (!root) // 若节点为空,终止递归
return nullptr;
if (root->data == data) // 找到目标数据
return root;
treenode* ret;
ret = find(data, root->left); // 递归查找左子树
if (ret) return ret; // 若找到,直接返回
ret = find(data, root->right); // 递归查找右子树
if (ret) return ret;
return nullptr; // 未找到,返回空
}

// 前序遍历(根-左-右)
void printpre(treenode* node) {
if (!node) return;
cout << node->data << " ";
printpre(node->left);
printpre(node->right);
}

// 中序遍历(左-根-右)
void printmid(treenode* node) {
if (!node) return;
printmid(node->left);
cout << node->data << " ";
printmid(node->right);
}

// 后序遍历(左-右-根)
void printpost(treenode* node) {
if (!node) return;
printpost(node->left);
printpost(node->right);
cout << node->data << " ";
}
};

五、总结

通过本文的代码示例,新手可以直观理解二叉树的基本实现逻辑:从节点定义到树操作封装,再到递归遍历与数据管理。掌握这些基础后,可进一步探索更复杂的树结构(如平衡树、堆等)。建议实践时逐步调试,观察节点连接关系,加深对递归逻辑的理解。记住:数据结构是算法的基石,扎实的基础能大幅提升编程能力!

来源: 手把手教你实现二叉树:从代码注释到实战应用(新手友好版)

点赞
收藏
评论区
推荐文章
白茶清欢 白茶清欢
4年前
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树.....不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。你将会获得:1.如何使用js实现二叉查找树。2.学会前、中、后序遍历。3.了解相关实现原理阅读时长5min,可选择直接调试代码特点    二叉查找树中序遍历后
似梦清欢 似梦清欢
2年前
树与二叉树
二叉树层次建树二叉树(BinaryTree)是由有限个结点组成的集合,它或者为空集合,或者仅含一个根结点,或者由一个根结点和两棵互不相交的左、右子树组成。树为空即根节点为空。二叉树的基本形态如下图:a:空的二叉树,treeNULL。b:只有空节点的二叉树,
Wesley13 Wesley13
3年前
B树与B+树的区别?
1.B树简介B树是一种多路平衡搜索树。它由二叉树变换而来的。定义如下:1.1每个节点最多有m1个关键字1.2根节点最少有1个关键字1.3非根节点至少有m/2个关键字1.4每个节点的关键字都是按照从小到大的顺序排列,每个关键字的左子树中的关键字都小于它,而右子树中所有关键字都大于它。1.5所有的叶子节点都处于同
Wesley13 Wesley13
3年前
JAVA递归实现线索化二叉树
JAVA递归实现线索化二叉树基础理论首先,二叉树递归遍历分为先序遍历、中序遍历和后序遍历。先序遍历为:根节点左子树右子树中序遍历为:左子树根节点右子树后序遍历为:左子树右子树根节点(只要记住根节点在哪里就是什么遍历,且都是先左再右)线索化现在有这么一棵二叉树,它的数据结
Wesley13 Wesley13
3年前
PHP数据结构与算法:二叉树
一、定义二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)。二、特性1.在二叉树的第i层上至多有2^(i1)个结点(i0)2.深度为k的二叉树至多有2^k1个结点(k0)3.对于任意一棵二叉树,如果其叶结点数为N0,而
Wesley13 Wesley13
3年前
B
BTreeBTree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对23查找树的一种扩展。一个m阶的BTree有以下性质1.每个节点最多有m个子节点;2.每个非叶子节点(根节点除外)至少含有m/2个子节点;3.
菜园前端 菜园前端
2年前
什么是二叉树?
原文链接:什么是二叉树?树中每个节点最多只能有两个子节点,在JavaScript中一般都是通过Object来模拟二叉树。常用操作前序遍历中序遍历后序遍历前序遍历根左右。口诀:1.访问根节点2.对根节点的左子树进行前序遍历3.对根节点的右子树进行前序遍历通过
贾蔷 贾蔷
1星期前
二叉树入门指南:从零开始理解树形数据结构
一、简介和应用二叉树是一种重要的非线性数据结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。它在计算机科学中有广泛的应用,是许多高级数据结构的基础。‌应用场景‌:1.数据库索引(如B树、B树)2.文件系统目录结构3.表达式树(用于编译器实现)4
贾蔷 贾蔷
1星期前
手搓二叉树构建类代码详解:从入门到实践(适合新手小白)
一、简介和应用二叉树是数据结构中常见的一种树形结构,每个节点最多有两个子节点(左子节点和右子节点)。它广泛应用于算法设计、数据存储与搜索(如二叉搜索树)、表达式解析等领域。本文将通过手写的C代码,讲解如何构建一个基础的二叉树类,帮助新手理解其原理与实现
深度学习 深度学习
4小时前
头插法实现的树结构:链表式多叉树实现指南
一、简介和特点头插法实现的树是一种使用子节点的多叉。本文实现的树类通过链表头插法高效管理子节点关系,适合需要频繁插入子节点的场景。‌主要特点‌:1.动态子节点管理:使用链表存储子节点1.高效插入:头插法实现O(1)的子节点插入1.泛型支持:模板类设计支持多