C/C++ 二叉樹

前言

學(xué)習(xí)了二叉樹，特此記錄一下哥童。代碼可能寫的不好豁护，大神勿噴怔软。

樹

一種數(shù)據(jù)結(jié)構(gòu)，下圖很好的描述了這種數(shù)據(jù)結(jié)構(gòu)择镇。

樹

樹中每一個(gè)元素都叫做節(jié)點(diǎn)(Node)挡逼，而最上面的那個(gè)元素比較特殊，作為樹的根節(jié)點(diǎn)腻豌，因此它也被叫做根(Root)家坎。

層

根據(jù)樹的結(jié)構(gòu)，我們可以把它通過上圖的方式分層吝梅，這樣看一個(gè)節(jié)點(diǎn)的深度就會(huì)方便很多虱疏。(大部分資料root節(jié)點(diǎn)為第一層，而我習(xí)慣以第0層開始苏携，這個(gè)依據(jù)大家課本或者自己的習(xí)慣看做瞪，對(duì)算法實(shí)現(xiàn)影響不大。)

基本概念(摘自《數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述(第二版)》)

路徑長(zhǎng)(Length)是指該路徑上邊的條數(shù)右冻。

比如上圖中第一層的節(jié)點(diǎn)到0號(hào)節(jié)點(diǎn)的路徑長(zhǎng)就是1装蓬。

深度(Depth)是指一個(gè)節(jié)點(diǎn)到root節(jié)點(diǎn)的唯一路徑長(zhǎng)。

比如上面這棵樹的0號(hào)節(jié)點(diǎn)深度就是0纱扭。第三層節(jié)點(diǎn)的深度就是3牍帚。

高度(Height)是指 $n_i$ 到一片樹葉的最長(zhǎng)路徑的長(zhǎng)。

怎么理解這句話呢乳蛾，比如暗赶，第四層18號(hào)節(jié)點(diǎn)的高度就是0；第二層3號(hào)節(jié)點(diǎn)的高度是2肃叶，4號(hào)節(jié)點(diǎn)的高度是1蹂随。其實(shí)高度就是和深度反著來的，深度是從上往下的因惭，高度是從下往上的岳锁。那么一棵樹的高度就是指root節(jié)點(diǎn)的高度，比如上面那棵樹0號(hào)節(jié)點(diǎn)的高度就是4筛欢，所以這棵樹的高度就是4浸锨。

一棵樹的深度等于它最深的樹葉的深度唇聘；該深度總是等于這個(gè)樹的高度。

二叉樹(Binary Tree)

基于對(duì)樹的概念柱搜，二叉樹便是一個(gè)節(jié)點(diǎn)上最多有2個(gè)子節(jié)點(diǎn)的一種樹迟郎。

二叉樹

幾種特殊的二叉樹

滿二叉樹(Strict/Full Binary Tree)
如圖所示的便是滿二叉樹：

滿二叉樹

通過觀察，也就是說聪蘸，滿二叉樹每一個(gè)節(jié)點(diǎn)滿足其子節(jié)點(diǎn)數(shù)不是=0就是=2宪肖。

完美二叉樹(Perfect Binary Tree)
完美二叉樹更簡(jiǎn)單的說就是滿二叉樹的一種特殊情況，他的最底層的節(jié)點(diǎn)是鋪滿的健爬，沒有空缺的控乾。

完美二叉樹

完全二叉樹(Complete Binary Tree)
完全二叉樹結(jié)合序號(hào)理解起來會(huì)好一些。
比如娜遵，我們對(duì)上面那顆完美二叉樹進(jìn)行標(biāo)號(hào)：

標(biāo)號(hào)后的完美二叉樹

這樣很容易就能看出來序號(hào)的規(guī)律蜕衡。
那么，假如我們從中拿掉幾顆節(jié)點(diǎn)：

拿掉了一些節(jié)點(diǎn)的二叉樹

這樣你就發(fā)現(xiàn)他的序號(hào)不連續(xù)了设拟，出現(xiàn)了斷裂慨仿。
而完全二叉樹的序號(hào)是連續(xù)的，所以纳胧，下面這顆便是完全二叉樹：

完全二叉樹

簡(jiǎn)單的二叉樹性質(zhì)

實(shí)現(xiàn)

數(shù)組存

學(xué)習(xí)了完全二叉樹镰吆，你就會(huì)很好理解用數(shù)組存的方式了。
用圖來表示就是這樣的：

用數(shù)組存二叉樹

具體的實(shí)現(xiàn)跑慕，可以參考我寫的二叉堆：《C 堆》万皿。

