时间戳

首页 > 解决方案 > 带字符串的左孩子，右兄弟二叉树

c++ - 带字符串的左孩子，右兄弟二叉树

问题描述

我正在编写一个程序来创建一个基于树的数据结构，用于存储字符串集合，任意称为“Pxtree”。该程序是对左子右兄弟二叉树问题的修改，涉及动态内存和指针，不使用节点结构/类。

数据结构采用树的形式。树中的每个节点都与一个字符相关联（以及一个表示计数的整数，稍后将解释）。每个节点也可以有任意数量的子节点。节点的子节点根据插入/删除时间的顺序保存（因此不一定按字母顺序）。

字符存储在节点中的方式是，可以通过遵循从根开始的路径并在每个节点处选择一个子节点来跟踪字符串。每个节点的字符被连接起来给出字符串。另一种看待这个问题的方法是，每个字符串都由单个字母的路径表示，但是共享一些开头字母（或前缀）的字符串会将其路径的这些部分合并。因此，一个节点的任何两个子节点都不应该包含相同的字符。

树的根节点包含一个不属于任何字符串的特殊字符“\0”。

打印的树应采用如下形式：

h 0
  e 0
    l 0
      l 0
        o 1
      p 1

本例中输入的字符串是“hello”和“help”。

每个字符旁边的整数显示它是否是字符串的结尾。如果整数为 1，则字符为字符串的结尾。如果它大于 1，则表示同一字符串在树中多次出现。

我已经在程序中编写了多个函数：默认构造函数、复制构造函数/复制赋值、整数计数以及允许输入和删除字符串的添加和删除函数。注意：删除字符串并不会完全删除字符串，而是将其最后一个字符的整数计数设置为 0。

到目前为止，这是我的代码：

像素树.cpp：

#include <iostream>
#include "Pxtree.h"
using namespace std;

Pxtree::Pxtree() { // default constructor
        c_ = '\0';
        count_ = 0;

        leftmostChild_ = nullptr;
        nextSibling_ = nullptr;
}

Pxtree::~Pxtree() { // destructor

Pxtree::Pxtree(const Pxtree& other) { // copy constructor
        leftmostChild_ = other.leftmostChild_;
        nextSibling_ = other.nextSibling_;

        c_ = other.c_;
        count_ = other.count_;
}

Pxtree& Pxtree::operator=(const Pxtree& other) { // copy assignment
        if (&other != this) {
                c_ = other.c_;

                if (other.nextSibling_ == nullptr) nextSibling_ = nullptr;
                else nextSibling_ = new Pxtree(*other.nextSibling_);
        }
        return *this;
}

int Pxtree::count(string s) const { // integer count
        if (c_ == '\0') {
                if (leftmostChild_ == nullptr) return 0;
                else return leftmostChild_->count(s);
        }
        else if (c_ == s[0]) {
                if (s.length() == 1) return count_;
                else if (leftmostChild_ == nullptr) return 0;
                else return leftmostChild_->count(s.erase(0,1));
        }
        else {
                if (nextSibling_ == nullptr) return 0;
                else return nextSibling_->count(s);
        }
}

void Pxtree::add(string s) { // add string function
        Pxtree *p = this;

        for (char c : s) {
                if (p->leftmostChild_ != nullptr) {
                        if (p->leftmostChild_->c_ == c) p = p->leftmostChild_;
                        else if (p->nextSibling_ != nullptr) {
                                while (p->nextSibling_ != nullptr) {
                                        if (p->nextSibling_->c_ == c) {
                                                p = p->nextSibling_;
                                                break;
                                        }
                                        p = p->nextSibling_;
                                }
                                if (p->c_ == c) continue;
                                if (p->nextSibling_ == nullptr) {
                                        printf("Add sibling %c\n", c);

                                        auto *node = new Pxtree();

                                        node->c_ = c;
                                        node->count_ = 0;
                                        node->leftmostChild_ = nullptr;
                                        node->nextSibling_ = nullptr;

                                        p->nextSibling_ = node;
                                }
                        }
                        else {
                                printf("Add sibling %c\n", c);

                                auto *node = new Pxtree();

                                node->c_ = c;
                                node->count_ = 0;
                                node->leftmostChild_ = nullptr;
                                node->nextSibling_ = nullptr;

                                p->nextSibling_ = node;
                                p = node;
                        }
                }
                else {
                        printf("Add child %c\n", c);

                        auto *node = new Pxtree();

                        node->c_ = c;
                        node->count_ = 0;
                        node->leftmostChild_ = nullptr;
                        node->nextSibling_ = nullptr;

                        p->leftmostChild_ = node;
                        p = node;
                }
        }
        p->count_++;
}

void Pxtree::remove(string s) {
        Pxtree *p = this;
        if (s.length() == 0) return;

        for (char c : s) {
                if (p->leftmostChild_ != nullptr) {
                        if (p->leftmostChild_->c_ == c) {
                                p = p->leftmostChild_;
                                printf("%c\n", p->c_);
                                printf("count: %d\n", p->count_);
                        }
                        else if (p->nextSibling_ != nullptr) {
                                while (p->nextSibling_ != nullptr) {
                                        if (p->nextSibling_->c_ == c) {
                                                p = p->nextSibling_;
                                                break;
                                        }
                                        p = p->nextSibling_;
                                }
                                if (p->c_ == 0) {
                                        printf("%c\n", c);
                                        printf("count: %d\n", p->count_);
                                        continue;
                                }
                                if (p->nextSibling_ == nullptr) return;
                                if (p->nextSibling_->c_ == c) {
                                        p = p->nextSibling_;
                                        printf("%c\n", p->c_);
                                        printf("count: %d\n", p->count_);
                                }
                        }
                        else return;
                }
        }
        p->count_--;
        printf("final count: %d\n", p->count_);
}

string Pxtree::print() const {
}

string Pxtree::autoComplete(string s) const {
}

void Pxtree::compact() {
}

像素树.h：

#ifndef PXTREE_H_
#define PXTREE_H_

#include <string>
using std::string;

class Pxtree {
public:
        Pxtree();
        ~Pxtree();
        Pxtree(const Pxtree& other);
        Pxtree& operator=(const Pxtree& other);
        int count(string s) const;
        void add(string s);
        void remove(string s);
        string print() const;
        string autoComplete(string s) const;
        void compact();

private:
        char c_;
        int count_;
        Pxtree* leftmostChild_;
        Pxtree* nextSibling_;
};

#endif

我正在努力为析构函数(~Pxtree()) 和打印函数(string print() const) 编写代码；我不确定从哪里开始。

标签： c++stringprintingbinary-treedestructor

解决方案

推荐阅读