C++指针实现二叉树前序遍历触发Segmentation Fault问题求助

问题描述 #

我用指针实现了一个C++二叉树，尝试通过递归前序深度优先遍历打印节点，但处理右节点时触发Segmentation Fault。换其他二叉树实现就能正常运行，所以问题应该出在当前的指针实现里。

测试代码 #

#include "../data-structures/trees/binary-tree-pointers/tree.h"
using namespace std;

void PrintTree(BinaryTree<int> tree, BinaryTree<int>::node node) {
   cout << tree.Label(node) << endl;
   if (tree.LeftChild(node) != tree.lambda) PrintTree(tree, tree.LeftChild(node));
   if (tree.RightChild(node) != tree.lambda) PrintTree(tree, tree.RightChild(node));
}

int main() {
   BinaryTree<int> tree;
   BinaryTree<int>::node node;

   tree.CreateRoot(1);
   tree.CreateLeftChild(tree.Root(), 2);
   tree.CreateRightChild(tree.Root(), 3);
   node = tree.Root();
   node = tree.LeftChild(node);
   tree.CreateLeftChild(node, 4);
   tree.CreateRightChild(node, 5);
   node = tree.LeftChild(node);
   tree.CreateLeftChild(node, 7);
   node = tree.Root();
   node = tree.RightChild(node);
   tree.CreateRightChild(node, 8);

   PrintTree(tree, tree.Root());

   return 0;
}

二叉树实现代码 #

#include <iostream>
#include <cstdlib>

template <typename nodeType>
class BinaryTree {
   private:
   struct Tnode {
      Tnode *parent, *left, *right;
      nodeType label;
   };

   Tnode *B;

   public:
   typedef Tnode* node;
   const node lambda = NULL;

   void Del(node n) {
      if (n->left != NULL) Del(n->left);
      if (n->right != NULL) Del(n->right);
      delete n;
   }

   void Prnt(node n) {
      std::cout << n->label << " ";
      if (n->left != NULL) Prnt(n->left);
      if (n->right != NULL) Prnt(n->right);
   }

   BinaryTree() {
      B = NULL;
   }

   BinaryTree(nodeType x) {
      B = new Tnode;
      B->parent = B->left = B->right = NULL;
      B->label = x;
   }

   bool IsEmpty() {
      return B == lambda;
   }

   nodeType Label(node n) {
      if (n == lambda) {
         std::cout << "That node doesn't exist!" << std::endl;
         exit(EXIT_FAILURE);
      }
      return n->label;
   }
   
   node Root() {
      return B;
   }

   node Parent(node n) {
      if (n == lambda) {
         std::cout << "That node doesn't exist!" << std::endl;
         exit(EXIT_FAILURE);
      }
      return n->parent;
   }

   node LeftChild(node n) {
      if (n == lambda) {
         std::cout << "That node doesn't exist!" << std::endl;
         exit(EXIT_FAILURE);
      }
      return n->left;
   }

   node RightChild(node n) {
      if (n == lambda) {
         std::cout << "That node doesn't exist!" << std::endl;
         exit(EXIT_FAILURE);
      }
      return n->right;
   }

   void ChangeLabel(node n, nodeType x) {
      if (n == lambda) {
         std::cout << "That node doesn't exist!" << std::endl;
         exit(EXIT_FAILURE);
      }
      n->label = x;
   }

   void CreateRoot(nodeType x) {
      if (!this->IsEmpty()) {
         std::cout << "Can't create root! Tree is not empty!" << std::endl;
         exit(EXIT_FAILURE);
      }
      B = new Tnode;
      B->parent = B->left = B->right = NULL;
      B->label = x;
   }

   void CreateLeftChild(node n, nodeType x) {
      if (n == lambda) {
         std::cout << "That node doesn't exist!" << std::endl;
         exit(EXIT_FAILURE);
      }
      if (n->left != lambda) {
         std::cout << "Can't create left node! It already exists" << std::endl;
         exit(EXIT_FAILURE);
      }
      Tnode *newNode = new Tnode;
      newNode->left = newNode->right = NULL;
      newNode->parent = n;
      newNode->label = x;
      n->left = newNode;
   }

   void CreateRightChild(node n, nodeType x) {
      if (n == lambda) {
         std::cout << "That node doesn't exist!" << std::endl;
         exit(EXIT_FAILURE);
      }
      if (n->right != lambda) {
         std::cout << "Can't create right node! It already exists" << std::endl;
         exit(EXIT_FAILURE);
      }
      Tnode *newNode = new Tnode;
      newNode->label = x;
      newNode->left = newNode->right = NULL;
      newNode->parent = n;
      n->right = newNode;
   }

   void Delete(node n) {
      if (n == lambda) {
         std::cout << "That node doesn't exist!" << std::endl;
         exit(EXIT_FAILURE);
      }
      if (n->parent != NULL) {
         if (n->parent->left == n) n->parent->left = NULL;
         else n->parent->right = NULL;
         Del(n);
      }
      else {
         Del(n);
         B = NULL;
      }
   }

   void Print() {
      Prnt(B);
      std::cout << std::endl;
   }

   ~BinaryTree() {
      if (B != lambda) Del(B);
   }
};

问题根源 #

PrintTree函数的第一个参数使用值传递：BinaryTree<int> tree。每次递归调用都会生成一个二叉树的副本，当副本生命周期结束时，析构函数~BinaryTree()会调用Del递归删除所有节点，导致原树的节点内存被提前释放。后续遍历到右节点时，访问的是已经被释放的内存，直接触发Segmentation Fault。

修复方案 #

将PrintTree的第一个参数改为引用传递，避免复制整个树，也就不会触发不必要的节点删除：

void PrintTree(BinaryTree<int>& tree, BinaryTree<int>::node node) {
   cout << tree.Label(node) << endl;
   if (tree.LeftChild(node) != tree.lambda) PrintTree(tree, tree.LeftChild(node));
   if (tree.RightChild(node) != tree.lambda) PrintTree(tree, tree.RightChild(node));
}

额外优化 #

原代码中lambda是类的非静态const成员，每次创建对象都会生成一个副本，建议改为静态成员，减少冗余且访问更合理：

template <typename nodeType>
class BinaryTree {
   // ... 原有代码 ...
   public:
   typedef Tnode* node;
   static const node lambda; // 修改为静态成员
   // ... 原有代码 ...
};

// 类外初始化静态成员
template <typename nodeType>
const typename BinaryTree<nodeType>::node BinaryTree<nodeType>::lambda = nullptr;

这样在判断节点是否为空时，可直接使用BinaryTree<int>::lambda，无需依赖具体对象。

内容的提问来源于stack exchange，提问作者Timjuice