但是，使用數(shù)組有一點(diǎn)會(huì)很方便核行。通過觀察數(shù)字和層數(shù)之間的關(guān)系牢硅，我們可以發(fā)現(xiàn)存在這這樣一個(gè)規(guī)律:

層數(shù)H	元素?cái)?shù)量n
0	$1 = 2^0$
1	$2 = 2^1$
2	$4 = 2^2$
3	$8 = 2^3$
...	...
H	$n = 2^H$

那么每層序號(hào)的最大值便是到該層最后一個(gè)元素?cái)?shù)量的總和 - 1，簡(jiǎn)而言之就是一等比數(shù)列求和……

那么這樣就可以通過一個(gè)序號(hào)來求一個(gè)節(jié)點(diǎn)在樹中的深度了： $H = (int) log_2(N + 1)$ (N為序號(hào)數(shù)钮科，H為層數(shù)唤衫，我是從0開始的)

結(jié)構(gòu)體+指針存

根據(jù)每一個(gè)節(jié)點(diǎn)的特點(diǎn)，我們可以使用一個(gè)結(jié)構(gòu)體來描述每個(gè)節(jié)點(diǎn)绵脯。

每一個(gè)節(jié)點(diǎn)的圖示

用結(jié)構(gòu)體來表示就是：

struct LeafNode {
    int data; // 數(shù)據(jù)
    struct LeafNode *left; // 左邊葉子的指針
    struct LeafNode *right; // 右邊葉子的指針
};

由于struct LeafNode太長(zhǎng)了，我們可以在#include<...>之后加一句

typedef struct LeafNode Node;

來方便之后操作休里。

遍歷

有了一顆二叉樹蛆挫，那么怎么樣才能把它讀取出來呢？

通過遞歸

用類似DFS的思路妙黍，我們可以寫出下面的方法：

void preorderTraversal(Node *nd)
{
    if (nd == NULL) return;
    printf("%d ",nd -> data);
    preorderTraversal(nd -> left);
    preorderTraversal(nd -> right);
}

閱讀完代碼悴侵，其實(shí)思路就是遇到一個(gè)非空元素就把它輸出，然后在先往左節(jié)點(diǎn)走拭嫁，走完了可免，再往右邊走抓于，一級(jí)一級(jí)往上退，直到遍歷完浇借。

這種遍歷方式就叫前序遍歷(Preorder Traversal)捉撮。

看完這個(gè)代碼，我們也能想到把printf的位置換一下：

void inorderTraversal(Node *nd)
{
    if (nd == NULL) return;
    inorderTraversal(nd -> left);
    printf("%d ",nd -> data);
    inorderTraversal(nd -> right);
}

這樣就成了中序遍歷了(Inorder Traversal)妇垢。它是先遇到的節(jié)點(diǎn)不輸出巾遭，然后第二次遇到它時(shí)再輸出。

同樣的闯估，后序遍歷(Postorder Traversal)就是這樣的了：

void postorderTraversal(Node *nd)
{
    if (nd == NULL) return;
    postorderTraversal(nd -> left);
    postorderTraversal(nd -> right);
    printf("%d ",nd -> data);
}

它就是第三次遇到一個(gè)節(jié)點(diǎn)再輸出的灼舍。

最后放出一張路徑圖：

ppt作圖大法

通過隊(duì)列

用隊(duì)列來實(shí)現(xiàn)的話，這個(gè)算法就有點(diǎn)類似BFS了涨薪。

void levelTraversal(Node *root)
{
    if (root == NULL) return; // 如果root是空的直接return掉
    queue<Node*> childs; // 創(chuàng)建節(jié)點(diǎn)隊(duì)列
    childs.push(root); // 先把root節(jié)點(diǎn)加入套餐
    while (childs.size() != 0) // 隊(duì)列空了就結(jié)束
    {
        Node *current = childs.front(); // 取出隊(duì)列前端的節(jié)點(diǎn)
        printf("%d ",current -> data); // 提取數(shù)據(jù)
        if (current -> left != NULL) childs.push(current -> left); // 如果不是空的骑素，就加入套餐
        if (current -> right != NULL) childs.push(current -> right); // 同上
        childs.pop(); // 去掉隊(duì)列前端的節(jié)點(diǎn)
    }
}

這個(gè)其實(shí)就是層次遍歷。

構(gòu)建二叉樹

簡(jiǎn)單的了解了二叉樹的概念以及實(shí)現(xiàn)之后刚夺，我們將自己來構(gòu)建一顆二叉樹献丑。

