كيفية طباعة BST في C ++

Question

يقوم برنامج C ++ بإنشاء شجرة بحث ثنائية. أنا أعرف كيفية طباعة القيم في النظام المسبق، بعد الترتيب، والترتيب.

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

كيف أقوم بذلك؟

Answer 1

هذه المقالة يحتوي على رمز لما تحتاجه، يبدو:

نص Alt http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg.

تحرير: ذهب هذا الموقع دون اتصال

هنا واحدة أخرى استكشاف بعض الخيارات الأخرى.

Answer 2

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

measure the depth of the tree, call that D
have two queues, called Q1 and Q2
enque the top node of the tree in Q1
for (i = D; --i>=0; ){
  foreach node in Q1 {

    on first iteration of this inner loop, print 2^i - 1 spaces,
    else print 2^(i+1) - 1 spaces.

    if node == null print blank
    else print node.value

    if node.left exists enque node.left in Q2
    else enque null in Q2

    if node.right exists enque node.right in Q2
    else enque null in Q2
  }
  copy Q2 to Q1
  clear Q2
  print end-of-line
}

كل مساحة مطبوعة هي عرض حقل رقمي واحد. لنفترض أن الشجرة لديها عمق D = 4. ثم تطور الطباعة مثل هذا:

// it looks like this, and the space sequences are
i = 3: -------n 7
i = 2: ---n-------n 3 7
i = 1: -n---n---n---n 1 3 3 3
i = 0: n-n-n-n-n-n-n-n 0 1 1 1 1 1 1 1

Answer 3

طريقة واحدة هي استخدام Graphviz. على وجه التحديد، استخدم برنامج "DOT" الخاص به، ولكن الحصول على الإخراج للنظر بالضبط كما تصفه قد لا يكون ممكنا.

Answer 4

    void print(node *p,int start)
    {
        start++;
        if (p->right != NULL)
        {
            print(p->right,start);
        }
        for (int i = 0; i <= start; i++)
        {
            cout<<"    ";
        } 
        cout << p->value<<endl;
        if (p->left != NULL)
        {
            print(p->left, start);
        }
    }

Answer 5

حسنا، في محطة، من الصعب ... لأنه قد لا يصلح. ولكن هناك مكتبات رسم الرسوم البيانية هناك يمكن أن تجعل صور لطيفة بالنسبة لك. هناك graphvis هو واحد من الأكثر شعبية.

تحرير: إذا كنت فقط WAN فقط لطباعة النص، فإن Graphvis لديه لغة ترميز يمكن للمستخدم أن يمر إلى graphvis بدوره يجعل الصور الجميلة.