二叉樹和特殊節點打印

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

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

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

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; 
    } 
};

這是否需要堆棧實現？

來源

2013-10-28 waplet

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

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

嘗試類似：（未測試還）

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

來源

2013-10-28 12:07:08

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

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,

來源

2013-10-28 12:08:37 user2927610

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

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

我我做了這樣的事情，但由於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））的時間...

來源

2013-10-28 21:15:26 waplet

二叉樹和特殊節點打印

回答

相關問題