用類似前序遍歷的方式來實(shí)現(xiàn)：

Node *preorderAdd(Node **node)
{
    Node *n = (Node*) malloc(sizeof(Node)); // 創(chuàng)建新的節(jié)點(diǎn)
    n -> left = NULL; // 初始化節(jié)點(diǎn)中的指針為NULL
    n -> right = NULL; // 初始化節(jié)點(diǎn)中的指針為NULL
    char c; // 用于暫時(shí)儲(chǔ)存讀入的自字符
    int isEmpty = 0; // 用于記錄是否要?jiǎng)?chuàng)建子節(jié)點(diǎn)，/就不新建了光督，是數(shù)字的話才新建節(jié)點(diǎn)
    int data = 0; // 數(shù)據(jù)
    int hasNum = 0; // 用于記錄讀入的是否為所需要的數(shù)據(jù)
    while ((c = getchar()) != EOF && !((c == ' ' || c == '\n') && hasNum)) // 當(dāng)讀入的字符為空格或者換行符 以及 讀入的字符里有數(shù)字或者/的時(shí)候挑出循環(huán)
    {
        if (c == '/')
        {
            isEmpty = 1; // 讀入的是/阳距，所以不需要新建節(jié)點(diǎn)
            hasNum = 1; // 讀入了所想要的字符
        } else if (c >= '0' && c <= '9') { // 如果是數(shù)字
            data = data * 10 + c - '0'; // 塞入數(shù)據(jù)
            hasNum = 1; // 讀入了所想要的字符
        }
    }

//--------------------------------上面都是一些輸入----------------------------

    n -> data = data; // 把數(shù)據(jù)塞入節(jié)點(diǎn)
    if (!isEmpty) // 如果不是/，那就記錄數(shù)據(jù)
    {
        if (node != NULL) *node = n; // 如果傳入的節(jié)點(diǎn)為空结借，那就新建一個(gè)root節(jié)點(diǎn)
        preorderAdd(&(n -> left)); // 繼續(xù)添加節(jié)點(diǎn)的左節(jié)點(diǎn)
        preorderAdd(&(n -> right)); // 繼續(xù)添加節(jié)點(diǎn)的右節(jié)點(diǎn)
        return n; // 返回節(jié)點(diǎn)
    } else {
        free(n); // 是/那就free掉
        return NULL;
    }
}

~~也可以采用類似層次遍歷的方法來構(gòu)建二叉樹：~~(很早寫的筐摘，代碼質(zhì)量不堪入目)

// 層次讀入
Node *addElement()
{
    queue<Node*> q;
    queue<Node*> next;
    int data = 0;
    char input; // 輸入
    char last = '/'; // 方便記錄/
    while ((input = getchar()) != EOF)
    {
         if (input == '.' || input == '/') return NULL; // 如果遇到空的，直接跳過
         if (input == ' ' || input == '\n') // 如果遇到了空格或者換行符
         {
             if (last != '/' && last != ' ' && last != '\n') // 如果上一個(gè)是數(shù)字船老，那就退出root節(jié)點(diǎn)的輸入
             {
                 last = input;
                 break;
             }
         } else if (input >= '0' && input <= '9') { // 如果是數(shù)字
             data = data * 10 + input - '0'; // 塞入數(shù)據(jù)
             last = input;
         }
    }
    Node *root_nd = createNode(data); // 創(chuàng)建root節(jié)點(diǎn)
    q.push(root_nd); // 把root節(jié)點(diǎn)加入套餐
    int l_f = 0; // 0 - 左節(jié)點(diǎn)咖熟，1 - 右節(jié)點(diǎn)
    int isSkip = 0; // 遇到/就跳過
    data = 0; // 數(shù)據(jù)清零，方便讀入
    
    while ((input = getchar()) != '.') { // 遇到"."結(jié)束輸入
        if (input == ' ' || input == '\n') // 塞入數(shù)據(jù)
        {
            if (last == ' ' || last == '\n') continue;
            if (last == '/') isSkip = 1; // 如果上一個(gè)輸入為/那就當(dāng)做跳過了
            else isSkip = 0;
            Node *nd = createNode(data); // 創(chuàng)建子節(jié)點(diǎn)
            if (!isSkip) // 如果是數(shù)據(jù)
            {
                if (!l_f) q.front() -> left = nd; // 左邊就塞左節(jié)點(diǎn)
                else q.front() -> right = nd; // 塞右節(jié)點(diǎn)
                next.push(nd); // 加入下一次要輸入的節(jié)點(diǎn)的套餐
            }
            l_f = !l_f; // 交換
            if (!l_f) q.pop(); // 輸入一個(gè)數(shù)據(jù)就刪掉一個(gè)節(jié)點(diǎn)
            if (q.size() == 0) { // 節(jié)點(diǎn)刪完了柳畔，說明要換層了
                q.swap(next); // 交換下一個(gè)與當(dāng)前的隊(duì)列
                next = queue<Node*>(); // 將下一個(gè)節(jié)點(diǎn)的
            }
            data = 0; // 清零數(shù)據(jù)
            last = input; // 記錄上一個(gè)讀入的自字符馍管，用于記錄是否讀入了/或者是空格\n之類的
        } else {
            last = input; // 記錄上一個(gè)讀入的自字符，用于記錄是否讀入了/
            data = data * 10 + input - '0'; // 把字符轉(zhuǎn)成數(shù)據(jù)
        }
    }
    return root_nd; // 返回root節(jié)點(diǎn)
}

