C语言-具有递归功能的二叉树，打印 "node connection"

Question

我的代码的一部分被困住了。我应该接受必须放入二叉树中的所有元素并对它们进行排序，这工作正常，如果我采用 6, 5, 4, 3, 2, 1，它会将 3 打印为root，然后是 1、2、4、5，然后是 6，因为这就是递归函数应该如何工作(必须使用代码中提到的函数)，这是正确的。我的问题是我不确定如何使用指针并打印哪些指针是“连接的”。例如这样的事情就足够了:节点 - 3， parent - 无， child - 1 和 5节点 - 5，父节点 - 3，子节点 - 4 和 6

我对所有想法持开放态度。

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


typedef struct _node
{
int data;
struct _node *left;
struct _node *right;

}node;

node* newnode(int a)
{
node *p;

p=(node*)malloc(sizeof(node));

p->data = a;

printf("%d\n", p->data);

p->left = NULL;
p->right = NULL;

return p;
};

void MakeBalTree(int *x, int left, int right)
{
int middle;

if (left <= right)
{
    middle = (left + right)/2;
    newnode(x[middle]);
}

if(left>right)
    return;

MakeBalTree (x, left, middle-1);
MakeBalTree (x, middle+1, right);
}

void sort(int *x, int count)
{
int i, j, tmp;

for (i = 0; i < count - 1; i++)
{
    for (j = i + 1; j < count; j++)
    {
        if (x[i] > x[j])
        {
            tmp = x[i];
            x[i] = x[j];
            x[j] = tmp;
        }
    }
}
}

int main()
{
int i, j;
int count = 0;
int *x = NULL;
char c;

do{
    printf("Enter a number:");
    scanf("%d", &i);
    count++;

    x = (int*)realloc(x, count * sizeof(int));
    x[count-1]=i;

    printf("Enter more numbers (y/n)? \n");
    scanf(" %c", &c);

    if(c=='y')
        continue;
    if(c=='n')
        sort(x, count);
    else while(c != 'y' && c !='n')
    {
        printf("Wrong character, please enter again:");
        scanf(" %c", &c);
    }
}while(c=='y');

MakeBalTree(x, 0, count-1);

free(x);

return 0;

}

Answer 1

忽略排序等方面的任何其他内容。打印二叉树的方法是遍历树，向下移动时打印每个节点。 最简单的方法是使用递归。例如

void printTree (node* root, node* parent)
{
    if (parent == NULL) {
        printf("Node - %d, parent - none, children ", root->data);
    } else {
        printf("Node - %d, parent - %d, children ", root->data, parent->data);
    }
    if (root->left != NULL && root->right != NULL) {
        printf("%d and %d\n", root->right->data, root->left->data);
    } else if (root->left == NULL && root->right != NULL) {
        printf("%d\n", root->right->data);
    } else if (root->left != NULL && root->right == NULL) {
        printf("%d\n", root->left->data);
    } else {
        printf("none\n");
    }

    if (root->left != NULL)
        printTree(root->left, root);
    if (root->right != NULL)
        printTree(root->right, root);
}

// Calling
printTree(&root, NULL);

这不是最好的方法，它本身可以优化，一般来说最好执行迭代中序遍历。您可以找到一个示例 here 。要点是:

1) Create an empty stack S.

2) Initialize current node as root

3) Push the current node to S and set current = current->left until current is NULL

4) If current is NULL and stack is not empty then

a) Pop the top item from stack.

b) Print the popped item, set current = popped_item->right

c) Go to step 3.

5) 如果 current 为 NULL 并且堆栈为空，那么我们就完成了。