C++实现二叉树数据结构笔记与代码

“数据结构（C++）上课笔记——二叉树的C++实现(2020-5-11) .doc” 这篇文档详细介绍了如何在C++中实现二叉树的数据结构，主要关注二叉链表的类定义以及相关操作。二叉树是一种非线性的数据结构，由节点组成，每个节点最多有两个子节点，通常称为左子节点和右子节点。 首先，文档定义了一个模板类`BinTreeNode`，用于表示二叉树的节点。这个类包含三个成员： 1. `T data`：数据域，存储节点的数据，使用模板参数`T`，可以是任何类型。 2. `BinTreeNode<T>* leftChild`：指向左子节点的指针。 3. `BinTreeNode<T>* rightChild`：指向右子节点的指针。 类`BinTreeNode`还包含了两个构造函数： - 默认构造函数初始化左右子节点指针为`NULL`。 - 带参数的构造函数允许初始化节点的数据、左子节点和右子节点。 接着，文档定义了另一个模板类`BinaryTree`，代表整个二叉树。它有一个私有成员`BinTreeNode* root`，表示树的根节点。`BinaryTree`类提供了以下公共方法： 1. 构造函数：用于创建一个二叉树，可以指定根节点及其左右子树。 2. `int Height()`：计算树的高度，即最长路径上的节点数量。 3. `int Size()`：返回树中节点的总数。 4. `bool IsEmpty()`：检查树是否为空。 5. `BinTreeNode<T>* Parent(BinTreeNode<T> *current)`：返回指定节点的父节点。 6. `BinTreeNode<T>* LeftChild(BinTreeNode<T> *current)`：返回指定节点的左子节点。 7. `BinTreeNode<T>* RightChild(BinTreeNode<T> *current)`：返回指定节点的右子节点。 8. `bool Insert(T item)`：向树中插入新的元素。 9. `bool Remove(T item)`：从树中删除指定元素。 10. `bool Find(const T& item)const`：查找元素是否存在。 11. `bool getData(const T& item)const`：获取指定元素的节点数据。 12. `BinTreeNode<T>* getRoot()const`：获取树的根节点。 13. `void preOrder(void(*visit)(BinTreeNode<T>*p))`：前序遍历，先访问根节点，然后左子树，最后右子树，`visit`是用户提供的访问函数。 14. `void inOrder(void(*visit)(BinTreeNode<T>*p))`：中序遍历，先左子树，然后访问根节点，最后右子树。 这些方法覆盖了对二叉树的基本操作，包括创建、查询、修改和遍历。通过这些方法，开发者可以方便地在C++中构建和操作二叉树数据结构，用于各种算法和问题解决。这份上课笔记和调试成功的代码是学习和复习二叉树概念的宝贵资料，对于提高编程技能和理解数据结构原理非常有帮助。