我這邊輸入的位數(shù)字薪韩，以輸入.為結(jié)束標(biāo)志确沸，/表示空節(jié)點(diǎn)。

講完了遍歷&構(gòu)建俘陷，那該如何實(shí)際應(yīng)用呢罗捎？更具體的可以了解下別的有關(guān)二叉樹的數(shù)據(jù)結(jié)構(gòu)，或者去做一些二叉樹的題目拉盾。

下面我就將使用前序遍歷來更優(yōu)雅地輸出一顆二叉樹桨菜。

Linux `tree`命令二叉樹版

Linux里有一個(gè)命令叫做tree，他的作用是將當(dāng)前目錄下的所有文件通過遞歸全部輸出。而我們的文件系統(tǒng)正是一棵樹倒得，所以我們可以用所學(xué)知識(shí)來模仿tree的格式來輸出我們的二叉樹泻红，使其更具有可讀性。

tree命令示意

觀察圖中的輸出方式霞掺，我們很容易就可以理解一個(gè)目錄下的詳細(xì)情況谊路，所以這種輸出方式很直觀。

下面我們就來嘗試實(shí)現(xiàn)一下這個(gè)輸出方式根悼。

我們可以發(fā)現(xiàn)：

只要一個(gè)節(jié)點(diǎn)下方還有他的兄弟節(jié)點(diǎn)凶异，那就會(huì)輸出一個(gè)|來延長(zhǎng)樹枝。如果沒有的話則用空格來占位挤巡。
在輸出數(shù)據(jù)的時(shí)候剩彬，如果一個(gè)節(jié)點(diǎn)是那一層中最后一個(gè)子節(jié)點(diǎn)的話锣笨，那就以└──來連接數(shù)據(jù)雾叭，在中間的話，那就用├──連接棠隐。
數(shù)據(jù)是以前序遍歷輸出的母廷。

有了這些規(guī)律轻黑，那我們就可以嘗試用代碼來實(shí)現(xiàn)一下了：

void printTree(Node *n,int h,vector<int> *l,int hasNext)
{
    if (n == NULL) return; // 如果當(dāng)前節(jié)點(diǎn)為空，那就結(jié)束遞歸
    for (int i = 0;i < h;i ++) // 輸出空格或者樹枝
    {
        if (i == h - 1) // 輸出鄰近葉子的樹枝
        {
            if (hasNext) printf("├── "); // 如果葉子在中間琴昆，那就輸出凸型樹枝
            else {
                printf("└── "); // 如果葉子在最下面氓鄙，那就輸出尾樹枝
                (*l)[i] = 0; // 標(biāo)志著|可以不用再打印了
            }
        } else
        {
            if ((*l)[i]) printf("│   "); // 如果左節(jié)點(diǎn)有右節(jié)點(diǎn)，那就延長(zhǎng)樹枝
            else printf("    "); // 如果沒有的話业舍，那就直接輸出空格來占位
        }
    }
    printf("%d\n",n -> data); // 輸出葉子里的數(shù)據(jù)
    int b = n -> right != NULL; // 記錄除了左節(jié)點(diǎn)是否還有右節(jié)點(diǎn)
    if (l == NULL) // 創(chuàng)建一個(gè)vector抖拦，用于記錄左節(jié)點(diǎn)是否有右節(jié)點(diǎn)
    {
        vector<int> arr;
        l = &arr;
    }
    if (l -> size() <= h) l -> push_back(b); // 將是否有右節(jié)點(diǎn)的信息壓入vector
    else (*l)[h] = b;
    printTree(n -> left,h + 1,l,b); // 遍歷左節(jié)點(diǎn)
    printTree(n -> right,h + 1,l,0); // 遍歷右節(jié)點(diǎn)
}

