Advertisement
varun1729

Untitled

May 4th, 2023
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.31 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. struct TreeNode {
  6. int val;
  7. struct TreeNode* left;
  8. struct TreeNode* right;
  9. };
  10.  
  11. struct TreeNode* newNode(int val) {
  12. struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
  13. node->val = val;
  14. node->left = NULL;
  15. node->right = NULL;
  16. return node;
  17. }
  18.  
  19. struct TreeNode* buildTree(char* str) {
  20. int len = strlen(str);
  21. if (len == 0 || str[0] == 'N') {
  22. return NULL;
  23. }
  24. int i = 0, j = 0, numTokens = 0;
  25. char* tokens[1000];
  26. while (i < len) {
  27. j = i;
  28. while (j < len && str[j] != ' ') {
  29. j++;
  30. }
  31. tokens[numTokens] = (char*) malloc(sizeof(char) * (j - i + 1));
  32. strncpy(tokens[numTokens], str + i, j - i);
  33. tokens[numTokens][j - i] = '\0';
  34. numTokens++;
  35. i = j + 1;
  36. }
  37. struct TreeNode* root = newNode(atoi(tokens[0]));
  38. struct TreeNode** queue = (struct TreeNode**) malloc(sizeof(struct TreeNode*) * numTokens);
  39. int front = 0, rear = 0;
  40. queue[rear++] = root;
  41. i = 1;
  42. while (front != rear && i < numTokens) {
  43. struct TreeNode* parent = queue[front++];
  44. char* currVal = tokens[i++];
  45. if (currVal[0] != 'N') {
  46. int val = atoi(currVal);
  47. struct TreeNode* leftChild = newNode(val);
  48. parent->left = leftChild;
  49. queue[rear++] = leftChild;
  50. }
  51. if (i >= numTokens) {
  52. break;
  53. }
  54. currVal = tokens[i++];
  55. if (currVal[0] != 'N') {
  56. int val = atoi(currVal);
  57. struct TreeNode* rightChild = newNode(val);
  58. parent->right = rightChild;
  59. queue[rear++] = rightChild;
  60. }
  61. }
  62. free(queue);
  63. for (i = 0; i < numTokens; i++) {
  64. free(tokens[i]);
  65. }
  66. return root;
  67. }
  68. void inorderTraversal(struct TreeNode* root) {
  69. if (root) {
  70. inorderTraversal(root->left);
  71. printf("%d ", root->val);
  72. inorderTraversal(root->right);
  73. }
  74. }
  75. int main() {
  76. //char str[] = "1 2 3 N N 4 5";
  77. char str[3500];
  78. //printf("Enter a string: ");
  79. fgets(str, sizeof(str), stdin);
  80. struct TreeNode* root = buildTree(str);
  81. inorderTraversal(root);
  82. // do something with the tree...
  83. return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement