2012-10-14 60 views
0

我正在嘗試編寫一個代碼,該代碼在二進制搜索樹根和級別下打印出該級別樹的元素。這是工作的罰款:但是無法以相反順序在給定級別打印BST的元素

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) 

回答

1

要調用的revprintmyprint。的revprint固定的版本:

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

來吧,我當然能做到這一點!我想知道的是爲什麼代碼不工作! – SexyBeast

+0

你能提供初始化樹的代碼嗎?在這種情況下,至少可以進行測試。 –

+0

我可以,但在這裏幾乎沒有必要。每個節點有三個屬性 - 「左」,「右」和「數據」。我使用root和level調用函數:'revprint(root,level)'。 – SexyBeast

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. 
+0

這是很好的工作。但是我提到的方法,或者通過簡單地使用堆棧,可以更簡潔地完成... – SexyBeast

+0

我可以刪除數組的使用情況,但代碼將變得比以前嚴格得多。 –

相關問題