這樣，在之后的學(xué)習(xí)中使用這個(gè)二叉樹輸出方法就可以很直觀地觀察到數(shù)據(jù)的結(jié)構(gòu)舷暮，從而方便我們debug态罪。

不過這樣輸出看起來其實(shí)并沒有那么好，首先我們無法分辨那個(gè)是左節(jié)點(diǎn)下面，哪個(gè)是右節(jié)點(diǎn)复颈，所以我們可以通過修改hasNext來讓這個(gè)函數(shù)輸出的左右節(jié)點(diǎn)更有區(qū)分度：

printTree(n -> pLeft,h + 1,l,1); // 可以顯示左右節(jié)點(diǎn)：├為左，└為右

也就是說只要改動(dòng)左節(jié)點(diǎn)的遍歷即可沥割。

但是耗啦，我們一般看的話可以認(rèn)為這是一顆橫著擺放的二叉樹，而我們橫過來看的話左右節(jié)點(diǎn)卻是相反的机杜，所以為了方便看芹彬，我再一次的修改了代碼：

void printTree_h(Node *n,int h,vector<int> *l,int hasNext)
{
    if (n == NULL) return;
    
    for (int i = 0;i < h;i ++)
    {
        if (i == h - 1)
        {
            if (hasNext) printf("├── ");
            else {
                printf("└── ");
                (*l)[i] = 0;
            }
        } else
        {
            if ((*l)[i]) printf("│   ");
            else printf("    ");
        }
    }
    printf("%d\n",n -> data);
    int b = n -> left != NULL;
    if (l == NULL)
    {
        vector<int> arr;
        l = &arr;
    }
    if (l -> size() <= h) l -> push_back(b);
    else (*l)[h] = b;
    // printTree(n -> pRight,h + 1,l,b); // 正常輸出
    printTree_h(n -> right,h + 1,l,1); // 可以顯示左右節(jié)點(diǎn)：├為右，└為左
    printTree_h(n -> left,h + 1,l,0);
}

其實(shí)就是將遞歸的那兩句話換了個(gè)位置就好了叉庐，這樣顯示就順多了。

一顆不太好看的BST樹

第二種樹的打印方式

之前做藍(lán)橋杯的題的時(shí)候遇到一種比較好看的打印方式会喝。

struct ps {
    int dps;
    int length;
    int type;
};

void print_binTree(Node *root, int d, int lr, vector<ps> dps)
{
    if (root == NULL) return;
    
    ps p = {d, (int) log10(root -> data) + 1, root -> right != NULL && lr == 0};
    if (dps.size() <= d) dps.push_back(p);
    else dps[d] = p;
    print_binTree(root -> right,d + 1, 1, dps);
    for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
    {
        if (i -> type && i -> dps != 0) printf("|");
        else printf(".");
        for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
        {
            printf(".");
        }
        
    }
    if (d != 0) printf("|-");
    printf("%d",root -> data);
    if (root -> left != NULL || root -> right != NULL) printf("-|");
    printf("\n");
    dps[d].type = root -> left != NULL && lr;
    print_binTree(root -> left,d + 1, 0, dps);
}

調(diào)用方法陡叠。

print_binTree(root,0,1,vector<ps>());

效果：

tree2的效果

圖中正是使用了下面的全部代碼玩郊。

全部代碼

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#include <set>

using namespace std;

typedef struct LeafNode Node;

struct LeafNode {
    int data; // 數(shù)據(jù)
    struct LeafNode *left; // 左邊葉子的指針
    struct LeafNode *right; // 右邊葉子的指針
};

Node *createNode(int data)
{
    Node *rootNode = (Node*) malloc(sizeof(Node));
    rootNode -> data = data;
    rootNode -> left = NULL;
    rootNode -> right = NULL;
    return rootNode;
}

