0

私は、バイナリ検索ツリーのルートとレベルを指定して、そのレベルでツリーの要素を出力するコードを作成しようとしています。これは正常に機能しています。

def myprint(root,level):
    if root:
        if not level:
            print root.data,
        else:
            myprint(root.left,level-1)
            myprint(root.right,level-1)

ただし、要素を逆の順序で印刷するように微調整しようとすると、機能しません。次のツリーの場合：

                         26
                    /          \
                   13          39
                  /  \        /  \
                 6    19     32   51
                / \   / \    / \  / \
               4   8  14    31 33   68
                        \
                         17

レベル3（ルートのレベルは0）の要素を右から左に出力する場合、出力はになります68 33 31 14 8 4。上記のコードは逆を正しく実行します。つまり、を出力し4 8 14 31 33 68ます。ただし、以下のコードは逆の順序を正しく出力せず、31 33 68 4 8 14代わりに出力します。

def revprint(root,level):
    if root:
        if not level:
            print root.data,
        else:
            myprint(root.right,level-1)
            myprint(root.left,level-1)

誰かがエラーを見つけて、それを修正する方法を教えてもらえますか？ツリーを初期化するためのコードは次のとおりです。

class tree:
    def __init__(self,data):
        self.data = data
        self.successor,self.left,self.right = None,None,None
    def push(self,data):
        root = self
        while root:
            oldroot = root
            if root.data > data:
                root = root.left
            elif root.data < data:
                root = root.right
        if data > oldroot.data:
            oldroot.right = tree(data)
        else:
            oldroot.left = tree(data)

a = tree(26)
for x in [13,39,6,19,4,8,5,10,9,14,17,15,32,51,68,31,33,36,34]:
a.push(x)
4

2 に答える 2

2 
Here my code prints the tree level by level as well as upside down

int counter=0;// to count the toatl no. of elments in the tree


void tree::print_treeupsidedown_levelbylevel(int *array)
{
int j=2;  
int next=j;
int temp=0;
while(j<2*counter)
{
    if(array[j]==0)
    break;

    while(array[j]!=-1)
    {
        j++;
    }

    for(int i=next,k=j-1 ;i<k; i++,k--)
    {
        temp=array[i];
        array[i]=array[k];
        array[k]=temp;
    }

    next=j+1;
    j++;
}

for(int i=2*counter-1;i>=0;i--)
{
    if(array[i]>0)
    printf("%d ",array[i]);

    if(array[i]==-1)
    printf("\n");
}
} 

void tree::BFS()
{
queue<node *>p;

node *leaf=root;

int array[2*counter];
for(int i=0;i<2*counter;i++)
array[i]=0;

int count=0;

node *newline=new node; //this node helps to print a tree level by level
newline->val=0;
newline->left=NULL;
newline->right=NULL;
newline->parent=NULL;

p.push(leaf);
p.push(newline);

while(!p.empty())
{
    leaf=p.front();
    if(leaf==newline)
    {
        printf("\n");
        p.pop();
        if(!p.empty())
        p.push(newline);
        array[count++]=-1;
    }
    else
    {
        cout<<leaf->val<<" ";
        array[count++]=leaf->val;

        if(leaf->left!=NULL)
        {
            p.push(leaf->left);
        }
        if(leaf->right!=NULL)
        {
            p.push(leaf->right);
        }
        p.pop();
    }
}
delete newline;

print_treeupsidedown_levelbylevel(array);
}


 Here in my code the function BFS prints the tree level by level, which 
 also fills the data in an int array for printing the tree upside down.
(note there is a bit of swapping is used while printing the tree upside down 
 which helps to achieve our goal). 
 if the swaping is not performed then for a tree like

                     8
                   /  \
                  1    12
                  \     /
                   5   9
                 /   \
                4     7
                     /
                    6
  o/p will be
  6
  7 4
  9 5
  12 1
  8

  but the o/p has to be
  6
  4 7
  5 9
  1 12
  8

  this the reason why swapping part wass needed in that array.
于 2012-11-12T12:48:39.747 に答える
1

に電話myprintしていrevprintます。の修正版revprint:

def revprint(root,level):
    if root:
        if not level:
            print root.data,
        else:
            revprint(root.right,level-1)
            revprint(root.left,level-1)
于 2012-10-14T07:57:18.030 に答える