شجرة البحث الثنائية Java

Question

لدي سؤال حول كيف يمكنني إزالة طفل من عقدة (جذر)؟ نظرا لأنني لا أستطيع الاتصال بالإزالة، إذا قمت بإنجاب الطفل خالية، فسوف يتحرك أطفال هذا الطفل؟ مثل، هل أنا فقط تهيئة ذلك تماما؟ أو أود أن أشر إلى طفل الطفل؟

Answer 1

في شجرة بحث ثنائية تقليدية، يمكن أن يكون لإزالة العقدة عواقب مختلفة اعتمادا على عدد الأطفال العقدة:

• عقدة مع عدم إزالة أي أطفال
• يمكن إزالة عقدة مع طفل واحد، وسيتم استبدال العقدة بطفلك الوحيد. هذا ينطبق بغض النظر عما إذا كان الطفل هو الطفل الأيسر أو الأيمن.
• عقدة مع طفلين لديها قاعدة أكثر تعقيدا قليلا: يجب أن تجد خليفة حسب الطلب أو سابقا للسلف من العقدة المراد إزالتها، استبدل قيمة العقدة الحالية بقيمة فلس أو سلفها، ثم حذف الخلف أو السلف (وفقا لهذه القواعد).

Answer 2

هل هذه الواجبات المنزلية؟ لا حرج في ذلك ... نحن فقط نود مساعدة الناس على التعلم بدلا من إخبارهم بالإجابات.

إذا قمت بتعيين عقدة الطفل فقط إلى Null، فسوف تفقد أي معلومات حول أطفال الأطفال.

Answer 3

ستعرف فئة شجرة قياسية أطفالها، عالقة عادة في مجموعة أو جمع - في حالة شجرة ثنائية، لديك فقط طفلان مباشران، لذلك سيعمل صفيف بحجم ثابت. ولهذا السبب، عادة ما ينفذون نوعا ما من طريقة "إزالة الإزالة" التي يدعوها الطفل إلى إزالتها من قائمة الأطفال.

كما ذكر أعلاه، يصبح هذا معقدا إذا كان الطفل الذي تقوم بإزالة الأطفال.

Answer 4

إجابة تيم تبدو أفضل. ولكن نعم، سوف ترغب في القيام بأحد الأشياء الثلاثة اعتمادا على نوع الطفل الذي يتم إزالته. إذا جعلت طفلا فارغا، فلن يتحرك الأطفال لأنك فقدت إشارة إليهم. بدلا من ذلك، سترغب في تحديد ما إذا كان يجب تعيين الأطفال الأيسرين أو المناسبين للطفل لإزالة الإزالة على المؤشر الذي يشير إلى الطفل الإزالة. بعد تعيين "مؤشر العقد" السابق (يسار أو يمين) إلى الطفل (يسار أو يمين) من العقدة الخاصة بك، لن يكون لديك مرجع بعد الآن إلى هذه العقدة، لذلك لا حاجة لضبطها إلى NULL (يمكنك " T الوصول إليها بعد الآن. ما لم تكتب نوعا ما من BST المرتبط بشكل مضاعف، وفي هذه الحالة ليست هي الكلاسيكية BST)

Answer 5

يجب أن يساعدك هذا الرمز

public Node<T> getParentOf(Node<T> child){
    findParentOf(this.root, child);
    return temp;
}

private void findParentOf(Node<T> ROOT, Node<T> child){
    if(ROOT.hasLeft()){
        findParentOf(ROOT.left, child);
    }

    if(ROOT.left == child || root.right == child){
        temp = ROOT;
    }

    if(ROOT.hasRight()){
        findParentOf(ROOT.right, child);
    }
}


private void replaceNode(Node<T> original, Node<T> newNode){
    Node<T> tempParent = getParentOf(original);
    if(original == tempParent.left){
        tempParent.left = newNode;
    }else if(original == tempParent.right){
        tempParent.right = newNode;
    }
}

private void traverseChildrenAndAdd(Node<T> newParent, Node<T> oldParent){
    newParent.insert(oldParent.data);
    if(oldParent.hasLeft()){
        traverseChildrenAndAdd(newParent,oldParent.left);
    }



    if(oldParent.hasRight()){
        traverseChildrenAndAdd(newParent,oldParent.right);
    }
}
private void deleteNode(Node<T> ROOT, Node<T> d){
    if(d.data.compareTo(ROOT.data) < 0){
        deleteNode(ROOT.left, d);
    }else if(d.data.compareTo(ROOT.data) > 0){
        deleteNode(ROOT.right, d);
    }else if(d == this.root){
        if(this.root.hasLeft()){
            traverseChildrenAndAdd(root.left, root.right);
            root = root.left;
        }else if(root.hasRight()){
            root = root.right;
        }else{
            root = null;
        }
    }else{
        if(ROOT.hasLeft()&&ROOT.hasRight()){
            Node<T> successor = getMinNode(ROOT);
            replaceNode(successor, successor.right);
        }else if(ROOT.hasLeft() || ROOT.hasRight()){
            if(ROOT.hasLeft()){
                replaceNode(ROOT, ROOT.left);
            }else{
                replaceNode(ROOT, ROOT.right);
            }
        }else{
            replaceNode(ROOT, null);
        }
    }
}

public void remove(T data){
    deleteNode(this.root, new Node<T>(data));
}

Answer 6

يمكنك أن تفعل شيئا مثل هذا (رمز زائدي):

بالنظر إلى جذر الشجرة "الجذر" والعقدة لحذف أو بعض البيانات "X" تفعل ما يلي

 if x < root
      recurse to left child
 if x > root
      recurse to right child
 else //node found
      find the min item of the node right child //min item should be left most leaf node node
      replace the value of the node you want to delete with min nodes value
      now delete the min node
 return root;

الشفرة:

delete(Node root, Object x){
    if(root == null){
        return null;
    }

    if(data < root.data){
        root = delete(root.left);
    }else if(root.data < data){
        root = delete(root.right);
    }else{
        if(root.left != null && root.right != null){
            Object tmp = findMin(root.right);
            root.data = tmp;
            root.right = delete(root.right, tmp);
        }else{
            return (root.left != null) ? root.left : root.right;    
        }
    }
return root;

}