// 層次讀入
Node *addElement()
{
    queue<Node*> q;
    queue<Node*> next;
    int data = 0;
    char input; // 輸入
    char last = '/'; // 方便記錄/
    while ((input = getchar()) != EOF)
    {
         if (input == '.' || input == '/') return NULL; // 如果遇到空的，直接跳過
         if (input == ' ' || input == '\n') // 如果遇到了空格或者換行符
         {
             if (last != '/' && last != ' ' && last != '\n') // 如果上一個(gè)是數(shù)字枉阵，那就退出root節(jié)點(diǎn)的輸入
             {
                 last = input;
                 break;
             }
         } else if (input >= '0' && input <= '9') { // 如果是數(shù)字
             data = data * 10 + input - '0'; // 塞入數(shù)據(jù)
             last = input;
         }
    }
    Node *root_nd = createNode(data); // 創(chuàng)建root節(jié)點(diǎn)
    q.push(root_nd); // 把root節(jié)點(diǎn)加入套餐
    int l_f = 0; // 0 - 左節(jié)點(diǎn)译红，1 - 右節(jié)點(diǎn)
    int isSkip = 0; // 遇到/就跳過
    data = 0; // 數(shù)據(jù)清零，方便讀入
    
    while ((input = getchar()) != '.') { // 遇到"."結(jié)束輸入
        if (input == ' ' || input == '\n') // 塞入數(shù)據(jù)
        {
            if (last == ' ' || last == '\n') continue;
            if (last == '/') isSkip = 1; // 如果上一個(gè)輸入為/那就當(dāng)做跳過了
            else isSkip = 0;
            Node *nd = createNode(data); // 創(chuàng)建子節(jié)點(diǎn)
            if (!isSkip) // 如果是數(shù)據(jù)
            {
                if (!l_f) q.front() -> left = nd; // 左邊就塞左節(jié)點(diǎn)
                else q.front() -> right = nd; // 塞右節(jié)點(diǎn)
                next.push(nd); // 加入下一次要輸入的節(jié)點(diǎn)的套餐
            }
            l_f = !l_f; // 交換
            if (!l_f) q.pop(); // 輸入一個(gè)數(shù)據(jù)就刪掉一個(gè)節(jié)點(diǎn)
            if (q.size() == 0) { // 節(jié)點(diǎn)刪完了兴溜，說明要換層了
                q.swap(next); // 交換下一個(gè)與當(dāng)前的隊(duì)列
                next = queue<Node*>(); // 將下一個(gè)節(jié)點(diǎn)的
            }
            data = 0; // 清零數(shù)據(jù)
            last = input; // 記錄上一個(gè)讀入的自字符侦厚，用于記錄是否讀入了/或者是空格\n之類的
        } else {
            last = input; // 記錄上一個(gè)讀入的自字符，用于記錄是否讀入了/
            data = data * 10 + input - '0'; // 把字符轉(zhuǎn)成數(shù)據(jù)
        }
    }
    return root_nd; // 返回root節(jié)點(diǎn)
}

Node *preorderAdd(Node **node)
{
    Node *n = (Node*) malloc(sizeof(Node)); // 創(chuàng)建新的節(jié)點(diǎn)
    n -> left = NULL; // 初始化節(jié)點(diǎn)中的指針為NULL
    n -> right = NULL; // 初始化節(jié)點(diǎn)中的指針為NULL
    char c; // 用于暫時(shí)儲(chǔ)存讀入的自字符
    int isEmpty = 0; // 用于記錄是否要?jiǎng)?chuàng)建子節(jié)點(diǎn)拙徽，/就不新建了刨沦，是數(shù)字的話才新建節(jié)點(diǎn)
    int data = 0; // 數(shù)據(jù)
    int hasNum = 0; // 用于記錄讀入的是否為所需要的數(shù)據(jù)
    while ((c = getchar()) != EOF && !((c == ' ' || c == '\n') && hasNum)) // 當(dāng)讀入的字符為空格或者換行符 以及 讀入的字符里有數(shù)字或者/的時(shí)候挑出循環(huán)
    {
        if (c == '/' || c == '.')
        {
            isEmpty = 1; // 讀入的是/，所以不需要新建節(jié)點(diǎn)
            hasNum = 1; // 讀入了所想要的字符
        } else if (c >= '0' && c <= '9') { // 如果是數(shù)字
            data = data * 10 + c - '0'; // 塞入數(shù)據(jù)
            hasNum = 1; // 讀入了所想要的字符
        }
    }
    n -> data = data; // 把數(shù)據(jù)塞入節(jié)點(diǎn)
    if (!isEmpty) // 如果不是/膘怕，那就記錄數(shù)據(jù)
    {
        if (node != NULL) *node = n; // 如果傳入的節(jié)點(diǎn)為空想诅，那就新建一個(gè)root節(jié)點(diǎn)
        preorderAdd(&(n -> left)); // 繼續(xù)添加節(jié)點(diǎn)的左節(jié)點(diǎn)
        preorderAdd(&(n -> right)); // 繼續(xù)添加節(jié)點(diǎn)的右節(jié)點(diǎn)
        return n; // 返回節(jié)點(diǎn)
    } else {
        free(n); // 是/那就free掉
        return NULL;
    }
}

