生成平衡二叉樹

-1

我不確定這是否正在做它應該做的事。我的目標是從一組值中生成一個平衡的二叉樹。請讓我知道這是否正確。生成平衡二叉樹

注意：不是平衡二叉搜索樹，只是平衡二叉樹。

int heightPrivate(nodePtr node) 
{ 
if (node == NULL) 
    return -1; 

return 1 + std::max(heightPrivate(node->left), heightPrivate(node->right)); 
} 

void addNodePrivate(nodePtr node, int val) 
{ 
    if (root == NULL) 
    { 
    root = new BTNode; 
    root->data = val; 
    root->left = root->right = NULL; 
    } 
    else 
    { 
    if (node->left == NULL) 
    { 
     node->left = new BTNode; 
     node->left->data = val; 
     node->left->left = node->left->right = NULL; 
    } 
    else if (node->right == NULL) 
    { 
     node->right = new BTNode; 
     node->right->data = val; 
     node->right->left = node->right->right = NULL; 
    } 
    else 
    { 
     int lheight = heightPrivate(node->left); 
     int rheight = heightPrivate(node->right); 

     if (lheight < rheight) 
     addNodePrivate(node->left, val); 
     else if (rheight < lheight) 
     addNodePrivate(node->right, val); 
     else 
     addNodePrivate(node->left, val); 
    } 
    } 
} 

void printPostorderPrivate(nodePtr p, int indent=0) 
{ 
    if(p != NULL) { 
    if(p->left) printPostorderPrivate(p->left, indent+4); 
    if(p->right) printPostorderPrivate(p->right, indent+4); 
    if (indent) { 
     std::cout << std::setw(indent) << ' '; 
    } 
    std::cout<< p->data << " \n "; 
    } 
}

在主...

int main() 
{ 
    BTree tree; 

    tree.addNode(1); 
    tree.addNode(2); 
    tree.addNode(3); 
    tree.addNode(4); 
    tree.addNode(5); 
    tree.addNode(6); 
    tree.addNode(7); 

    tree.printPostorder();

結果我得到的是這樣的：

的2 4和5的孩子現在的問題是，爲什麼是7進入下一個層次。

來源

2016-05-22 Don Code

7出現的原因是因爲在addNodePrivate方法檢查兩個子分支的高度，如果它們相等，它會離開。

因此，當你插入7時，當程序位於根節點1時，它看到左分支的高度和右分支的高度都等於1（節點2有5和4的孩子但是沒有孫子，節點3有孩子6也沒有孫子），所以它向左 - 向下 - 與節點2的分支。

要實現你想要的，你需要選擇具有最短路徑的分支，所以比較兩個分支的高度是不夠的。

希望有所幫助，祝你好運。

來源

2016-05-22 08:49:46

這的確如此，我通過實現一種計算節點數量的方法，並基於此選擇了一種方法，從而實現了我想要的效果。但無論如何，很好的解釋，謝謝！ –

生成平衡二叉樹

回答

相關問題