工作树遍历程序似乎不起作用
Working tree traversal program seems like it does not work
我不熟悉 C 中的树。为了了解更多信息，我搜索并找到了一些不错的示例程序。 http://see-programming.blogspot.in/2013/03/insertion-deletion-and-traversal-in.html 我复制了它 运行 它完美地工作了。它的一项功能被称为 traverse。其代码如下：
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); 在打印节点之前再次调用该函数。因此我不明白整棵树是如何打印出来的。如果有人能解释一下会很有帮助。
我们以这棵二叉树为例。
binary tree
- 如何打印整棵树？
每次调用traverse函数，都会打印*node的数据。
遍历过程是一个递归过程，处理根节点的函数会调用处理根节点的left-child和right-child的函数。例如，traverse(15) 将调用 traverse(5) 和 traverse(16)，而 traverse(5) 将调用 traverse(3) 和 traverse(12)。
递归以叶节点结束，访问并打印每个节点。
- 为什么结果是in-order？
在void traverse(struct treeNode *node)的每一次调用中，我们都可以把*node当作一棵子树的根。以下代码表示 *node 的数据在其 left-child returns 递归之前不会被打印。
traverse(node->left);
printf("%3d", node->data);
traverse(node->right);
而遍历(node->left) returns只有遍历其left-child和right-child时，node->left的childs也会打印在*node之前。因此，*node 左侧 sub-tree 中的所有节点将在 *node 之前打印，而 *node 右侧 sub-tree 中的所有节点将在其之后打印。
例如traverse(12)在打印12之前调用traverse(10)，traverse(10)调用traverse(6)，traverse(6)调用traverse(7)。由于7是叶子节点，依次遍历(7)、遍历(6)、遍历(10)returns。然后 traverse(12) 打印 12 并调用 traverse(13)。
我们可以得到 in-order 结果 6 7 10 12 13
我不熟悉 C 中的树。为了了解更多信息，我搜索并找到了一些不错的示例程序。 http://see-programming.blogspot.in/2013/03/insertion-deletion-and-traversal-in.html 我复制了它 运行 它完美地工作了。它的一项功能被称为 traverse。其代码如下：
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); 在打印节点之前再次调用该函数。因此我不明白整棵树是如何打印出来的。如果有人能解释一下会很有帮助。
我们以这棵二叉树为例。 binary tree
- 如何打印整棵树？
每次调用traverse函数，都会打印*node的数据。
遍历过程是一个递归过程，处理根节点的函数会调用处理根节点的left-child和right-child的函数。例如，traverse(15) 将调用 traverse(5) 和 traverse(16)，而 traverse(5) 将调用 traverse(3) 和 traverse(12)。
递归以叶节点结束，访问并打印每个节点。
- 为什么结果是in-order？
在void traverse(struct treeNode *node)的每一次调用中，我们都可以把*node当作一棵子树的根。以下代码表示 *node 的数据在其 left-child returns 递归之前不会被打印。
traverse(node->left);
printf("%3d", node->data);
traverse(node->right);
而遍历(node->left) returns只有遍历其left-child和right-child时，node->left的childs也会打印在*node之前。因此，*node 左侧 sub-tree 中的所有节点将在 *node 之前打印，而 *node 右侧 sub-tree 中的所有节点将在其之后打印。
例如traverse(12)在打印12之前调用traverse(10)，traverse(10)调用traverse(6)，traverse(6)调用traverse(7)。由于7是叶子节点，依次遍历(7)、遍历(6)、遍历(10)returns。然后 traverse(12) 打印 12 并调用 traverse(13)。
我们可以得到 in-order 结果 6 7 10 12 13