// 前序遍歷
void preorderTraversal(Node *nd)
{
    if (nd == NULL) return;
    printf("%d ",nd -> data);
    preorderTraversal(nd -> left);
    preorderTraversal(nd -> right);
}

// 中序遍歷
void inorderTraversal(Node *nd)
{
    if (nd == NULL) return;
    inorderTraversal(nd -> left);
    printf("%d ",nd -> data);
    inorderTraversal(nd -> right);
}

// 后序遍歷
void postorderTraversal(Node *nd)
{
    if (nd == NULL) return;
    postorderTraversal(nd -> left);
    postorderTraversal(nd -> right);
    printf("%d ",nd -> data);
}

// 層次遍歷
void levelTraversal(Node *root)
{
    if (root == NULL) return; // 如果root是空的直接return掉
    queue<Node*> childs; // 創(chuàng)建節(jié)點(diǎn)隊(duì)列
    childs.push(root); // 先把root節(jié)點(diǎn)加入套餐
    while (childs.size() != 0) // 隊(duì)列空了就結(jié)束
    {
        Node *current = childs.front(); // 取出隊(duì)列前端的節(jié)點(diǎn)
        printf("%d ",current -> data); // 提取數(shù)據(jù)
        if (current -> left != NULL) childs.push(current -> left); // 如果不是空的，就加入套餐
        if (current -> right != NULL) childs.push(current -> right); // 同上
        childs.pop(); // 去掉隊(duì)列前端的節(jié)點(diǎn)
    }
}

void printTree(Node *n,int h,vector<int> *l,int hasNext)
{
    if (n == NULL) return; // 如果當(dāng)前節(jié)點(diǎn)為空岛心，那就結(jié)束遞歸
    for (int i = 0;i < h;i ++) // 輸出空格或者樹枝
    {
        if (i == h - 1) // 輸出鄰近葉子的樹枝
        {
            if (hasNext) printf("├── "); // 如果葉子在中間来破，那就輸出凸型樹枝
            else {
                printf("└── "); // 如果葉子在最下面，那就輸出尾樹枝
                (*l)[i] = 0; // 標(biāo)志著|可以不用再打印了
            }
        } else
        {
            if ((*l)[i]) printf("│   "); // 如果左節(jié)點(diǎn)有右節(jié)點(diǎn)忘古，那就延長(zhǎng)樹枝
            else printf("    "); // 如果沒有的話徘禁，那就直接輸出空格來占位
        }
    }
    printf("%d\n",n -> data); // 輸出葉子里的數(shù)據(jù)
    int b = n -> right != NULL; // 記錄除了左節(jié)點(diǎn)是否還有右節(jié)點(diǎn)
    if (l == NULL) // 創(chuàng)建一個(gè)vector，用于記錄左節(jié)點(diǎn)是否有右節(jié)點(diǎn)
    {
        vector<int> arr;
        l = &arr;
    }
    if (l -> size() <= h) l -> push_back(b); // 將是否有右節(jié)點(diǎn)的信息壓入vector
    else (*l)[h] = b;
    printTree(n -> left,h + 1,l,b); // 遍歷左節(jié)點(diǎn)
    printTree(n -> right,h + 1,l,0); // 遍歷右節(jié)點(diǎn)
}

void printTree_h(Node *n,int h,vector<int> *l,int hasNext)
{
    if (n == NULL) return;
    
    for (int i = 0;i < h;i ++)
    {
        if (i == h - 1)
        {
            if (hasNext) printf("├── ");
            else {
                printf("└── ");
                (*l)[i] = 0;
            }
        } else
        {
            if ((*l)[i]) printf("│   ");
            else printf("    ");
        }
    }
    printf("%d\n",n -> data);
    int b = n -> left != NULL;
    if (l == NULL)
    {
        vector<int> arr;
        l = &arr;
    }
    if (l -> size() <= h) l -> push_back(b);
    else (*l)[h] = b;
    // printTree(n -> pRight,h + 1,l,b); // 正常輸出
    printTree_h(n -> right,h + 1,l,1); // 可以顯示左右節(jié)點(diǎn)：├為右髓堪，└為左
    printTree_h(n -> left,h + 1,l,0);
}

struct ps {
    int dps;
    int length;
    int type;
};

