C++二叉树以及相关遍历的实现

该程序实现了一个二叉树（btree）类，支持节点的创建、删除以及前序、中序、后序遍历查找功能。以下是对各功能模块及其算法的详细分析：

---

​1. 节点结构（node 结构体）​

• ​功能：
  • 存储节点数据 data。
  • 维护父子关系：pre 指向父节点，child1 和 child2 是两个子节点的 unique_ptr。
  • 使用 isalive 标志表示节点是否有效（删除操作通过标记而非物理删除）。
• ​实现特点：
  • 使用 unique_ptr 自动管理子节点内存，避免内存泄漏。
  • 通过 isalive 实现逻辑删除，保留树结构但标记节点为“无效”。

    struct node {node* pre;//指向父节点的指针bool isalive = false;//标识符，如果为true代表节点在树中还存在T data;std::unique_ptr<node> child1;//它的类型是std::unique_ptr<node>，是一个模板类的实例对象。该对象内部封装了一个原生指针（node*），指向动态分配的node类型对象。等效于：node* raw_child1;std::unique_ptr<node> child2;//node构造函数，父指针指向父节点，数据，子节点为空初始化node(node* parent, T val) : pre(parent), data(val), child1(nullptr), child2(nullptr) {}
    };std::unique_ptr<node> head;//根节点
    node* temp = nullptr;//指向最先要删除或者最先创建子节点的指针
    std::deque<node*> que;//队列，实现层级遍历构造

---

​2. 创建节点（createNode）​

• ​功能：按层级顺序插入节点，构建完全二叉树。
• ​算法：
  • ​广度优先插入：使用队列 que 维护待插入子节点的父节点。
    1. 若树为空，创建根节点并加入队列。
    2. 非空时，从队列头部取出父节点 temp，优先填充左子节点（child1），再填充右子节点（child2）。
    3. 新节点加入队列尾部，成为后续插入的父节点。
    4. 当父节点的两个子节点均填满后，将其移出队列。

       void createNode(T data) {if (!head) {head = std::make_unique<node>(nullptr, data);//动态创建根节点head->isalive = true;temp = head.get();//head中的原始指针传给temp，实际就是temp=head指向的对象que.push_back(temp);//将对象从尾部插入到队列中，因为是根节点，进去以后就是队首return;}if (que.empty()) {std::cout << "无法插入新节点，树已满或队列异常" << std::endl;return;}auto newNode = std::make_unique<node>(temp, data);newNode->isalive = true;if (!temp->child1) {temp->child1 = std::move(newNode);//移动构造，也称动态构造，因为newNode是临时变量，他创建的像保存下来就要new出来挂到树上，不然newNode没了对象也没了导致指向他的指针悬空lsqueue(temp->child1.get());}else if (!temp->child2) {temp->child2 = std::move(newNode);lsqueue(temp->child2.get());//temp的child2的原始指针（node*）que.pop_front();//父界节点的child2指向了一个节点，不能再创建节点了，把父节点从队列弹出if (!que.empty()) {temp = que.front();//更新temp}}
       }
       

• ​示例：
  • 插入顺序 60, 26, 29, 28, 95, 21 生成的树结构如下：

        60/  \26   29/  \  /
    28 95 21

---

​3. 删除节点（deleteNode）​

• ​功能：删除最近插入的节点（队列末尾节点），维护树结构。
• ​算法：
  1. 从队列末尾取出待删除节点 toDelete，标记 isalive = false。
  2. 解除父节点对 toDelete 的引用：
     • 若 toDelete 是左子节点，重置父节点的 child1。
     • 若为右子节点，重置 child2。
  3. 若父节点删除后无子节点，将其重新加入队列头部，允许后续插入。
• ​特点：
  • 删除操作基于队列的 LIFO 顺序（删除最后插入的节点）。
  • 物理删除通过 unique_ptr::reset() 自动释放内存。

    //删除节点
    void deleteNode() {if (que.empty()) {std::cout << "队列为空" << std::endl;return;}node* toDelete = que.back();que.pop_back();//把这个节点的指针从队列pop出来toDelete->isalive = false;//如果被删除的节点有父对象if (toDelete->pre) {node* parent = toDelete->pre;//pre是node类型，是todelete的父节点if (parent->child1.get() == toDelete) {parent->child1.reset();//重置节点指针}else if (parent->child2.get() == toDelete) {parent->child2.reset();}//当父节点创建了两个节点后会从队列中pop，所以如果执行操作时父节点最后一个子节点被删除需要把父节点重新加入队列最先构造子节点// 检查父节点是否还有子节点，若无则加入队列处理if (!parent->child1 && !parent->child2) {que.push_front(parent);}}//如果被删除的节点没有父节点，他就是根节点else {// 删除的是根节点head.reset();std::cout << "根节点已被删除" << std::endl;}
    }

---

​4. 遍历查找（prefind/midfind/postfind）​

• ​功能：非递归实现前序、中序、后序遍历，查找目标值。
• ​算法：

​前序遍历（prefind）​

• ​步骤：
  1. 使用栈模拟递归，按 ​根-左-右 顺序访问节点。
  2. 先将根节点压栈，循环中弹出栈顶节点并检查。
  3. 右子节点先压栈（保证左子节点先访问）。
• ​代码逻辑：

  while (!st.empty()) {cur = st.top(); st.pop();if (cur->isalive && cur->data == target) { ... }if (cur->child2) st.push(child2);if (cur->child1) st.push(child1);
  }

​中序遍历（midfind）​

• ​步骤：
  1. 按 ​左-根-右 顺序访问节点。
  2. 从根节点出发，沿左子节点深入到底，依次压栈。
  3. 弹出栈顶节点并检查，转向右子节点。
• ​代码逻辑：

  while (current || !st.empty()) {while (current) { st.push(current); current = current->child1; }current = st.top(); st.pop();if (current->isalive && current->data == target) { ... }current = current->child2;
  }

​后序遍历（postfind）​

• ​步骤：
  1. 按 ​左-右-根 顺序访问节点。
  2. 记录最后访问节点 lastVisited，避免重复处理右子节点。
  3. 左子节点压栈到底，检查右子节点是否已处理，再访问根节点。
• ​代码逻辑：

  while (current || !st.empty()) {while (current) { st.push(current); current = current->child1; }node* topNode = st.top();if (topNode->child2 && topNode->child2 != lastVisited) {current = topNode->child2;} else {st.pop();if (topNode->isalive && topNode->data == target) { ... }lastVisited = topNode;}
  }

---

​5. 辅助函数（lsqueue）​

• ​功能：维护队列 que，确保按层级顺序插入节点。
• ​逻辑：
  • 将新节点加入队列尾部。
  • 若当前父节点 temp 的两个子节点均存在，将其移出队列。
  • 更新 temp 为队列头部节点，作为下一个插入的父节点。

---

​总结

• ​树结构：通过 createNode 构建完全二叉树，确保每层节点从左到右填充。
• ​删除与插入协调：队列维护待插入位置的父节点，删除后可能允许父节点重新插入子节点。
• ​遍历效率：非递归遍历通过栈实现，避免递归开销，时间复杂度为 O(n)。
• ​特点：逻辑删除保留树结构，适合需要频繁插入/删除的场景。学的头疼。