Reputation:
Working tree traversal program seems like it does not work
I was new to trees in C. To learn more, I googled and found some nice example program. http://see-programming.blogspot.in/2013/03/insertion-deletion-and-traversal-in.html I copied it and ran it It worked perfectly. One of its functions was known as traverse. Its code is as follows:
void traverse(struct treeNode *node) {
if (node != NULL) {
traverse(node->left);
printf("%3d", node->data);
traverse(node->right);
}
return;
}
The whole program:
#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;
}
When I ran the program it worked perfectly. But when I analyzed the traverse function, I could not understand it. When you call the traverse function from the main, you pass the root to it as in this program. But when the node is not NULL, it continues printing the tree as more data is left to print. But every time the node is not NULL, the line traverse (node->left); calls the function once again before printing the node. Thus I do not understand how the whole tree gets printed. It would be helpful if someone could explain.
Upvotes: 1
Views: 265
Answers (1)
Reputation: 71
Let's take this binary tree as an example. binary tree
- How the whole tree gets printed?
Each time we call traverse function, we will print the data of *node.
Traverse process is a recursive process in which functions dealing with root node will call functions dealing with root's left-child and right-child. For example, traverse(15) will call traverse(5) and traverse(16), and traverse(5) will call traverse(3) and traverse(12).
Recuration ends with leaf nodes and every node is visited and printed.
- Why the result is in-order?
In each call of void traverse(struct treeNode *node), we could regard *node as the root of a subtree. Following codes mean data of *node won't be printed until recurse of its left-child returns.
traverse(node->left);
printf("%3d", node->data);
traverse(node->right);
And traverse(node->left) returns only when its left-child and right-child are traversed, childs of node->left will also printed before *node. So, all nodes in left sub-tree of *node will be printed before *node, and all nodes in right sub-tree of *node will be printed after it.
For example, traverse(12) calls traverse(10) before print 12, traverse(10) calls traverse(6) and traverse(6) calls traverse(7). Since 7 is a leaf node, traverse(7), traverse(6) and traverse(10) returns in order. Then traverse(12) print 12 and calls traverse(13).
We could get in-order result of 6 7 10 12 13
Upvotes: 3
Related Questions
- Tree traversal - Segmentation fault error
- C - recursion not working in a Binary Search Tree
- How do I modify my tree traversal program that I wrote in C so that it doesn't rely on recursion?
- Recursive Functions in Tree Problems
- Recursive tree traversal
- Recursive Binary Tree
- Tree recursion compiles, but crashes on execution
- Tree + Recursion
- Need clarification where I am wrong with tree traversal results
- Tree traversal, Recursion