在 C 中表示二叉树的递归函数
Recursive function to represent binary tree in C
问题
我想打印二叉树的节点 inorder
并且希望打印的节点与它们所在的高度一样多,然后是数据。
研究完成
我找到了其他帖子,例如 this one or this one,但我仍然不知道如何以我想要的方式表示我的二叉树,因为它与那些问题中所述的不同。
示例
假设我以这种方式插入带有数据的节点:
5,4,2,3,9,8
表示二叉树时我期望的输出是:
-9
--8
5
-4
---3
--2
玩具示例代码
到目前为止,我能够以正确的顺序打印节点。但几天后,我仍然对如何实现递归函数以获得正确的表示一无所知。我也试过循环,但发现它更混乱,也没有得到正确的结果。
问题是破折号的数量不正确,我不确定我需要在递归中的什么地方附加破折号。我想我可能需要重写整个 printBinaryTreeRecurrsively
代码。
下面是可以整体编译的玩具示例代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct repBinaryTree *BinaryTree;
struct repBinaryTree {
int data;
BinaryTree left;
BinaryTree right;
};
BinaryTree newNode() {
BinaryTree b = new repBinaryTree;
b->data = NULL;
b->left = b->right = NULL;
return b;
}
BinaryTree insertNode(int i, BinaryTree b) {
if (b==NULL) {
b = newNode();
b->data = i;
} else if ( i < b->data ) {
if (b->left == NULL) {
b->left = newNode();
b->left->data = i;
} else {
insertNode(i, b->left);
}
} else if ( i > b->data ) {
if (b->right == NULL) {
b->right = newNode();
b->right->data = i;
} else {
insertNode(i, b->right);
}
}
return b;
}
char* printBinaryTreeRecurrsively(BinaryTree b, char level[]) {
if (b == NULL) {
printf("\n");
return level;
} else {
level = printBinaryTreeRecurrsively(b->right, level);
printf("%s%d",level,b->data);
level = printBinaryTreeRecurrsively(b->left, level);
}
strcat(level,"-");
return level;
}
int main () {
BinaryTree b = insertNode(5,NULL);
b = insertNode(4, b);
b = insertNode(2, b);
b = insertNode(3, b);
b = insertNode(9, b);
b = insertNode(8, b);
printf("Recursive BinaryTree print:");
char level0[] = "";
printBinaryTreeRecurrsively(b, level0);
printf("Expected BinaryTree print:");
printf("\n-9\n--8\n5\n-4\n---3\n--2\n");
}
编译后得到的输出和运行命令行程序如下:
cedric@multivac:~$ g++ printBinaryTree.cpp -o printBinaryTree
cedric@multivac:~$ ./printBinaryTree
Recursive BinaryTree print:
9
8
--5
--4
--3
---2
Expected BinaryTree print:
-9
--8
5
-4
---3
--2
问题
我应该如何重写我的 printBinaryTreeRecurrsively
函数代码以获得正确的输出?
改成这个函数
void printBinaryTreeRecurrsively(BinaryTree b, int level) {
if (b == NULL) {
printf("\n");
} else {
printBinaryTreeRecurrsively(b->right, level+1);
for (int i = 0; i < level; i++) {
printf("-");
}
printf("%d",b->data);
printBinaryTreeRecurrsively(b->left, level+1);
}
}
并以
的身份调用 main()
printBinaryTreeRecurrsively(b, 0);
此方法比担心字符串连接等要简单得多。只需使用 int
跟踪您所在的级别,打印正确的 -
数量,并告诉级别下面再打印一个 -
.
问题
我想打印二叉树的节点 inorder
并且希望打印的节点与它们所在的高度一样多,然后是数据。
研究完成
我找到了其他帖子,例如 this one or this one,但我仍然不知道如何以我想要的方式表示我的二叉树,因为它与那些问题中所述的不同。
示例
假设我以这种方式插入带有数据的节点:
5,4,2,3,9,8
表示二叉树时我期望的输出是:
-9
--8
5
-4
---3
--2
玩具示例代码
到目前为止,我能够以正确的顺序打印节点。但几天后,我仍然对如何实现递归函数以获得正确的表示一无所知。我也试过循环,但发现它更混乱,也没有得到正确的结果。
问题是破折号的数量不正确,我不确定我需要在递归中的什么地方附加破折号。我想我可能需要重写整个 printBinaryTreeRecurrsively
代码。
下面是可以整体编译的玩具示例代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct repBinaryTree *BinaryTree;
struct repBinaryTree {
int data;
BinaryTree left;
BinaryTree right;
};
BinaryTree newNode() {
BinaryTree b = new repBinaryTree;
b->data = NULL;
b->left = b->right = NULL;
return b;
}
BinaryTree insertNode(int i, BinaryTree b) {
if (b==NULL) {
b = newNode();
b->data = i;
} else if ( i < b->data ) {
if (b->left == NULL) {
b->left = newNode();
b->left->data = i;
} else {
insertNode(i, b->left);
}
} else if ( i > b->data ) {
if (b->right == NULL) {
b->right = newNode();
b->right->data = i;
} else {
insertNode(i, b->right);
}
}
return b;
}
char* printBinaryTreeRecurrsively(BinaryTree b, char level[]) {
if (b == NULL) {
printf("\n");
return level;
} else {
level = printBinaryTreeRecurrsively(b->right, level);
printf("%s%d",level,b->data);
level = printBinaryTreeRecurrsively(b->left, level);
}
strcat(level,"-");
return level;
}
int main () {
BinaryTree b = insertNode(5,NULL);
b = insertNode(4, b);
b = insertNode(2, b);
b = insertNode(3, b);
b = insertNode(9, b);
b = insertNode(8, b);
printf("Recursive BinaryTree print:");
char level0[] = "";
printBinaryTreeRecurrsively(b, level0);
printf("Expected BinaryTree print:");
printf("\n-9\n--8\n5\n-4\n---3\n--2\n");
}
编译后得到的输出和运行命令行程序如下:
cedric@multivac:~$ g++ printBinaryTree.cpp -o printBinaryTree
cedric@multivac:~$ ./printBinaryTree
Recursive BinaryTree print:
9
8
--5
--4
--3
---2
Expected BinaryTree print:
-9
--8
5
-4
---3
--2
问题
我应该如何重写我的 printBinaryTreeRecurrsively
函数代码以获得正确的输出?
改成这个函数
void printBinaryTreeRecurrsively(BinaryTree b, int level) {
if (b == NULL) {
printf("\n");
} else {
printBinaryTreeRecurrsively(b->right, level+1);
for (int i = 0; i < level; i++) {
printf("-");
}
printf("%d",b->data);
printBinaryTreeRecurrsively(b->left, level+1);
}
}
并以
的身份调用main()
printBinaryTreeRecurrsively(b, 0);
此方法比担心字符串连接等要简单得多。只需使用 int
跟踪您所在的级别,打印正确的 -
数量,并告诉级别下面再打印一个 -
.