C++实现完全二叉树 |21xrx.com

C++实现完全二叉树

2023-07-13 06:17:03 深夜i -- --

C++ 完全二叉树实现

完全二叉树是一种特殊的二叉树，它的所有叶子节点都在同一层上，而且除了最后一层外，其它层的节点数量都是满的，最后一层的节点从左到右排列。如何使用C++实现完全二叉树呢？

首先要定义一个节点类来表示树中的每一个节点。节点类应该包含节点值、左子节点、右子节点、父节点等信息。C++中可以用结构体或类来实现节点类，下面是一个示例：


struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode* parent;
  TreeNode(int value): val(value), left(NULL), right(NULL), parent(NULL){}
};

接下来，定义一个完全二叉树类。完全二叉树类应该包含二叉树的根节点、节点数量等信息，还应该提供向树中插入节点、删除节点、查询节点等操作。下面是一个简单的示例：


class CompleteBinaryTree {
public:
  CompleteBinaryTree(): root(NULL), size(0) {}
  TreeNode* insertNode(int value) {
    if (size == 0) {
      root = new TreeNode(value);
      size++;
      return root;
    }
    queue<TreeNode*> q;
    q.push(root);
    TreeNode* node = NULL;
    while (!q.empty()) {
      node = q.front();
      q.pop();
      if (!node->left) {
        node->left = new TreeNode(value);
        node->left->parent = node;
        size++;
        return node->left;
      }
      else if (!node->right) {
        node->right = new TreeNode(value);
        node->right->parent = node;
        size++;
        return node->right;
      }
      else {
        q.push(node->left);
        q.push(node->right);
      }
    }
  }
  void deleteNode(TreeNode* node) {
    if (!node || !root) return;
    if (node == root)
      delete root;
      size--;
      root = NULL;
      return;
    
    TreeNode* parent = node->parent;
    if (!parent) return;
    if (!isLastNode(node)) {
      TreeNode* lastNode = getLastNode();
      swap(node->val, lastNode->val);
      node = lastNode;
    }
    if (node->parent->left == node) node->parent->left = NULL;
    else node->parent->right = NULL;
    size--;
    delete node;
    adjustDelete(parent);
  }
  TreeNode* searchNode(int value) {
    if (!root) return NULL;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      TreeNode* node = q.front();
      q.pop();
      if (node->val == value) return node;
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    return NULL;
  }
  int getSize() return size;
private:
  TreeNode* root; // 根节点
  int size; // 节点数量
  bool isLastNode(TreeNode* node) {
    if (node->parent->right == node) {
      TreeNode* temp = node;
      while (temp->parent && temp->parent->right == temp)
        temp = temp->parent;
      
      if (!temp->parent) return true;
      temp = temp->parent->right;
      while (temp->left)
        temp = temp->left;
      
      if (temp == getLastNode()) return true;
      else return false;
    }
    else
      return false;
    
  }
  void adjustDelete(TreeNode* node) {
    while (node) {
      if (!node->left && !node->right || !node->right && node->left && !node->left->left && !node->left->right)
        node = node->parent;
      
      else if (!node->right && node->left && (node->left->left || node->left->right || getSize() % 2 == 0))
        delete node->left;
        size--;
        node->left = NULL;
        node = node->parent;
      
      else if (node->right && !node->right->left && !node->right->right)
        delete node->right;
        size--;
        node->right = NULL;
        node = node->parent;
      
      else if (node->right && (node->right->left || node->right->right || getSize() % 2 == 0))
        delete node->left;
        size--;
        node->left = node->right;
        node->left->parent = node;
        node->right = NULL;
        node = node->parent;
      
    }
  }
  TreeNode* getLastNode() {
    queue<TreeNode*> q;
    q.push(root);
    TreeNode* node = NULL;
    while (!q.empty()) {
      node = q.front();
      q.pop();
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    return node;
  }
};

完全二叉树的插入操作比较简单，只需要按照树的层次遍历的顺序插入新节点即可；删除操作要复杂一些，因为如果直接删除某个节点可能会破坏完全二叉树的结构，因此需要进行一些调整。查询操作也比较简单，只需要按照树的层次遍历的顺序逐个比较节点值即可。

以上是使用C++实现完全二叉树的一个基本框架，请注意，这只是一个示例，实际上树的实现方式有很多种，具体实现可以根据需求进行调整。

上一篇: idea打包java可执行jar包

下一篇: C++中使用函数模板的回调函数

评论区

()

相似文章