c++ - 如何显示一种 collat​​z 猜想的二叉树？

Question

我创建了一个程序，生成如下所示的 collat​​z 猜想“树”元素的链表:

我希望我的链表显示在终端中 像这样:

  1  
  |  
  2  
  |  
  4  
  |  
  8  
  |  
 16  
  |   \  
 32    5  
  |    |  
 64   10

但我不知道如何进行。

This是我为生成系列而创建的代码。

注意:

• splitter 是产生两个指向它的数字的数字。
• 如果一个数字不是分隔符，它将有一个奇数指针为 NULL

Answer 1

在等待@RoryDaulton promise 的 Python 解决方案时，这里有一个 100% std C++ 解决方案，用于创建基于二叉树算法的控制台树。

第 1 步 - 在添加 ConsoleTree 类 之前，有必要在现有算法中添加一些元素。

Add a global ndigit integer to auto-size the length of tree-branches.

int limit, total = 1;
int ndigit = 1; // minimum number of digit

Add a field layer integer to store the branch position.

struct num {
    int n;
    int layer; // store the layer (start from 0)
    num *even;
    num *odd;
};

Extract the greater value to be displayed to compute the number of digit.

num *newnum(int x=1) {
    num *t = new num;

    t->n =x;
    ndigit = max(ndigit,x); // keep the greater value
    t->layer = 0;
    t->even=NULL;
    t->odd=NULL;
    return t;
}

Add in the generator() function the layer value.

    //...
    en->layer = front->layer + 1; // next layer on even
    on->layer = front->layer + 1; // next layer on odd
    front -> even = en;
    front -> odd = on;
    //...
    t->layer = front->layer + 1; // next layer
    front -> even = t;
    //...

第 2 步 - ConsoleTree 类 用于管理树的数字和分支。

class ConsoleTree {
private:
    int iSize;
    string *sDigitLines;
    string *sTreeLines;
protected:
    string FmtInt(int ival,int idigit,char cFill);
    string FmtTree(int idigit, bool bBranch);
    string ShiftRight(string& sLine, int ipos, int idigit);
public:
    ConsoleTree(int iLimit);
    ~ConsoleTree();
    int NbDigit(int x);
    void Make(num *pTree);
    void Print();
};

// Constructor to allocate the number of lines to be displayed
// sDigitLines array is dedicated to numbers
// sTreeLines array is dedicated to branches
ConsoleTree::ConsoleTree(int iLimit)
{
    iSize = iLimit+1;
    sDigitLines = new string[iSize];
    sTreeLines = new string[iSize];
}

// delete arrays
ConsoleTree::~ConsoleTree()
{
    delete[] sDigitLines;
    delete[] sTreeLines;
}

// format the numbers for sDigitLines
string ConsoleTree::FmtInt(int ival,int idigit,char cFill)
{
    ostringstream strStream;

    strStream << std::setfill(cFill) << std::setw(idigit) << (ival);
    return (strStream.str());
}

// format the tree & branches for sTreeLines
string ConsoleTree::FmtTree(int idigit, bool bBranch)
{
    ostringstream strStream;

    strStream << std::string(idigit-1, ' ') << "|";
    if (bBranch) strStream << std::string(idigit-2, '-') << "\\ ";
    return (strStream.str());
}

// Shift numbers & branches when adding new branches
string ConsoleTree::ShiftRight(string& sLine, int ipos, int idigit)
{
    int ilen = sLine.length();
    string sTemp;

    sTemp = sLine.substr(0,ipos);
    if ((ilen>ipos) && (sLine[ipos]=='-')) {
        sTemp += string(idigit, '-');
    }
    else {
        sTemp += string(idigit, ' ');
    }
    if (ilen>ipos) {
        sTemp += sLine.substr(ipos,ilen);
    }
    sLine = sTemp;
    return (sLine);
}

// compute the number of digit
int ConsoleTree::NbDigit(int x)
{
    ostringstream stmp;

    stmp << x;
    return (stmp.str().length()+1);
}

// recurrent function to create tree with numbers and branches
void ConsoleTree::Make(num *pn)
{
    int iLevel,iLen,iCut;
    string sTemp;

    while (pn!=NULL) {
        iLevel = pn->layer;
        sDigitLines[iLevel] += FmtInt(pn->n,ndigit,' ');
        if (pn->odd!=NULL) {
            iCut = sTreeLines[iLevel].length()+ndigit;
            sTreeLines[iLevel] += FmtTree(ndigit,true);
            for(int i=0;i<iLevel;i++) {
                sDigitLines[i] = ShiftRight(sDigitLines[i],iCut,ndigit);
                sTreeLines[i] = ShiftRight(sTreeLines[i],iCut,ndigit);
            }
            sDigitLines[iLevel] = ShiftRight(sDigitLines[iLevel],iCut,ndigit);
            Make(pn->odd);
        }
        else {
            sTreeLines[iLevel] += FmtTree(ndigit,false);
        }
        pn = pn->even;
    }
}

void ConsoleTree::Print()
{
    int iLimit = iSize -1;

    cout << "treeview" << endl;
    for(int i=0;i<iLimit;i++) {
        cout << sDigitLines[i] << endl;
        cout << sTreeLines[i] << endl;
    }
    cout << sDigitLines[iLimit] << endl;
}

第 3 步 - 然后修改 main() 函数以在使用 generator() 后显示树。

int main() {
    limit = 12; // define the height of the tree
    ndigit = 0;

    generator();

    num *pn = start; // first node of the binary-tree

    ConsoleTree myTree(limit);

    ndigit = myTree.NbDigit(ndigit);
    myTree.Make(pn);
    myTree.Print();

    cout << total << endl;

    return 0;
}

第 4 步 - 输出样本(限制 = 12)

    1
    |
    2
    |
    4
    |
    8
    |
   16
    |-----------------------\
    5                       32
    |                        |
   10                       64
    |---\                    |---\
    3   20                  21  128
    |    |                   |    |
    6   40                  42  256
    |    |--------\          |    |--------\
   12   13        80        84   85       512
    |    |         |         |    |         |
   24   26       160       168  170      1024
    |    |         |---\     |    |         |---\
   48   52        53  320  336  340       341 2048
    |    |---\     |    |    |    |---\     |    |
   96   17  104  106  640  672  113  680  682 4096

增强 - 使用半图形扩展 ASCII 字符更改控制台树的外观

In the ConsoleTree::FmtTree() function, use a set of 4 extended ASCII { 195, 179 & 196, 191 }.

#ifdef EXTEND_ASCII
    strStream << string(idigit-1, ' ') << string(1,((bBranch)?(195):(179)));
    if (bBranch) strStream << string(idigit-1, 196) << string(1, 191);
#else
    strStream << std::string(idigit-1, ' ') << "|";
    if (bBranch) strStream << std::string(idigit-2, '-') << "\\ ";
#endif

In the ConsoleTree::ShiftRight() function, use the extended ASCII 196 instead of '-'.

#ifdef EXTEND_ASCII
    // Warning: 196 is used as unsigned char ==> cast
    if ((ilen>ipos) && ((unsigned char)sLine[ipos]==196)) {
        sTemp += string(idigit, 196);
    }
#else
    if ((ilen>ipos) && (sLine[ipos]=='-')) {
        sTemp += string(idigit, '-');
    }
#endif

And a sample of output (limit = 7)

   1
   │
   2
   │
   4
   │
   8
   │
  16
   ├───────┐
   5      32
   │       │
  10      64
   ├───┐   ├───┐
   3  20  21 128