0

给定下图所示的二叉树，假设调用函数 A(root)，确定访问下图所示二叉树节点的顺序。假设树节点和指针的定义如图所示。假设 root 是一个指向包含 60 的节点的指针。 我对这个问题的回答如下。这是正确的吗？我做错什么了？

                                   60
                                 /    \
                                30     90
                               /  \   / 
                              5   38  77
                               \  /  / \
                               8 32 62  88



struct treeNode{
  int data;
  struct treeNode *left, *right:
  {

struct treeNode *tree_ptr;

void A(struct treeNode *node_ptr){
    if (node_ptr != NULL){
    printf(“%d ,”,node_ptr->data);
    B(node_ptr->left);
    B(node_ptr->right);
   }   
}

void B(struct treeNode *node_ptr){
    if (node_ptr != NULL) {
    A(node_ptr->left);
    printf(“%d ,”,node_ptr->data);
    A(node_ptr->right);
   }
 }

答案： 在 void A 中，它说首先打印 node_ptr-> data 所以打印 60 然后函数调用 B(node_ptr->left) 然后在 B 内，调用 A (node_ptr->left) 然后打印该数据是 5 . 然后调用 A(node_ptr->right) 返回到 A，打印该数据，以便打印 8。现在我不太确定下一步该做什么，但从逻辑上讲，打印 30 是有意义的，但我不确定 ptr 如何从 8 变为 30。然后如果你继续以相同的模式打印 38 并打印 32。对于右子树... 90 77 62 88

4

4 回答 4

1

对于初学者，您的代码中有很多错误。我猜它应该更像这样：

struct treeNode{
  int data;
  struct treeNode *left, *right;
}

treeNode *tree_ptr;

void A(treeNode *node_ptr){
    if (node_ptr != NULL){  /// this could be just if(node_ptr)
        printf(“%d ,”,node_ptr->data);
        B(node_ptr->left);
        B(node_ptr->right);
    }   
}

void B(treeNode *node_ptr){
    if (node_ptr != NULL) {
        A(node_ptr->left);
        printf(“%d ,”,node_ptr->data);
        A(node_ptr->right);
    }
}

您还混合了两种不同的遍历算法。A()是预购的，B()是有序的。A()并且B()应该称呼自己，而不是彼此。A（使用真实变量/函数名称而不是,等的另一个原因B。）

于 2010-12-14T21:11:47.470 回答
1

只需随着时间的推移写出完整的执行堆栈。像这样：

A(60)
  printf
  B(30)
    A(5)
      ...
    printf
    A(38)
      ...
  B(90)
    ...

（树的其余部分留给读者作为练习。）

然后从上到下，写下 printf 语句的结果。

于 2010-12-14T21:14:18.883 回答
1

A是前序遍历，而B是中序遍历。

确定打印顺序的一种简单方法是查看您如何访问节点本身。我通常在树的外部画一个轮廓（从根开始，根据你首先遍历的子树向左或向右移动）。如果我正在进行预购遍历，我会在沿其外部移动时打印出一个节点。如果我正在执行按顺序遍历，则仅当我在它下方移动时才打印出一个节点（当您查看按顺序遍历时，这是有道理的，因为您最终会先打印叶子；它们是您移动的第一个节点在你画轮廓的时候）。如果我正在执行后序遍历，则仅当我沿着其内部移动时才打印出一个节点。

更新

在 5 和 8 之后打印出 30 的原因是您没有执行纯粹的前序遍历。你在预购和有序遍历之间跳跃。

找出顺序的一种简单方法是在跟踪代码时实际写下代码所经历的步骤（我经常使用钢笔/铅笔和纸将信息保持在一起）。例如，您可以写出这样的调用堆栈：

A(60)
  printf(60)
  call B(60.left)
    B(30)
      call A(30.left)
        A(5)
          printf(5)
          call B(5.left)
            B(null)
          call B(5.right)
            B(8)
              call A(8.left)
                A(null)
              printf(8)
              call A(8.right)
                A(null)
      printf(30)
      call A(30.right)
        A(38)
        ...

你可以很容易地看到节点的打印顺序，更重要的是，为什么你从打印 8 跳到打印 30（一个递归调用已经结束，你正在回退一级）。

于 2010-12-14T21:15:18.850 回答
1

对于 Pre-order 或 In-order Pre - 60、30、5、8 35 32 等 In - 5、8、30、32、35 等，上述跟踪不能正确。

于 2011-03-28T08:59:36.530 回答