جافا TreeMap فرز الخيارات؟

Question

ولقد قيل لي أن TreeMap الطبقة جافا يستخدم تنفيذ شجرة RB. إذا كان هذا هو الحال، كيف يمكن للمرء القيام اتباعها، بلاي وpostorder شجرة المشي على TreeMap؟

وأم أن هذا غير ممكن؟

Answer 1

وأنت لن تكون قادرة على القيام بذلك مع TreeMap تنفيذها في المكتبة مجموعات. وإليك تنفيذ <وأ href = "https://www.java-tips.org/java-se-tips-100019/24-java-lang/1904-red-black-tree-implementation-in-java. أتش تي أم أل "يختلط =" نوفولو noreferrer "> شجرة الأحمر الأسود في جاوة التي يمكن أن ننظر في بالرغم من ذلك. تحقق من الأساليب printTree() لمعرفة كيفية السير على شجرة في ترتيب فرزها.

/**
 * Print all items.
 */
public void printTree( ) {
    printTree( header.right );
}

/**
 * Internal method to print a subtree in sorted order.
 * @param t the node that roots the tree.
 */
private void printTree( RedBlackNode t ) {
    if( t != nullNode ) {
        printTree( t.left );
        System.out.println( t.element );
        printTree( t.right );
    }
}

ومنذ ذلك ربما يمكنك كتابة الأساليب الخاصة بك لاجتياز شجرة في جميع المراتب الثلاثة.

Answer 2

وAFAIK وTreeSet / دروس TreeMap لا تعرض في الواقع أي من الداخلية ومجرد تتفق مع واجهة / خريطة مجموعة. ويضمن مكرر فقط للذهاب في ترتيب تصاعدي.

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

Answer 3

ويمكنك على الأقل القيام اتباعها المشي باستخدام مكرر ولكل حلقة:

void inOrderWalk(TreeMap<K,V> treeMap) {
   //this will loop through the values in the map in sorted order (inorder traversal)
   for (Map.Entry<K,V> entry : treeMap.entrySet() {
        V value = entry.getValue();
        K key = entry.getKey()
   }
}

ولكن، وغيرها من الملصقات على حق: جافا لا يعرض أي من الميكانيكا شجرة، لذلك طلب مسبق أو postorder غير ممكن في هذا الرأي

.