在 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

递归。试试这个。

    #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;
}

Answer 2

你可以做一个Tree traversal using the Pre-order技巧

Pre-order (NLR)

Access the data part of the current node.

Traverse the left subtree by recursively calling the pre-order function.

Traverse the right subtree by recursively calling the pre-order function.

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

#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);
}

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

Answer 3

打印二叉搜索树的方式有4种：

层序遍历
前序遍历
中序遍历
Post-顺序遍历

层序遍历使用STL Queue函数。而前序、中序和post序遍历使用了递归的概念。

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);

    }

}

Preorder, Inorder, Postorder

#include<iostream>

using namespace std;

 

struct Node {

    char data;

    struct Node *left;

    struct Node *right;

};


//Function to visit nodes in Preorder

void Preorder(struct Node *root) {

    // base condition for recursion

    // if tree/sub-tree is empty, return and exit

    if(root == NULL) return;


    printf("%c ",root->data); // Print data

    Preorder(root->left); // Visit left subtree

    Preorder(root->right); // Visit right subtree

}


//Function to visit nodes in Inorder

void Inorder(Node *root) {

    if(root == NULL) return;


    Inorder(root->left); //Visit left subtree

    printf("%c ",root->data); //Print data

    Inorder(root->right); // Visit right subtree

}


//Function to visit nodes in Postorder

void Postorder(Node *root) {

    if(root == NULL) return;


    Postorder(root->left); // Visit left subtree

    Postorder(root->right); // Visit right subtree

    printf("%c ",root->data); // Print data

}

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

Print Simple Binary Search Tree in C

c

printing

binary-tree

binary-search-tree