QuestionAnswered step-by-stepNeed help implementing these codes in c. Binary tree knowledge./**generate_levelBF*Generate the next level of the tree in a breadth-first manner*Pre-condition: the given tree is defined, the given queue* is defined*Post-condition: an additional level of possible moves has*been added to the given game tree and each*tree node of the new level also has been*added to the queue.*Informally: generate the next level of the game tree**param q Queue of reachable but unexpanded game trees*/void generate_levelBF(game_tree t, queue q){COMPLETE ME!}/**build_gameBF*Generate the game tree in a breadth-first manner*Pre-condition: the given queue and game tree are defined, and* the given int value represents the desired depth* of the tree*Post-condition: If the given tree isn’t already deep enough, an*additional level of possible moves is added to*the given game tree and each tree node of the*new level also is added to the queue.*Finally, the next tree is determined by removing*the front of the queue and the process continues*until the queue is empty*Informally: generate the game tree from the current point*in a breadth-first manner until it is “d” levels*deep**param q Queue of reachable but unexpanded game trees*param d desired depth (number of queens) that game tree should be built to*returnthe game tree with the first found solution, or an empty game*tree if there is no solution*/game_tree build_gameBF(game_tree t, queue q, int d){COMPLETE ME!}/**generate_levelDF*Generate the next level of the tree in a depth-first manner*Pre-condition: the given tree is defined, the given stack* is defined*Post-condition: an additional level of possible moves has*been added to the given game tree and each*tree node of the new level also has been*added to the stack.*Informally: generate the next level of the game tree**param q Stack of reachable but unexpanded game trees*/void generate_levelDF(game_tree t, stack s){COMPLETE ME!}/**build_gameDF*Generate the game tree in a depth-first manner*Pre-condition: the given stack and game tree are defined, and* the given int value represents the desired depth* of the tree*Post-condition: If the given tree isn’t already deep enough, an*additional level of possible moves is added to*the given game tree and each tree node of the*new level also is pushed onto the stack.*Finally, the next tree is determined by removing*the top of the stack and the process continues*until the stack is empty*Informally: generate the game tree from the current point*in a depth-first manner until it is “d” levels*deep**param s Stack of reachable but unexpanded game trees*param d desired depth (number of queens) that game tree should be built to*returnthe game tree with the first found solution, or an empty game*tree if there is no solution*/game_tree build_gameDF(game_tree t, stack s, int d){COMPLETE ME!}// typesstruct game_state_int {square_state board[DIMENSION][DIMENSION];};/**init_game_state*initialiser function.*Pre-condition: none*Post-condition: a game_state variable is created and pointed*to by the first parameter. Each element in*the board table is created empty*Informally: creates an initial game_state*/void init_game_state(game_state *gp){trace(“game_state: initialiser starts”);*gp=(game_state)malloc(sizeof(struct game_state_int));for(int i = 0; i < DIMENSION; i++){//ROWfor(int j = 0; j < DIMENSION; j++){//COLUMN//(*gp)->board[i][j] =init_square_state(&(*gp)->board[i][j], i, j);}}}/** get_square*Get function for a square_state.*Pre-condition: the given coordinate is within the bounds of the board*Post-condition: the value of the indicated square_state variable*is returned*Informally: return the square_state in the game_state variable’s board**Param int r the row component of the desired square’s coordinate*Param int c the column component of the desired square’s coordinate**return square_state the nominated square_state*/square_state get_square(game_state g, int r, int c){trace(“get_square: get_square starts and finishes”); return (g->board[r – 1][c – 1]);}/** set_square*Set function for a square_state.*Pre-condition: the given square_state value is defined and is within the* dimension of the board array*Post-condition: the square of the board at the given coordinate is updated*to the given square_state value*Informally: update the game_state board variable’s element to the given value**Param set_square s value to be placed into the game_state’s board field*/void set_square(game_state g, square_state s){ int r, c;// row and column of given square_statetrace(“set_square: set_square starts”);r = get_row(s);c = get_column(s);g->board[r – 1][c – 1] = s;trace(“set_square: set_square ends”);}/** valid*Check whether a square is on the board*Pre-condition: the given game_state is defined*Post-condition: true is returned if (r,c) is within the bounds*of the given game_state variable’s board field,*and false is returned otherwise*Informally: Return whether or not a square is on the board**Param r int row value to check*Param c int column value to check**return bool whether the coordinate is on the board*/bool valid(game_state g, int r, int c){if(g->board[r – 1][c – 1] != NULL){return true;} else{return false;}}/** row_clear*Check whether the indicated row is clear on the given board*Pre-condition: the given game_state is defined and the given row* number is within the board of the given game_state*Post-condition: true is returned if row r contains no queens, and*false is returned otherwise*Informally: Return whether or not a row is clear of queens**Param r int row value to check**return bool whether the row is clear*/bool row_clear(game_state g, int r){ int x;int y;trace(“row_clear: row_clear starts”);x = 0;y = r;while ((x <= DIMENSION) ){ if (taken(g, x, y)){trace("row_clear: row_clear finishes with false"); return false;}x++;}}/** column_clear*Check whether the indicated column is clear on the given board*Pre-condition: the given game_state is defined and the given* column number is within the board of the given* game_state*Post-condition: true is returned if column c contains no queens,*and false is returned otherwise*Informally: Return whether or not a column is clear of queens**Param c int column value to check**return bool whether the column is clear*/bool column_clear(game_state g, int c){ int x;int y;trace("column_clear: column_clear starts");x = c;y = 0;while ((y <= DIMENSION) ){ if (taken(g, x, y)){trace("column_clear: column_clear finishes with false"); return false;}y++;}}/** diagonals_clear*Check whether the diagonals from the given coordinate are clear*on the given board*Pre-condition: the given game_state is defined and the given row* and column numbers are within the board of the* given game_state*Post-condition: true is returned if the diagonals centered at*the given coordinate contain no queens, and*false is returned otherwise*Informally: Return whether or not the diagonals of a given*coordinate are clear of queens**Param r int row value for coordinate*Param c int column value for coordinate**return bool whether the diagonals are clear*/bool diagonals_clear(game_state g, int r, int c){ int x, y;// row and column of given game_statetrace("diagonals_clear: diagonals_clear starts");x = r;y = c; while ((x > 1) && (y > 1)){x–;y–;}trace(“diagonals_clear: found top left”); while ((x <= DIMENSION) && (y <= DIMENSION)){ if (taken(g, x, y)){trace("diagonals_clear: diagonals_clear finishes with false"); return false;}x++;y++;}trace("diagonals_clear: diagonals_clear left diagonal clear");x = r;y = c; while ((x > 1) && (y < DIMENSION)){x--;y++;}trace("diagonals_clear: found top right"); while ((x <= DIMENSION) && (y <= DIMENSION)){ if (taken(g, x, y)){trace("diagonals_clear: diagonals_clear finishes with false"); return false;}x++;y--;}trace("diagonals_clear: diagonals_clear finishes with true"); return true;}/** clash*Check whether the row, column, and/or diagonals from the given*coordinate on the given board are not clear of queens*Pre-condition: the given game_state is defined and the given row* and column numbers are within the board of the* given game_state*Post-condition: false is returned if the row, column, and/or*diagonals centered at the given coordinate contain*no queens, and true is returned otherwise*Informally: Return whether or not the row, column, anddiagonals*of a given coordinate are not clear of queens**Param r int row value for coordinate*Param c int column value for coordinate**return bool whether there is already a queen on the row, column,*and/or diagonals*/bool clash(game_state g, int r, int c){trace("clash: clash starts and finishes"); return !(row_clear(g, r) && column_clear(g, c) && diagonals_clear(g, r, c));}/** taken*Check whether a square on the board has already been visited*Pre-condition: the given game_state is defined and (r,c) is*within the bounds of the given game_state*variable's board field*Post-condition: true is returned if (r,c) has been visited (i.e.*is non-zero, and false is returned otherwise*Informally: Return whether or not a square has been taken**Param r int row value to check*Param c int column value to check**return bool whether the nominated square contains a queen*/bool taken(game_state g, int r, int c){ if(occupied(g->board[r-1][c-1])){return true;} else{return false;}}/** land*Visit a square on the board*Pre-condition: the given game_state is defined and (r,c) is*within the bounds of the given game_state*variable’s board field*Post-condition: the square at (r,c) has been visited*Informally: Visit a square**Param r int row value to use*Param c int column value to use*/void land(game_state g, int r, int c){occupy(g->board[r-1][c-1]);}/** clone*Deeply clone a game_state*Pre-condition: the given game_state is defined*Post-condition: a deep clone of the given game_state is returned*Informally: Copy a game**return game_state the independent copy of the game_state*/game_state clone(game_state g){//Create copygame_state copy = (game_state)malloc(sizeof(struct game_state_int));//Populate copy with informationfor(int i = 1; i <= DIMENSION; i++){for(int j = 1; j <= DIMENSION; j++){init_square_state(©->board[i][j], i, j);if (taken(g,i,j)==true){land(copy,i,j);}}}return copy;}void init_game_tree(game_tree *tp,bool e,void *o,int l){trace(“game_tree: initialiser starts”);*tp=(game_tree)malloc(sizeof(struct game_tree_int)); if (e){(*tp)->root = NULL;} else{init_t_node(&((*tp)->root), o, l);}trace(“game_tree: initialiser ends”);}/**is_empty_game_tree*Emptiness test.*Pre-condition: the game_tree variable is defined and valid*Post-condition: true is returned if the game_tree variable is*empty, false is returned otherwise*Informally: indicate if the game_tree contains no nodes**return boolean whether or not the game tree is empty*/bool is_empty_game_tree(game_tree t){ return t -> root == NULL;}/***get_data*Get function for “root” instance variable’s data value.*Pre-condition: the game_tree variable is defined and valid*Post-condition: the value of the game_tree variable’s data*field is returned*Informally: return the value within the root node**return void * the data item of the root node*/void *get_data(game_tree t){trace(“get_data: get_data starts”); if (is_empty_game_tree(t)){fprintf(stderr,”get_data: empty game tree”);exit(1);}trace(“get_data: get_data ends”); return get_t_node_data(t->root);}/**get_level*Get function for “root” instance variable’s level value.*Pre-condition: the game_tree variable is defined and valid*Post-condition: the value of the game_tree variable’s data*field’s level is returned*Informally: return the level value within the root node**return int the level number of the root node*/int get_level(game_tree t){trace(“get_level: get_data starts”); if (is_empty_game_tree(t)){fprintf(stderr,”get_level: empty game tree”);exit(1);}trace(“get_level: get_level ends”); return get_t_node_level(t->root);}/**get_child*Get function for “root” instance variable’s child value.*Pre – condition: the game_tree variable is defined and valid*Post – condition : the value of the game_tree variable’s child*field is returned in a newly*constructed game_tree variable*Informally : return the game_tree variable’s child**return game_tree the eldest child of the current node*/game_tree get_child(game_tree t){game_tree c;trace(“get_child: get_child starts”); if (is_empty_game_tree(t)){fprintf(stderr, “get_child: empty game tree”);exit(1);}init_game_tree(&c, true, NULL, -1);c->root = get_t_node_child(t->root);trace(“get_child: get_child ends”); return c;}/** get_sibling*Get function for “root” instance variable’s sibling value.*Pre-condition: the game_tree variable is defined and valid*Post-condition: the value of the game_tree variable’s sibling*field is returned in a newly constructed*game_tree variable*Informally: return the game_tree variable’s sibling**return game_tree the next sibling of the current node*/game_tree get_sibling(game_tree t){game_tree c;trace(“get_sibling: get_sibling starts”); if (is_empty_game_tree(t)){fprintf(stderr, “get_sibling: empty game tree”);exit(1);}init_game_tree(&c, true, NULL, -1);c->root = get_t_node_sibling(t->root);trace(“get_sibling: get_sibling ends”); return c;}/**set_data*Set function for “root” instance variable’s data field.*Pre-condition: the game_tree variable is defined and valid*Post-condition: the t_node variable’s data field is altered to*hold the given (o) value*Informally: store the given value in the root node of the*game_tree variable**param o void * to install as data for root node*/void set_data(game_tree t,void *o){trace(“set_data: set_data starts”); if (is_empty_game_tree(t)){fprintf(stderr,”set_data: empty game tree”);exit(1);}set_t_node_data(t->root,o);trace(“set_data: set_data ends”);}/**set_level*Set function for “root” instance variable’s level field.*Pre-condition: the game_tree variable is defined and valid*Post-condition: the t_node variable’s level field is altered*to hold the given (l) value*Informally: assign the given value as the level of the*game_tree variable**param l level number for root of current game tree*/void set_level(game_tree t,int l){trace(“set_level: set_level starts”); if (is_empty_game_tree(t)){fprintf(stderr,”set_level: empty game tree”);exit(1);}set_t_node_data(t->root, l);trace(“set_level: set_level ends”);}/**set_child*Set function for “root” instance variable’s child field.*Pre-condition: the game_tree variable is defined and valid*Post-condition: the t_node variable’s child field is altered*to hold the given (c) value*Informally: assign the given value as the child of the*game_tree variable**param c game_tree to be set as eldest child of current game tree*/void set_child(game_tree t, game_tree c){trace(“set_child: set_child starts”); if (is_empty_game_tree(t)){fprintf(stderr,”set_child: empty game tree”);exit(1);}set_t_node_data(t->root, c);trace(“set_child: set_child ends”);}/**set_sibling*Set function for “root” instance variable’s sibling field.*Pre-condition: the game_tree variable is defined and valid*Post-condition: the t_node variable’s sibling field is altered*to hold the given (s) value*Informally: assign the given value as the sibling of the*game_tree variable**param s game_tree to be set as next sibling of current game tree*/void set_sibling(game_tree t,game_tree s){trace(“set_sibling: set_sibling starts”); if (is_empty_game_tree(t)){fprintf(stderr,”set_sibling: empty game tree”);exit(1);}set_t_node_data(t->root, s);trace(“set_sibling: set_sibling ends”);}Computer ScienceEngineering & TechnologySoftware engineeringShare Question
