Các câu hỏi phỏng vấn [42]

  1. Cho một cây nhị phân với cấu trúc đỉnh như sau:
    struct BTNode {
        int data;
        BTNode* left;
        BTNode* right;
    }
    

    viết hàm void foo(BTNode* root) nhận vào con trỏ đến gốc cây và in ra các node trên cây theo thứ tự inorder mà chỉ được dùng O(1)-không gian. (Do đó, các loại giải pháp dùng recursion hay dùng stack là không được phép.)

  2. Tiếp theo câu trước, giả sử cây nhị phân cho trước là cây tìm kiếm nhị phân: data bên trái nhỏ hơn gốc và nhỏ hơn data bên phải. Viết hàm BTNode* bar(BTNode* root), sắp xếp lại các con trỏ, để biến cây nhị phân này thành một danh sách liên kết kép và vòng lặp (circular doubly-linked list). Hàm trả về con trỏ vào phần tử đầu của danh sách. Ở đây, ta sẽ hiểu left là con trỏ về phần tử trước (previous) và right trả về phần tử sau (next) trong danh sách liên kết kép.
Chủ đề : Lập trình and tagged , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

3 Comments

  1. Chấn Ngô
    Posted 08/05/2012 at 9:32 am | Permalink

    Hello a NQH,

    Em nghĩ bài này mình dùng cách duyệt cây theo giải thuật Moris Traversal, trong quá trình duyệt mình sẽ thay đổi tree, duyệt xong sẽ chuyển ngược về tree ban đầu. Ý tưởng chính là như sau:
    1. Initialize current as root
    2. While current is not NULL
    If current does not have left child
    a) Print current’s data
    b) Go to the right, i.e., current = current->right
    Else
    a) Make current as right child of the rightmost node in current’s left subtree
    b) Go to this left child, i.e., current = current->left
    Theo cách này thì ko yêu cầu thêm về bộ nhớ là hằng số (constant space).
    Em copy đoạn C++ code người # viết mọi người kiểm tra xem:

    #include
    #include
     
    /* A binary tree tNode has data, pointer to left child
       and a pointer to right child */
    struct tNode
    {
       int data;
       struct tNode* left;
       struct tNode* right;
    };
     
    /* Function to traverse binary tree without recursion and
       without stack */
    void MorrisTraversal(struct tNode *root)
    {
      struct tNode *current,*pre;
     
      if(root == NULL)
         return; 
     
      current = root;
      while(current != NULL)
      {
        if(current->left == NULL)
        {
          printf(" %d ", current->data);
          current = current->right;
        }
        else
        {
          /* Find the inorder predecessor of current */
          pre = current->left;
          while(pre->right != NULL && pre->right != current)
            pre = pre->right;
     
          /* Make current as right child of its inorder predecessor */
          if(pre->right == NULL)
          {
            pre->right = current;
            current = current->left;
          }
     
          /* Revert the changes made in if part to restore the original
            tree i.e., fix the right child of predecssor */
          else
          {
            pre->right = NULL;
            printf(" %d ",current->data);
            current = current->right;
          } /* End of if condition pre->right == NULL */
        } /* End of if condition current->left == NULL*/
      } /* End of while */
    }
     
    /* UTILITY FUNCTIONS */
    /* Helper function that allocates a new tNode with the
       given data and NULL left and right pointers. */
    struct tNode* newtNode(int data)
    {
      struct tNode* tNode = (struct tNode*)
                           malloc(sizeof(struct tNode));
      tNode->data = data;
      tNode->left = NULL;
      tNode->right = NULL;
     
      return(tNode);
    }
     
    /* Driver program to test above functions*/
    int main()
    {
     
      /* Constructed binary tree is
                1
              /   \
            2      3
          /  \
        4     5
      */
      struct tNode *root = newtNode(1);
      root->left        = newtNode(2);
      root->right       = newtNode(3);
      root->left->left  = newtNode(4);
      root->left->right = newtNode(5); 
     
      MorrisTraversal(root);
     
      getchar();
      return 0;
    }
    
    • numos
      Posted 08/11/2012 at 5:52 am | Permalink

      Dear bạn Chấn Ngô,

      Mình thử check lời giải của bạn. Bạn in ra kết quả theo thứ tự trước Preorder trong khi yêu cầu bài toán là Inorder.
      Bản kiểm tra lại xem.

      Ý tưởng của mình để in theo thứ tự Inorder dùng O(1)-memory.

      1. Initialize current as root
      2. While current is not NULL
      2.1. Print current’s data.
      2.2. If current->left is NULL then current = current->right.
      Else
      {
      2.2.1. Make the right child of the rightmost node in current->left is current->right.
      2.2.2. current = current->left.
      }

      #include
      #include
      /* A binary tree tNode has data, pointer to left child
      and a pointer to right child */
      struct tNode
      {
      int data;
      struct tNode* left;
      struct tNode* right;
      };

      void Inorder(struct tNode *root)
      {
      struct tNode *current,*node;

      current = root;
      while(current != NULL)
      {
      printf(” %d “, current->data);
      if(current->left == NULL)
      {
      current = current->right;
      }
      else
      {
      /* Find the rightmost node of current->left */
      node = current->left;
      while(node->right != NULL)
      node = node->right;
      /* Set the right child of the rightmost node of current->left is current->right*/
      node->right = current->right;

      current = current->left;
      }
      } /* End of while */
      }

      /* UTILITY FUNCTIONS */
      /* Helper function that allocates a new tNode with the
      given data and NULL left and right pointers. */
      struct tNode* newtNode(int data)
      {
      struct tNode* tNode = (struct tNode*)
      malloc(sizeof(struct tNode));
      tNode->data = data;
      tNode->left = NULL;
      tNode->right = NULL;

      return(tNode);
      }

      /* Driver program to test above functions*/
      int main()
      {

      /* Constructed binary tree is
      1
      / \
      2 3
      / \
      4 5
      */
      struct tNode *root = newtNode(1);
      root->left = newtNode(2);
      root->right = newtNode(3);
      root->left->left = newtNode(4);
      root->left->right = newtNode(5);

      Inorder(root);

      getchar();
      return 0;
      }

  2. Xuân Lương
    Posted 20/08/2012 at 3:11 pm | Permalink

    Hi GS. Hưng
    Bài 111 em nghĩ có thể giải dựa trên ý tưởng sau:
    - Về cơ bản thì ta dùng một con trỏ đi tuần tự ở nút gốc rồi rẽ sang trái cho tới khi chạm nút lá thì print data -> đi ngược lên nút cha -> print data -> rẽ phải …
    - Để giải quyết yêu càu không gian là O(1) thì ta có một con trỏ để duyện trong cây và một biến đi kèm để biết là con trỏ đó đã rẽ phải / trái mấy lần. Biến đó được cập nhật dựa trên cơ chế là:
    – Nếu con trỏ ở root thì foo = 1
    – Một lần rẽ trái thì foo = foo * 2
    – Một lần rẽ phải thì foo = foo * 2 + 1
    Với cách này, khi con trỏ chạy tới nút lá, ta gán nó trở về nút gốc và duyệt lại cho tới nút cha của nút cuối cùng mà nó đã trỏ tới. Việc này time-consuming nhưng có thể thỏa mãn yêu cầu về bộ nhớ?

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>