| Line 283: | Line 283: | ||
else return Tree_search(node->right,value); | else return Tree_search(node->right,value); | ||
} | } | ||
| + | This function searches for a node having a given value. If the BST does not exist then it returns NULL. If node has been found it returns it. If the value of the node is less than the passed value then it begins to search to the left side of it. If the value passed in the function is greater than the value of the node then it progresses to the right side of the node. Since this is a recursive function this process keeps on happening till node value becomes equal to the passed value. This as mentioned above will return the node. | ||
/*void *Tree_postorder(TreNode *node) | /*void *Tree_postorder(TreNode *node) | ||
Revision as of 20:00, 7 May 2012
Shiyu Wang Lec28 April 27th
typedef struct treenode {
struct treenode *left; struct treenode *right; int value;
}Node;
Node* root=NULL;
root=tree_insert(root,13);
root=tree_insert(root,7);
root=tree_insert(root,22);
Node*Tree_insert(Node*n,int v) {
if(n==NULL)
{
return Node_construct(v);
}
if((n->value)==v)
{
return n;
}
if((n->value)>v)
{
n->left=Tree_insert(n->left,v);
}
else
{
n->right=Tree_insert(n->right,v);
}
return n;
}
Contents
=========================================================
Huayi Guo section-1 Professor Niklas lecture 28
- /
- include<stdio.h>
- include<stdlib.h>
- include<string.h>
typedef struct TreeNode_t{
int value; struct TreeNode_t *left, *right;
}TreeNode;
TreeNode *Tree_create(int value) {
TreeNode *node = malloc(sizeof(Treenode));
node->value = value;
node->left = NULL;
node->right= NULL;
return node;
}
TreeNode *Tree_insert(TreeNode * node, int value) {
if(node == NULL) return TreeNode_create(value);
if(node->value >=value){
node->left = Tree_insert(node->left,value); } else node->right = Tree_insert(node->right,value);
return node;
} void *Tree_inorder(TreNode *node) {
if(node==NULL)return ;
Tree_inorder(node->left);
printf("%d\n",node->value);
Tree_inoder(node->right);
}
void *Tree_preorder(TreNode *node) {
if(node==NULL)return node;
printf("%d\n",node->value);
Tree_inorder(node->left);
Tree_inoder(node->right);
}
TreeNode *Tree_search(TreeNode *node,int value) {
if(node == NULL)return NULL; if(node->value ==)return node; if(node->value < value)return Tree_search(node->left,value); else return Tree_search(node->right,value);
}
/*void *Tree_postorder(TreNode *node) {
if(node==NULL)return node;
Tree_inorder(node->left);
Tree_inoder(node->right);
printf("%d\n",node->value);
}*/
void Tree_destroy(TreNode *node)
{
if(node==NULL)return; Tree_destroy(node->left);
Tree_destroy(node->right); free(node); }
int main(int argc, char *argv[]) {
if(argc != 3){
return EXIT_FAILURE; }
FILE *f = fopen(argv[1],"r");
if(f ==NULL){ return EXIT_FAILURE; }
int num;
while(fscanf(f, "%d",&num) == 1){ root = Tree_insert(root, num); }
fclose(f);
Tree_inorder(root); Tree_destroy(root);
return EXIT_SUCCESS; }
========================================
Wudi Zhou, Professor Lu's section, April 30th
typedef struct treenode {
struct treenode *left; struct treenode *right; int value;
}Node;
Node* root=NULL;
root=tree_insert(root,13);
root=tree_insert(root,7);
root=tree_insert(root,22);
Node*Tree_insert(Node*n,int v) {
if(n==NULL)
{
return Node_construct(v);
}
if((n->value)==v)
{
return n;
}
if((n->value)>v)
{
n->left=Tree_insert(n->left,v);
}
else
{
n->right=Tree_insert(n->right,v);
}
return n;
}
=======================================
Hanye Xu May 2nd
In this lecture, the detail of binary tree are introduced.
typedef struct treenode {
struct treenode *left; struct treenode *right; int value;
}Node;
Node* root=NULL;
root=tree_insert(root,13);
root=tree_insert(root,7);
root=tree_insert(root,22);
Node*Tree_insert(Node*n,int v) {
if(n==NULL)
{
return Node_construct(v);
}
if((n->value)==v)
{
return n;
}
if((n->value)>v)
{
n->left=Tree_insert(n->left,v);
}
else
{
n->right=Tree_insert(n->right,v);
}
return n;
}
=============
Rohan Khante
=============
typedef struct TreeNode_t{
int value; struct TreeNode_t *left, *right;
}TreeNode; Declared in header file. Every node has two pointers. and a value
TreeNode *Tree_create(int value) {
TreeNode *node = malloc(sizeof(Treenode));
node->value = value;
node->left = NULL;
node->right= NULL;
return node;
} Since one is interested in obtaining a node we need to return a TreeNode. This will malloc space equal to the struct TreeNode. Left and Right pointers are initialized to NULL since we do not want them to point to anything yet. The value is stored inside the value
TreeNode *Tree_insert(TreeNode * node, int value) {
if(node == NULL) return TreeNode_create(value);
if(node->value >=value){
node->left = Tree_insert(node->left,value); } else node->right = Tree_insert(node->right,value);
return node;
} This function is a recursive function. If node doesnt exist then node is created. If node has a value greater than the passes value then the function goes to the child of the node and checks there. It keeps there till it reaches a place where there is no node and creates a node. Same goes for the right side. The node is then finally returned. This ensures that the format of the BST is maintained. The elements of the node on the left hand side are smaller and the ones on the right side are greater than the parent node.
void *Tree_inorder(TreNode *node)
{
if(node==NULL)return ;
Tree_inorder(node->left);
printf("%d\n",node->value);
Tree_inoder(node->right);
}
The inorder listing of T is the nodes of T1 in inorder, followed by the root r, followed by the nodes of T2 in inorder, . . . , and the nodes of Tk in inorder.
void *Tree_preorder(TreNode *node) {
if(node==NULL)return node;
printf("%d\n",node->value);
Tree_inorder(node->left);
Tree_inoder(node->right);
}
The preorder listing of T is the root of T, followed by the nodes of T1 in preorder, . . . , and the nodes of Tk in preorder.
TreeNode *Tree_search(TreeNode *node,int value) {
if(node == NULL)return NULL; if(node->value ==)return node; if(node->value < value)return Tree_search(node->left,value); else return Tree_search(node->right,value);
} This function searches for a node having a given value. If the BST does not exist then it returns NULL. If node has been found it returns it. If the value of the node is less than the passed value then it begins to search to the left side of it. If the value passed in the function is greater than the value of the node then it progresses to the right side of the node. Since this is a recursive function this process keeps on happening till node value becomes equal to the passed value. This as mentioned above will return the node.
/*void *Tree_postorder(TreNode *node) {
if(node==NULL)return node;
Tree_inorder(node->left);
Tree_inoder(node->right);
printf("%d\n",node->value);
}*/ The postorder listing of T is the nodes of T1 in postorder, . . . , the nodes of Tk in postorder, all followed by the root r.
void Tree_destroy(TreNode *node) {
if(node==NULL)return; Tree_destroy(node->left);
Tree_destroy(node->right); free(node); } Again a recursive function. It checks if the BST exists or not. Then it starts from the node passed to it as a parameter. Then proceeds to destroy the tree on the left side of it and then changes to right side. The node is freed every time.
