c - 如何打印二叉树？

Question

我创建了一个程序，它基本上有一个二叉树，我可以在其中删除/插入节点。我也可以计算它的遍历，但我想以真实的形式打印树。我的意思是。程序现在打印:1 2 3 4

我要打印:

       1    
     /   \
    2     3  
   /   
  4

这当然是可行的，但我时间有限。请提供此问题的解决方案。 (是的，我知道要求解决方案很多)。在我的代码中，我对调用打印结果的函数的行进行了注释。评论看起来像这样“//我想将其打印为一棵树”这些是计算和打印树的行。我想要的只是让它们打印出一棵真正的树。

我的代码:

#include<stdlib.h>
#include<stdio.h>
struct node1
{
    int key1;
    struct node1 *left1, *right1;
};

// A utility function to create a new BST node1
struct node1 *newnode1(int item)
{
    struct node1 *temp1 =  (struct node1 *)malloc(sizeof(struct node1));
    temp1->key1 = item;
    temp1->left1 = temp1->right1 = NULL;
    return temp1;
}

// A utility function to do inorder traversal of BST
void inorder(struct node1 *root1)
{
    if (root1 != NULL)
    {
        inorder(root1->left1);
        printf("%d ", root1->key1);
        inorder(root1->right1);
    }
}

/* A utility function to insert1 a new node1 with given key1 in BST */
struct node1* insert1(struct node1* node1, int key1)
{
    /* If the tree is empty, return a new node1 */
    if (node1 == NULL) return newnode1(key1);

    /* Otherwise, recur down the tree */
    if (key1 < node1->key1)
        node1->left1  = insert1(node1->left1, key1);
    else
        node1->right1 = insert1(node1->right1, key1);

    /* return the (unchanged) node1 pointer */
    return node1;
}

/* Given a non-empty binary search tree, return the node1 with minimum
   key1 value found in that tree. Note that the entire tree does not
   need to be searched. */
struct node1 * minValuenode1(struct node1* node1)
{
    struct node1* current = node1;

    /* loop down to find the left1most leaf */
    while (current->left1 != NULL)
        current = current->left1;

    return current;
}

/* Given a binary search tree and a key1, this function deletes the key1
   and returns the new root1 */
struct node1* deletenode1(struct node1* root1, int key1)
{
    // base case
    if (root1 == NULL) return root1;

    // If the key1 to be deleted is smaller than the root1's key1,
    // then it lies in left1 subtree
    if (key1 < root1->key1)
        root1->left1 = deletenode1(root1->left1, key1);

    // If the key1 to be deleted is greater than the root1's key1,
    // then it lies in right1 subtree
    else if (key1 > root1->key1)
        root1->right1 = deletenode1(root1->right1, key1);

    // if key1 is same as root1's key1, then This is the node1
    // to be deleted
    else
    {
        // node1 with only one child or no child
        if (root1->left1 == NULL)
        {
            struct node1 *temp1 = root1->right1;
            free(root1);
            return temp1;
        }
        else if (root1->right1 == NULL)
        {
            struct node1 *temp1 = root1->left1;
            free(root1);
            return temp1;
        }

        // node1 with two children: Get the inorder successor (smallest
        // in the right1 subtree)
        struct node1* temp1 = minValuenode1(root1->right1);

        // Copy the inorder successor's content to this node1
        root1->key1 = temp1->key1;

        // Delete the inorder successor
        root1->right1 = deletenode1(root1->right1, temp1->key1);
    }
    return root1;
}
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right); // i want to print this as a tree
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data); 
    }
}

void deltree(node * tree)
{
    if (tree)
    {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        return NULL;
    }

    if(val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return *tree;
    }
}

void main()
{
    node *root;
    node *tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);
    insert(&root, 0);
    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root); // i want to print this as a tree

    printf("In Order Display\n"); 
    print_inorder(root); // i want to print this as a tree

    printf("Post Order Display\n");
    print_postorder(root); // i want to print this as a tree
    /* Search node into tree */
    tmp = search(&root, 4);
    if (tmp)
    {
        printf("Searched node=%d\n", tmp->data);
    }
    else
    {
        printf("Data Not found in tree.\n");
    }
 struct node1 *root1 = NULL;      // these
    root1 = insert1(root1, 50);// lines
    root1 = insert1(root1, 30);// delete a
    root1 = insert1(root1, 20);//node
    root1 = insert1(root1, 40);//and
    root1 = insert1(root1, 70);//then prints 
    root1 = insert1(root1, 60);//it 
    root1 = insert1(root1, 80);//
    root1 = deletenode1(root1, 50);    //
    inorder(root1);  // i want to print this as a tree
    /* Deleting all nodes of tree */
    deltree(root);
}

Answer 1

问题是您需要有 2^maxDepth 方框才能正确绘制节点。

在 (0,(2^maxDepth)/2) 点绘制根，并且后续子节点位于 ((1,(父节点位置)/2), ((父节点位置)/2, 1) 位置。

考虑下面的示例代码。

int maxDepth(node* node)  
{ 
   if (node==NULL)  
       return 0; 
   else 
   { 
       /* compute the depth of each subtree */
       int lDepth = maxDepth(node->left); 
       int rDepth = maxDepth(node->right); 

       /* use the larger one */
       if (lDepth > rDepth)  
           return(lDepth+1); 
       else return(rDepth+1); 
   } 
}

void drawTree(node *node)
{
   int maxdepth = maxDepth(node);
   int numSpace = pow(2,maxdepth)+1;
    int i = 0;

    for (i = 0;i < maxdepth;i++)
    {
        printGraph(node, numSpace, 1, i, 0);
        numSpace /=2;

        printf("\n");
     }

}

int printGraph(node *node, int numSpace,int isLeft, int expectedLevel, int currentLevel)
{


   int i = 0;

   if (node == NULL || currentLevel > expectedLevel)
    {
     for (i = 0;i<(numSpace)/2;i++) printf(" ");
     return -1;
    }

   if (expectedLevel == currentLevel)
   {
      for (i = 0;i<(numSpace)/2;i++) printf(" ");
      printf("%d", node->data);

   }
   else
   {

      printGraph(node->left, numSpace, 1, expectedLevel, currentLevel+1);

     for (i = 0;i<(numSpace)/2;i++) printf(" ");

        printGraph(node->right, (numSpace), 0, expectedLevel, currentLevel+1);


     return ret;

   }
}

我从 main 调用 drawTree，如下所示。

void main()
{
    node *root;
    node *tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);
insert(&root, 0);

insert(&root, 7);
insert(&root, 16);
    insert(&root, 18);

drawTree(root);

    deltree(root);
}

示例输出:

        9
    4        15
  2    6    12    17
 0      7      16  18

Note: Now go ahead with adding edges to the nodes with the same approach.