平衡したバイナリツリーを生成する

Question

これが何をするのかわかりません。 私の目標は、一連の値からバランスのとれたバイナリツリーを生成することです。 これが正しいかどうかお知らせください。

注：バランスのとれたバイナリ検索ツリーではなく、バランスのとれたバイナリツリーです。私が手メインで

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(); 

結果がこれです：

  7 
     4 
     6 
    2 
     5 
    3 
1 

2の子供たちはそれがなぜ問題がある4と5です7次のレベルに進んでいます。

Answer 1

addNodePrivateメソッドで2つの子ブランチの高さをチェックし、等しい場合は左に移動するため、7が表示される理由があります。

7を挿入すると、プログラムがルート（ノード1）にあるとき、左の分岐の高さと右の分岐の高さの両方が1に等しいことがわかります（ノード2は子5と4を持ちますが孫がなく、ノード3には子6も孫もいません）、ノード2を持つブランチを左下に移動します。

目的を達成するには、の最短パスを持つブランチを選択する必要があります、2つの枝の高さを比較するだけでは不十分です。

希望は、運がよい。