Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Visual C++]Обход дерева в прямом порядке


Автор: lenatitova1 11.5.2008, 14:18
Помогите, пожалуйста исправить ошибки, так чтобы одход дерева был в обратном порядке, используя массивы. Мой код ошибок не выдает, но обход получается неправильный... Я запуталась в этих индексах и циклах.
Дерева выглядит примерно так            0
                                                           1       2
                                                         3  4    5
                                                            6 7  8
А мой код на Visual C++
    

#include "stdafx.h"
#include <iostream>
#include <conio.h>

using namespace std;

struct Tree
{
    int contents;
    int left;
    int right;
};

int _tmain(int argc, _TCHAR* argv[])
{
    Tree a [10];
    int b [10];
    int i, k, j, l, n;
    
    for (i = 1; i < 10; i++)
    {
        a [i].left = -1;
        a [i].right = -1;
    }

    a [0].left = 1;
    a [0].right = 2;
    
    a [1].left = 3;
    a [1].right = 4;

    a [2].left = 0;
    a [2].right = 5;

    a [3].left = 0;
    a [3].right = 0;

    a [4].left = 6;
    a [4].right = 7;

    a [5].left = 0;
    a [5].right = 8;
    
    a [6].left = 0;
    a [6].right = 0;

    a [7].left = 0;
    a [7].right = 0;

    a [8].left = 0;
    a [8].right = 0;

    for (i = 0; i <= 9; i++)
    {
        cout << i + 1 << " " << a [i].left << " " << a [i].right << endl;
    }
    cout << endl << endl;

    i = 0;
    k = 0;
    b [k] = -1;

    while (a [i].left > 0)
        {
            if (a [i].left > 0)
            {
                b [k] = a [i].left;
            }
            i = a [i].left;
        }
    if (b [k] == -1)
    {
        //cout << "%";
        a [i].left = 11;
        b [k] = a [i].left;
    }


    j = 0;
    i = -1;
    for (j = 0; j < 10; j++)
    for (i = 0; i < 10; i++)
    {
        if ((a [i].left == b [k]) || (a [i].right == b [k]))
        {
        //    cout << " !" << i << "! ";
                
            if (b [k] > 0)

            if ((a [i].right == 0) || (a [i].right == b [k]))
            {
                //спускаемся вниз
            //    cout << "down";
                //if (a [i].right == b [k]) cout << "@";
                k = k + 1;
                b [k] = i;
            //    cout << b [k] << " ";
            }
            else
            {
                //находим "левого"
            //    cout << "left";
                k = k + 1;
                l = a [i].right;
                for (n = 1; n < 10; n++)
                    if ((a [l].left == 0) && (a [l].right > 0))
                    {
                        l = a [l].right;
                        //cout << "$";
                    }

                if ((a [l].left == 0) && (a [l].right == 0))
                {
                    b [k] = l;
            //        cout << b [k] << " ";
                }
                else
                {
            //    cout << "#";
                    while (a [l].left > 0)
                    {
                        if (a [l].left > 0)
                        {
                            b [k] = a [l].left;
                        }
                        l = a [l].left;
                    }
            //        cout << b [k] << " ";
                }
            }
        }
    }
    


    if (a [0].left == 11) for (i = 8; i >=0; i--) if (b [i] >= 0) cout << b [i] << " ";
    if (a [0].left != 11) for (i = 9; i >=0; i--) if (b [i] >= 0) cout << b [i] << " ";
    cout << endl << endl;
    _getch ();
    return 0;
}

   

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)