我創建了生成考拉茲猜想的「樹」的元素的鏈表程序，如下圖所示：如何顯示一種collatz猜想的二叉樹？
我希望我的鏈接列表顯示在終端事情是這樣的：
1
|
2
|
4
|
8
|
16
| \
32 5
| |
64 10
但我不知道如何繼續。
This是我爲創建系列而創建的代碼。
注：
在等待由@RoryDaulton答應Python的溶液，這裏是一個100％的std C++溶液中以產生一個控制檯樹基於與二叉樹算法。
步驟1 - 在添加ConsoleTree class之前，有必要在現有算法中添加一些元素。
添加全局
ndigit整數以自動調整長度爲 的樹枝。
int limit, total = 1;
int ndigit = 1; // minimum number of digit
添加一個字段
layer整數存儲分支位置。
struct num {
int n;
int layer; // store the layer (start from 0)
num *even;
num *odd;
};
提取更大的值，以便顯示給計算 位的數目。
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;
}
添加在
generator()功能的層值。
//...
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;
//...
第二步 - 在ConsoleTree class管理數量和樹的分支。
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字符
改變控制檯樹的外觀在
ConsoleTree::FmtTree()函數中，使用一組4個擴展的 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
在
ConsoleTree::ShiftRight()功能，使用擴展的ASCII 196代替'-'。
#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
和輸出的一個樣品（極限= 7）
1
│
2
│
4
│
8
│
16
├───────┐
5 32
│ │
10 64
├───┐ ├───┐
3 20 21 128
這對我來說真的很多東西，但我會努力去理解它...非常感謝 –
@Adityaultra來增強顯示，我已經添加了一個替代解決方案使用半 - 圖形ASCII字符（「英文設置」從128到255）。 –
這裏是Python代碼打印在Collatz二叉樹到控制檯。填充Collatz樹的第一部分是遞歸的。第二秒打印結構不是遞歸的，我對這段代碼並不滿意 - 但它做到了我想要的。印刷可以被「擠壓」，以將一些列靠近在一起並且相同的一些水平空間。如果您想要按照樣品輸出中的順序排列色譜柱，請在fillthe rest()例程的大if部分中交換ndiv3和2*n參數。
"""Print a representation of a Collatz binary tree to the console."""
# Define each column (a list) in `columns`.
STARTROW = 0 # index of zero-based row where a column starts (int)
WIDTH = 1 # index of char width of max number in the column so far (int)
NUMBERS = 2 # index of the numbers in the column (list of ints)
def numstr(num):
"""Return a number string, properly formatted with commas"""
return '{:,}'.format(num)
def fillnewcolumn(num, row, columns, dontuse, limit):
"""Fill a new column, starting with number `num` in row `row` of
the partially-filled structure 'columns', not using the numbers in
`dontuse`, up to row 'limit'."""
dontuse.add(num) # mark num as used
columns.append([row, len(numstr(num)), [num]]) # top non-blank row of col
filltherest(row, columns, dontuse, limit) # keep going
def filloldcolumn(num, row, columns, dontuse, limit):
"""Fill the old column, starting with number `num` in row `row` of
the partially-filled structure 'columns', not using the numbers in
`dontuse`, up to row 'limit'."""
dontuse.add(num) # mark num as used
thiscolumn = columns[-1] # last column so far
thiscolumn[WIDTH] = max(thiscolumn[WIDTH], len(numstr(num)))
thiscolumn[NUMBERS].append(num) # add num to column
filltherest(row, columns, dontuse, limit) # keep going
def filltherest(row, columns, dontuse, limit):
"""Fill the rest of the partially-filled structure 'columns' which
already has used the numbers in `used`, from row 'row' in column
`col`."""
if limit <= 1:
return
thiscolumn = columns[-1] # last column so far
n = thiscolumn[NUMBERS][-1] # last number in this column
ndiv3, nmod3 = divmod(n, 3)
if nmod3 == 1 and ndiv3 % 2 != 0 and ndiv3 not in dontuse: # two branches
filloldcolumn(ndiv3, row+1, columns, dontuse, limit-1)
fillnewcolumn(2*n, row+1, columns, dontuse, limit-1)
else: # one branch from here
filloldcolumn(2*n, row+1, columns, dontuse, limit-1)
limit = int(input('How many levels of Collatz to print? '))
# Fill the structure.
columns = [] # information for the overall structure to print
dontuse = {0} # numbers to not add to the structure
fillnewcolumn(1, 0, columns, dontuse, limit)
# Print the structure to the console.
for row in range(limit):
numline = ''
diagline = ''
for column in columns:
startingrow = column[STARTROW]
numwidth = column[WIDTH]
if startingrow <= row:
nstr = numstr(column[NUMBERS][row-startingrow])
numline += nstr.rjust(numwidth) + ' '
if startingrow == row:
blanks = ' ' * (len(nstr) + 1)
oldlinesize = len(numline)
diagline = diagline.rstrip() + '\\'
dellinesize = oldlinesize - len(diagline)
diagline += blanks.rjust(dellinesize, '_')
else:
diagline += '|'.rjust(numwidth) + ' '
else:
numline += ''.rjust(numwidth) + ' '
diagline += ''.rjust(numwidth) + ' '
if row > 0:
print(diagline.rstrip())
print(numline.rstrip())
這裏是上述代碼中15行的輸出。
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 1,024
| | |\____ | | |\______
48 52 53 320 336 340 341 2,048
| |\___ | | | |\______ | |
96 17 104 106 640 672 113 680 682 4,096
| | | |\ |\ | | | |\ |\_
192 34 208 35 212 213 1,280 1,344 226 1,360 227 1,364 1,365 8,192
| |\ |\ | | | | | |\ |\ | | | |
384 11 68 69 416 70 424 426 2,560 2,688 75 452 453 2,720 454 2,728 2,730 16,384
如果切換列的順序，這裏是15行的輸出。圖案更加規整，並且最終減少了橫向空間。
1
|
2
|
4
|
8
|
16
|\___________________________________________
32 5
| |
64 10
|\____________________________________ |\__________________________
128 21 20 3
| | | |
256 42 40 6
|\___________________ | |\____________ |
512 85 84 80 13 12
| | | | | |
1,024 170 168 160 26 24
|\________ | | |\_____ | |
2,048 341 340 336 320 53 52 48
| | |\____ | | | |\___ |
4,096 682 680 113 672 640 106 104 17 96
|\ |\ | | | |\ |\ | | |
8,192 1,365 1,364 227 1,360 226 1,344 1,280 213 212 35 208 34 192
| | | | |\ |\ | | | | | |\ |\ |
16,384 2,730 2,728 454 2,720 453 452 75 2,688 2,560 426 424 70 416 69 68 11 384
感謝比C++版本更小... –
您可以顯示提供的「樹」的一部分到終端格式？顯示的文本（如「合併請求...」）與軟件生成的數據之間的鏈接是什麼？ –
這就是我需要通過線路連接的數字，因此它提供了一種可視化的方式來查看連接 –
代碼是否可以使用其他語言，例如Python？ –