c - 工作树遍历程序似乎不起作用

Question

我不熟悉 C 中的树。为了了解更多信息，我搜索并找到了一些不错的示例程序。 http://see-programming.blogspot.in/2013/03/insertion-deletion-and-traversal-in.html我复制并运行了它，效果很好。它的一项功能被称为遍历。其代码如下:

void traverse(struct treeNode *node) {
    if (node != NULL) {
            traverse(node->left);
            printf("%3d", node->data);
            traverse(node->right);
    }
    return;
}

整个程序:

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

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

 struct treeNode *root = NULL;

 /* create a new node with the given data */
 struct treeNode* createNode(int data) {
    struct treeNode *newNode;
    newNode = (struct treeNode *) malloc(sizeof (struct treeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return(newNode);
  }

 /* insertion in binary search tree */
 void insertion(struct treeNode **node, int data) {
    if (*node == NULL) {
            *node = createNode(data);
    } else if (data < (*node)->data) {
            insertion(&(*node)->left, data);
    } else if (data > (*node)->data) {
            insertion(&(*node)->right, data);
    }
  }


  /* deletion in binary search tree */
  void deletion(struct treeNode **node, struct treeNode **parent, int data)     {
    struct treeNode *tmpNode, *tmpParent;
    if (*node == NULL)
            return;
    if ((*node)->data == data) {
            /* deleting the leaf node */
            if (!(*node)->left && !(*node)->right) {
                    if (parent) {
                            /* delete leaf node */
                            if ((*parent)->left == *node)
                                    (*parent)->left = NULL;
                            else
                                    (*parent)->right = NULL;
                            free(*node);
                    } else {
                            /* delete root node with no children */
                            free(*node);
                    }
            /* deleting node with one child */
            } else if (!(*node)->right && (*node)->left) {
                    /* deleting node with left child alone */
                    tmpNode = *node;
                    (*parent)->right = (*node)->left;
                    free(tmpNode);
                    *node = (*parent)->right;
            } else if ((*node)->right && !(*node)->left) {
                    /* deleting node with right child alone */
                    tmpNode = *node;
                    (*parent)->left = (*node)->right;
                    free(tmpNode);
                    (*node) = (*parent)->left;
            } else if (!(*node)->right->left) {
                    /*
                     * deleting a node whose right child
                     * is the smallest node in the right
                     * subtree for the node to be deleted.
                     */

                    tmpNode = *node;

                    (*node)->right->left = (*node)->left;

                    (*parent)->left = (*node)->right;
                    free(tmpNode);
                    *node = (*parent)->left;
            } else {
                    /*
                     * Deleting a node with two children.
                     * First, find the smallest node in
                     * the right subtree.  Replace the 
                     * smallest node with the node to be
                     * deleted. Then, do proper connections
                     * for the children of replaced node.
                     */
                    tmpNode = (*node)->right;
                    while (tmpNode->left) {
                            tmpParent = tmpNode;
                            tmpNode = tmpNode->left;
                    }
                    tmpParent->left = tmpNode->right;
                    tmpNode->left = (*node)->left;
                    tmpNode->right =(*node)->right;
                    free(*node);
                    *node = tmpNode;
            }
    } else if (data < (*node)->data) {
            /* traverse towards left subtree */
            deletion(&(*node)->left, node, data);
    } else if (data > (*node)->data) {
            /* traversing towards right subtree */
            deletion(&(*node)->right, node, data);
    }
  }

  /* search the given element in binary search tree */
  void findElement(struct treeNode *node, int data) {
    if (!node)
            return;
    else if (data < node->data) {
            findElement(node->left, data);
    } else if (data > node->data) {
            findElement(node->right, data);
    } else
            printf("data found: %d\n", node->data);
    return;

   }

   void traverse(struct treeNode *node) {
    if (node != NULL) {
            traverse(node->left);
            printf("%3d", node->data);
            traverse(node->right);
    }
    return;
    }

    int main() {
    int data, ch;
    while (1) {
            printf("1. Insertion in Binary Search Tree\n");
            printf("2. Deletion in Binary Search Tree\n");
            printf("3. Search Element in Binary Search Tree\n");
            printf("4. Inorder traversal\n5. Exit\n");
            printf("Enter your choice:");
            scanf("%d", &ch);
            switch (ch) {
                    case 1:
                            while (1) {
                            printf("Enter your data:");
                            scanf("%d", &data);
                            insertion(&root, data);
                            printf("Continue Insertion(0/1):");
                            scanf("%d", &ch);
                            if (!ch)
                                    break;
                            }
                            break;
                    case 2:
                            printf("Enter your data:");
                            scanf("%d", &data);
                            deletion(&root, NULL, data);
                            break;
                    case 3:
                            printf("Enter value for data:");
                            scanf("%d", &data);
                            findElement(root, data);
                            break;
                    case 4:
                            printf("Inorder Traversal:\n");
                            traverse(root);
                            printf("\n");
                            break;
                    case 5:
                            exit(0);
                    default:
                            printf("u've entered wrong option\n");
                            break;
            }
    }
    return 0;

     }

当我运行该程序时，它运行良好。但是当我分析traverse函数的时候，我就看不懂了。当您从 main 调用遍历函数时，您将根传递给它，就像在这个程序中一样。但是当节点不为 NULL 时，它会继续打印树，因为还有更多数据要打印。但是每次节点不为 NULL 时，行 traverse (node->left); 在打印节点之前再次调用该函数。因此我不明白整棵树是如何打印出来的。如果有人能解释一下，那将会很有帮助。

Answer 1

我们以这个二叉树为例。 binary tree

• 如何打印整棵树？

每次我们调用traverse函数，我们都会打印*node的数据。

遍历过程是一个递归过程，其中处理根节点的函数将调用处理根节点的左子节点和右子节点的函数。例如，traverse(15) 将调用 traverse(5) 和 traverse(16)，而 traverse(5) 将调用 traverse(3) 和 traverse(12)。

递归以叶节点结束，访问并打印每个节点。

• 为什么结果是有序的？

在void traverse(struct treeNode *node)的每次调用中，我们都可以将*node视为子树的根。以下代码表示 *node 的数据在其左子节点返回之前不会被打印。遍历(节点->左)；
printf("%3d", 节点->数据);
遍历(节点->右)；

而traverse(node->left)只有遍历了它的左 child 和右 child 才返回，node->left的 child 也会在*node之前打印。因此，*node 的左子树中的所有节点将在 *node 之前打印，而 *node 的右子树中的所有节点将在其之后打印。

例如，traverse(12) 在打印 12 之前调用 traverse(10)，traverse(10) 调用 traverse(6)，traverse(6) 调用 traverse(7)。由于7是叶子节点，traverse(7)、traverse(6)、traverse(10)依次返回。然后 traverse(12) 打印 12 并调用 traverse(13)。

我们可以得到 6 7 10 12 13 的有序结果