c - 打印 BST - C 程序

Question

我是 C 新手，正在学习函数和指针。我必须在 t_print 方法中以下面必需的格式打印二叉搜索树，我将非常感激有人可以指导我如何去做。

到目前为止我有这个代码:

typedef struct tree {
  void* data;
  struct tree* left;
  struct tree* right;
} Tree;


/*set the data on the tree node */
void  t_set_data(Tree* t, void* data) {
t->data = data;}

/*let l be the left node of tree *t */
void  t_set_left(Tree* t, Tree* l){
 t->left = l;}

/*let r be the left node of tree *t */
void  t_set_right(Tree* t, Tree* r){
 t->right = r;}

/* simply return left node of the tree */
Tree* t_left(Tree* t){
    return t-> left;}

/* simply return right node of the tree */
Tree* t_right(Tree* t){
    return t-> right;}

/* simply return the data of the tree */
void* t_data(Tree* t){
    return t->data;}

/* make the node of the tree and allocate space for it*/
Tree* t_make(){
    Tree *t = (Tree*)malloc(sizeof(tree));
    t->left=NULL;
    t->right = NULL;
    t-> data = NULL;
    return t;
    }
/* 

print the whole tree in the following format

Root is printed with zero trailing spaces to the left
Every node/subtree is printed with one additional space
Below is an example for a tree with depth 2:

Root
<space>Left-Child
<space><space>Left-Left-Child
<space><space>Left-Right-Child
<space>Right-Child 
     .... and so on ...


Use (void(* p))(function pointer) to print.

 */
void  t_print( Tree* t ,int space, void(* p)(void*) ){
}

Answer 1

这取决于您希望打印数据的顺序，但对于 BST，“按顺序”是合适的(而不是预排序或后排序)。

要“按顺序”打印树，该函数会执行以下操作:

• 如果当前节点不为空
  • 按顺序打印左子树
  • 打印当前节点
  • 按顺序打印右子树

“按顺序打印 xxx 子树”操作是使用左或右指针递归调用“按顺序打印”函数。

预订的算法是:

• 如果当前节点不为空
  • 打印当前节点
  • 打印前序的左子树
  • 打印预序中的右子树

后序的算法是:

• 如果当前节点不为空
  • 按后序打印左子树
  • 按后序打印右子树
  • 打印当前节点

事情就是这么简单。

嗯，几乎就这么简单......

如果您想将数据括起来或以其他方式识别树结构，则必须更加努力。通常，您还会得到一个包含前缀(标识输出的标签)和后缀(可能只是换行符)的 cover 函数；通常，这不是递归打印的一部分。但算法的核心就像描述的那样简单。