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 回答