c programming code related to bfs and dfs?

Question

A ...Depth=1,1st level bfs/dfs
/|\
/ | \
/ | \
B C D(D HAS 2 CHILDREN I AND J) ....Depth=2,level 2,first do bfs
/| |\ \\ Breadth=2,level 2,do dfs(right branch to left branch)
/ | | \ \\
/ | | \ \\
E F G H IJ(J HAS 1 CHILD O)
/ | / | | .......depth=3,level 3,first do bfs
/ | / | | breadth=3,level 3,do dfs(right to left)
K L M N O ....depth=4,level 4,first do bfs
/| breadth=4,level 4,do dfs(right to left)
/ |
/ |
P Q
the tree has total 17 nodes(A to Q)
the edges are A B,A C,A D,B E,B F,C G,C H,D I,D J,E K,E L,H M,H N,J O,L P,L Q.





Here,the dfs search will be carried out in the opposite of the normal convention i.e. from right to left.
The first level(level 1) will search as bfs/dfs(searching in this level won matter since the level has only 1 node A).Next in level 2,it will first search in bfs fashion and will print BCD,then it will search this level in dfs fashion and it will print JO.In the next level(level 3),same procedure will be followed,the level will be first searched in bfs manner and it will print EFGHI,then it will be searched in dfs manner and it will print NM.Same process will be followed in level 4 and it will print KL for bfs and PQ for dfs.It is to be noted that once one of the nodes are searched in bfs/dfs,they are not to be considered for the next level's search,like when in level 3,we get EFGHI whilesearching in bfs,but we dont consider J since it is already visited in the previous level's dfs search.



the program will print

A-BCD-JO-EFGHI-NM-KL-QP

Answer 1

Please check my links for some great material on depth-first and breadth-first searching, and binary trees and linked lists in general.



The answer is to make two recursive functions, depthFirst and breadthFirst. Each of these takes a pointer to a node and a pointer to a string as arguments. The escape condition on both is being passed a null pointer instead of a node.



The difference is that with the breadth first function, (at least, this is the way I would do it since I'm already using a binary tree which is easy to turn into a linked list) the top level nodes are arranged into a modified doubly linked list. One node pointer goes horizontally across, and the other contains the node originally stored in the binary search tree. A new list is then created for the next level down, and passed to the function recursively as normal.



You can use the same node object in both cases; the depthFirst node will simply have one of its two node pointers set to null since ordinary recursion can hit every node on the tree only once.



So the prototype for either function is



char *depthFirst(struct Node *node, char *output)

{

char *buff;

struct Node *next;



if(node == NULL)

return output;



/* glue output to retrieved strings here */



/* build any lists and recur here */

}



Note: Technically it's possible to hit things in breadth-first order and use an ordinary binary tree; the trick at that point is to handle gluing the output strings together after recursion and after the substrings have been retrieved. But I find the way I suggested is a lot easier to map mentally and understand. I also feel it's more time efficient, although I haven't attempted to prove this, because on most computers string operations take longer than reassigning pointers, and doing things with an ordinary binary tree would nearly double the number of string operations.

Answer 2

Like some mentioned, you are able to grow to be a competent utility developer in any language. regardless of the undeniable fact that, i could advise going in direction of the languages like C++, C#, and Java that employers seek for.

Answer 3

include

void mind()

{

printf("i have no idea what this **** is xD")

};

byebye()

now go sleep :P