二叉樹的旋轉功能

我必須做出以下類在C++實現：二叉樹的旋轉功能

struct Node { 
    Node* parent; 
    Node* left; 
    Node* right; 
    std::string name; 
}; 

class BinaryTree { 
public: 
    BinaryTree(); 
    std::string ToString() const; 
    void RotateLeft(Node* node); 
    void RotateRight(Node* node); 
    void MakePerfect(); 
private: 
    void CreateVine(); 
    void MakePerfectFromVine(); 
private: 
    Node *root; 
};

這個類實現在DSW算法用於製作二叉樹完美（所有級別都滿了，除了最後一個）

我已經做了哪些工作的實施，我測試了它，一切看起來很好，但我不得不這樣來改變旋轉功能：

void RotateLeft(Node*& node); 
    void RotateRight(Node*& node);

不幸的是，讓我做這項工作的人說我禁止改變他們。但未改變的功能不起作用。我使用它們CreateVine()和MakePerfectFromVine()：

void CreateVine() { 
    Node *current = root; 
    while(current != NULL) 
     if(current->left != NULL){ 
      current=current->left; 
      rotateRight(current);    
     } 
     else 
      current = current->right; 

}

在這個片段中的指針current點樹中的一個節點。節點旋轉後，它將改變它的父節點和/或左節點和/或右節點，但是current將指向具有舊信息的舊節點。爲了將旋轉函數中所做的更改反映到rotate函數之外，我必須使用reference-to-pointer，pointer-to-pointer或函數本身必須返回節點;

我能想到解決這個問題的唯一方法是，如果我知道二叉樹不允許重複的元素，我旋轉節點後搜索其字符串值並將current設置爲指向它，但我不確定二叉樹是否允許重複元素，這會增加算法的時間複雜度。

有沒有辦法避免使用引用指針和指針指針？

來源

2012-03-13 Daniel Rusev

剔除樹中，你可能不得不考慮別的事情，可以有額外的間接水平得到指針樹中給定節點的根：

Node **pp; 
if (node->parent->left == node) 
    pp = &node->parent->left; 
else 
    pp = &node->parent->right;

這樣你就可以實際上保持你的算法，只是解決參考這樣做的功能。請注意，這是一個草圖，你必須檢查根目錄（parent==0），並在那裏以不同的方式操作。

來源

2012-03-13 11:57:35

我將研究它並回來給你。 – 2012-03-13 12:38:43

我不知道我是否做了你想讓我做的事，但它工作。這是我之前的旋轉函數： 'void RotateLeft（Node * node）{' 'Node * tmp;''...'node = tmp;''}'。我所做的只是改變最後一行'* node = * tmp;' – 2012-03-14 20:10:49

@ user763852如果你的函數的最後一個表達式是那個賦值，你應該注意它對調用者完全沒有任何作用，因此應該被刪除 – 2012-03-15 00:00:43

二叉樹的旋轉功能

回答

相關問題