tìm thứ tự sắp xếp trong BST mà không cần thêm bất kỳ khoảng trống nào

Question

Tôi đang tìm cách để tìm ra trình tự sắp xếp thứ tự của một nút trong BST withut sử dụng thêm không gian.

Answer 1

Để có được sự kế thừa inorder của một nút cho trước N chúng tôi sử dụng các quy tắc sau:

• Nếu N có một đứa trẻ ngay R thì inorderSuccessor(N) là chết tận cùng bên trái của R.
• khác inorderSuccessor(N) là tổ tiên gần nhất, M, của N (nếu nó tồn tại) mà N là hậu duệ của những con trái M. Nếu không có tổ tiên như vậy, inorderSucessor không tồn tại.

Xem xét một cây mẫu:

 A 
    /\ 
    B C 
/\ 
D E 
    /
    F 

ai inorder traversal cho: D B F E A C

inorderSuccessor(A) = C như C là người chết tận cùng bên trái của đứa trẻ phải A.

inorderSuccessor(B) = F là phần tử bên trái ngoài cùng bên phải của B.

inorderSuccessor(C) = Không tồn tại.

inorderSuccessor(D) = B là B là con còn lại của D.

inorderSuccessor(E) = A. E không có con ngay vì vậy chúng tôi đã kịch bản 2. Chúng tôi đi đến mẹ của E đó là B, nhưng E là người đã chết bên phải của B, vì vậy chúng tôi chuyển đến mẹ của B đó là A và B còn lại chết của A nên A là câu trả lời.

inorderSuccessor(F) = E là F là con còn lại của E.

Thủ tục:

treeNodePtr inorderSucessor(treeNodePtr N) { 
     if(N) { 
       treeNodePtr tmp; 
       // CASE 1: right child of N exists. 
       if(N->right) { 
         tmp = N->right; 
         // find leftmost node. 
         while(tmp->left) { 
           tmp = tmp->left; 
         } 
       // CASE 2: No right child. 
       } else { 
         // keep climbing till you find a parent such that 
         // node is the left decedent of it. 
         while((tmp = N->parent)) { 
           if(tmp->left == N) { 
             break; 
           } 
           N = tmp; 
         } 
       } 
       return tmp; 
     } 
     // No IOS. 
     return NULL; 
} 

Code In Action

Answer 2

Nếu bạn có thể truy cập thư mục gốc của một nút, thì đó chỉ là vấn đề di chuyển con trỏ xung quanh, do đó không có thêm khoảng trắng. Xem this lecture.

Answer 3

Nếu nút cho trước có một đứa trẻ ngay - hãy đến đó, và sau đó làm theo lặp đi lặp lại những đứa trẻ bên trái cho đến khi bạn đạt đến một nút N không có con bên trái. Trả lại N.

Nếu không, hãy làm theo cha mẹ cho đến khi bạn tìm thấy cha mẹ nơi nút đầu tiên là con trái. Trả lại phụ huynh này.

Node InOrderSuccessor(Node node) { 
    if (node.right() != null) { 
     node = node.right() 
     while (node.left() != null) 
      node = node.left() 
     return node 
    } else { 
     parent = node.getParent(); 
     while (parent != null && parent.right() == node) { 
      node = parent 
      parent = node.getParent() 
     } 
     return parent 
    } 
} 

Answer 4

Các phương pháp sau đây sẽ giúp bạn xác định inorder kế KHÔNG CÓ NÚT PHỤ HUYNH HAY KHÔNG GIAN EXTRA NON-đệ quy

struct node * inOrderSuccessor(struct node *root, struct node *n) 
    { 
    //*If the node has a right child, return the smallest value of the right sub tree* 

    if(n->right != NULL) 
     return minValue(n->right); 

    //*Return the first ancestor in whose left subtree, node n lies* 
    struct node *succ=NULL; 
    while(root) 
    { 
     if(n->datadata < root->data) 
     { 
      succ=root; root=root->left; 
     } 

     else if(n->data > root->data) 
     root=root->right; 
     else break; 
    } 
    return succ; 
} 

Tôi khá chắc chắn điều này là đúng. Làm đúng nếu tôi sai. Cảm ơn.