在C中打印简单的二进制搜索树

Question

我只是用C实现简单的二进制搜索树。

struct node_struct {
    int data;
    struct node_struct *right, *left;
};

typedef struct node_struct Node;

具有已经起作用的插入，删除和搜索功能。

但是我还需要实现以这种方式将树打印出来的打印功能

6
|-2
  |-1
  |-4
|-9

从节点6上方开始，左边2个，右边9个，节点2左边1个，右边4个。

所以我想问一下如何实现此打印功能。

Answer 1

您可以使用Tree traversal技术来制作Tree traversal

预订（NLR）

1. 访问当前节点的数据部分。

2. 通过递归调用前置函数遍历左子树。

3. 通过递归调用预排序函数遍历右侧子树。

保留当前级别的计数以打印缩进。例如：

Pre-order

---

Pre-order

Answer 2

递归地。试试这个。

#include <stdio.h>

struct node_struct
{
    int data;
    struct node_struct *right, *left;
};
typedef struct node_struct Node;

void treeprint(Node *root, int level)
{
        if (root == NULL)
                return;
        for (int i = 0; i < level; i++)
                printf(i == level - 1 ? "|-" : "  ");
        printf("%d\n", root->data);
        treeprint(root->left, level + 1);
        treeprint(root->right, level + 1);
}

int main(void)
{
        Node a, b, c, d, e, f;

        a.data = 6;
        a.left = &b;
        a.right = &c;

        b.data = 2;
        b.left = &d;
        b.right = &e;

        c.data = 9;
        c.left = NULL;
        c.right = NULL;

        d.data = 1;
        d.left = &f;
        d.right = NULL;

        e.data = 4;
        e.left = NULL;
        e.right = NULL;

        f.data = 8;
        f.left = NULL;
        f.right = NULL;

        treeprint(&a, 0);
}

Answer 3

有两种打印二进制搜索树的方法：

1. 级别顺序遍历
2. 预定遍历
3. 按顺序遍历
4. 后遍历

级别订单遍历使用STL队列功能。前序，有序和后序遍历使用递归的概念。

$ cc tree.c
$ ./a.out
6
|-2
  |-1
    |-8
  |-4
|-9
$

    #include <stdio.h>
#include <stdlib.h>

struct node_struct 
{
    int data;
    struct node_struct *right, *left;
};

// Implementation method
void RecursivePrint(struct node_struct* cur, int depth)
{
    //Don't print a null tree
    if(cur== 0)
    {
        return;
    }

    //Print data value of current node
    for(int i = 0; i <= depth; i++)
    {
        if(depth - i > 1)
        {
            printf("  ");
        }
        else if (depth - i == 1)
        {
            printf("|-");
        }
        else if (depth - i == 0)
        {
            printf("%d", cur->data);
        }
    }
    printf("\n");

    //Print left
    RecursivePrint(cur->left, depth + 1);
    //Print right
    RecursivePrint(cur->right, depth + 1);
}

// Method to call
void PrintTree(struct node_struct* root)
{
    RecursivePrint(root, 0);
}   

int main()
{
    struct node_struct* one;
    struct node_struct* two;
    struct node_struct* four;
    struct node_struct* six;
    struct node_struct* nine;
    one = (struct node_struct*)malloc(sizeof(struct node_struct));
    two = (struct node_struct*)malloc(sizeof(struct node_struct));
    four = (struct node_struct*)malloc(sizeof(struct node_struct));
    six = (struct node_struct*)malloc(sizeof(struct node_struct));
    nine = (struct node_struct*)malloc(sizeof(struct node_struct));

    one->data = 1;
    two->data = 2;
    four->data = 4;
    six->data = 6;
    nine->data = 9;

    one->left = 0;
    one->right = 0;

    two->left = one;
    two->right = four;

    four->left = 0;
    four->right = 0;

    six->left = two;
    six->right = nine;

    nine->left = 0;
    nine->right = 0;

    PrintTree(six);

    return 0;
}

Level order traversal

#include<iostream>

#include<queue>

using namespace std;


struct Node {

    char data;

    Node *left;

    Node *right;

};


// Function to print Nodes in a binary tree in Level order

void LevelOrder(Node *root) {

    if(root == NULL) return;

    queue<Node*> Q;

    Q.push(root); 

    //while there is at least one discovered node

    while(!Q.empty()) {

        Node* current = Q.front();

        Q.pop(); // removing the element at front

        cout<<current->data<<" ";

        if(current->left != NULL) Q.push(current->left);

        if(current->right != NULL) Q.push(current->right);

    }

}