2013-10-28 273 views
1

我有一個這樣的樹在二進制表示;二叉樹和特殊節點打印

    1 
       /
       2 
       \ 
       3 
       /\ 
       6 4 
       \ \ 
       7 5 
        /
        8 
       /
       9 
        \ 
        10 
        \ 
         11 

但在現實中,這不是二叉樹而是像

 1 
/| | \ 
2 3 4 5 
    /\ | 
    6 7 8 
     /| \ 
     9 10 11 

能否請你幫我得到打印出來的東西像(孩子的逆序打印出來)

1 : 5 4 3 2 
5 : 8 
3 : 7 6 
8 : 11 10 9 

我的TNode類看起來像。

class TNode { 
public: 
    unsigned long int data; 
    TNode * left;///first child 
    TNode * right;/// sibling 
    TNode * parent;/// parent 

    TNode(unsigned long int d = 0, TNode * p = NULL, TNode * n = NULL)///konstruktors 
    { 
     left = NULL; 
     right = NULL; 
     parent = p; 
     data = d; 
    } 
}; 

這是否需要堆棧實現?

+0

這個問題不對我有意義。二叉樹和n元樹之間的關係是什麼?你如何將一個映射到另一個? – pburka

+0

它在技術上: leftchild - firstChild rightChild - rightsibling – waplet

回答

0

嘗試類似:(未測試還)

printTree(TNode root) { 
    queue <TNode> proc; 
    proc.push(root); 
    while (!proc.empty()) { 
     TNode front = proc.front(); 
     proc.pop(); 

     // add front's children to a stack 
     stack <Tnode> temp; 
     Tnode current = front->left; 
     while (current != NULL) { 
      temp.push(current); 
      current = current->right; 
     } 
     // add the children to the back of queue in reverse order using the stack. 
     // at the same time, print. 
     printf ("%lld:", front->data); 
     while (!temp.empty()) { 
      proc.push(temp.top()); 
      printf(" %lld", temp.top()->data); 
      temp.pop(); 
     } 
     printf("\n"); 
    } 

} 

我仍然在努力使其更加優雅。感謝有趣的問題!

編輯:改變了格式說明LLD

0

怎麼樣這種方法: 遍歷中序樹(訪問每個節點)。對於每個節點(旅行時)檢查它是否有左孩子。如果是這樣(表示在原始樹中具有子元素的節點)以「:」打印節點數據並採取其子樹並遞歸地跟隨所有正確的兒子(它們代表所有兄弟姐妹),之後打印每個正確的兒子數據(您擁有它在 代碼相反順序:

void print_siblings() { 
    if (this->right != NULL) { 
     this->right->print_siblings(); 
    } 
    cout << data << ", "; 
} 

void traverse(void) { 
    if (this->left != NULL) { 
     cout << data << ":"; 
     this->left->print_siblings(); 
     cout << endl; 
     this->left->traverse(); 
    } 

    if (this->right != NULL) { 
     this->right->traverse(); 
    } 
} 

編輯:這是一箇中序遍歷:

void traverse_inorder(void) { 
    if (this->left != NULL) { 
     this->left->traverse_inorder(); 
     cout << data << ":"; 
     this->left->print_siblings(); 
     cout << endl; 
    } 

    if (this->right != NULL) { 
     this->right->traverse_inorder(); 
    } 
} 

輸出預購將是:

1:5, 4, 3, 2, 
3:7, 6, 
5:8, 
8:11, 10, 9, 

輸出爲序是:

3:7, 6, 
8:11, 10, 9, 
5:8, 
1:5, 4, 3, 2, 

EDIT2:只是爲了完整性,後序遍歷以及:-)

void traverse_postorder(void) { 
    if (this->left != NULL) { 
     this->left->traverse_postorder(); 
    } 

    if (this->right != NULL) { 
     this->right->traverse_postorder(); 
    } 
    if (this->left != NULL) { 
     cout << data << ":"; 
     this->left->print_siblings(); 
     cout << endl; 
    } 

} 

,其輸出:

8:11, 10, 9, 
5:8, 
3:7, 6, 
1:5, 4, 3, 2, 
+0

不是這個打印樹的順序,但與顛倒的孩子? – waplet

+0

實際上,即使它看起來有序,它仍然是預購。更具體的說,它是預先訂購的,但如果左邊的子項不是NULL(也就是在原始非二進制樹中有子項的節點),則只訪問/評估根目錄。但是,您所穿過的順序隻影響輸出的順序。請參閱我的第二篇文章進行比較... – user2927610

0

我我做了這樣的事情,但由於while循環,它是一種無條件的。 有什麼辦法使之更REC

void mirrorChilds(TNode * root)// 
{ 
    if(!root) return; 
    cout << root->data << " "; 
    //tmp = tmp->right; 
    if(!root->left) return; 
    TNode * tmp = root->left; 
    while(tmp != NULL) 
    { 

     root->left = tmp; 
     tmp = tmp->right; 
    } 

    tmp = root->left; 
    while(root != tmp) 
    { 
     cout << tmp->data << " "; 
     tmp = tmp->parent; 

    } 
    cout << endl; 
    tmp = root->left; 
    while(root != tmp) 
    { 
     if(tmp->left) mirrorChilds(tmp); 
     //if(tmp->left) cout << tmp->left->data << endl; 
     tmp = tmp->parent; 

    } 
} 

它的工作原理prefectly很好,但你們,我還挺想獲得爲O(n *日誌(n))的時間...