void print_binTree(Node *root, int d, int lr, vector<ps> dps)
{
    if (root == NULL) return;
    
    ps p = {d, (int) log10(root -> data) + 1, root -> right != NULL && lr == 0};
    if (dps.size() <= d) dps.push_back(p);
    else dps[d] = p;
    print_binTree(root -> right,d + 1, 1, dps);
    for (vector<ps>::iterator i = dps.begin();i != dps.end() - 1;i ++)
    {
        if (i -> type && i -> dps != 0) printf("|");
        else printf(".");
        for (int j = 0;j < i -> length + ((i -> dps) != 0) * 2;j ++)
        {
            printf(".");
        }
        
    }
    if (d != 0) printf("|-");
    printf("%d",root -> data);
    if (root -> left != NULL || root -> right != NULL) printf("-|");
    printf("\n");
    dps[d].type = root -> left != NULL && lr;
    print_binTree(root -> left,d + 1, 0, dps);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Type of building tree (p/l/other=exit):");
    char cmd;
    set<int> type = {'p','l'};
    while (scanf(" %c",&cmd) != EOF && type.find(cmd) != type.end())
    {
        Node *root = NULL;
        switch (cmd) {
        case 'p':
            root = preorderAdd(NULL);
            break;
        case 'l':
            root = addElement();
            break;
        }
        printf("preorder:\n");
        preorderTraversal(root);
        printf("\ninorder:\n");
        inorderTraversal(root);
        printf("\npostorder:\n");
        postorderTraversal(root);
        printf("\nlevel:\n");
        levelTraversal(root);
        printf("\ntree:\n");
        printTree_h(root,0,NULL,0);
        printf("\ntree2:\n");
        print_binTree(root,0,1,vector<ps>());
        printf("Type of building tree (p/l/other=exit):");
    }
    
    return 0;
}

運(yùn)行截圖：

截圖

注：這個(gè)是之前的老圖送朱，是我之前的代碼的效果，我更新了代碼旦袋，具體效果是上面的那幅圖骤菠。

最后編輯于：2020.02.24 20:26:15

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市疤孕，隨后出現(xiàn)的幾起案子商乎，更是在濱河造成了極大的恐慌，老刑警劉巖祭阀，帶你破解...
沈念sama閱讀 218,941評(píng)論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件鹉戚，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡专控，警方通過查閱死者的電腦和手機(jī)抹凳，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,397評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來伦腐，“玉大人赢底，你說我怎么就攤上這事。” “怎么了幸冻？”我有些...
開封第一講書人閱讀 165,345評(píng)論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵粹庞，是天一觀的道長(zhǎng)。經(jīng)常有香客問我洽损，道長(zhǎng)庞溜，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,851評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任碑定，我火速辦了婚禮流码，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘延刘。我一直安慰自己漫试，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,868評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布访娶。她就那樣靜靜地躺著商虐，像睡著了一般。火紅的嫁衣襯著肌膚如雪崖疤。梳的紋絲不亂的頭發(fā)上秘车，一...
開封第一講書人閱讀 51,688評(píng)論 1贊 305
城市分裂傳說
那天，我揣著相機(jī)與錄音劫哼，去河邊找鬼叮趴。笑死，一個(gè)胖子當(dāng)著我的面吹牛权烧，可吹牛的內(nèi)容都是我干的眯亦。我是一名探鬼主播，決...
沈念sama閱讀 40,414評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼般码，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼妻率！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起板祝，我...
開封第一講書人閱讀 39,319評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤宫静，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后券时，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體孤里，經(jīng)...
沈念sama閱讀 45,775評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,945評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年橘洞，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了捌袜。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,096評(píng)論 1贊 350
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡炸枣，死狀恐怖虏等，靈堂內(nèi)的尸體忽然破棺而出弄唧，到底是詐尸還是另有隱情，我是刑警寧澤博其，帶...
沈念sama閱讀 35,789評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布套才，位于F島的核電站，受9級(jí)特大地震影響慕淡，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜沸毁，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,437評(píng)論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一峰髓、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧息尺，春花似錦携兵、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,993評(píng)論 0贊 22
一樁弒父案徐紧，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至炭懊，卻和暖如春并级，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背侮腹。一陣腳步聲響...
開封第一講書人閱讀 33,107評(píng)論 1贊 271
情欲美人皮
我被黑心中介騙來泰國(guó)打工嘲碧，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人父阻。一個(gè)月前我還...
沈念sama閱讀 48,308評(píng)論 3贊 372
代替公主和親
正文我出身青樓愈涩，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親加矛。傳聞我的和親對(duì)象是個(gè)殘疾皇子履婉，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,037評(píng)論 2贊 355