在樹中打印某些元素

我需要製作一個程序，該程序將接受來自用戶的數字，將數字解釋爲遊戲的評分。該計劃的重點在於接受數字，並在質量和數量上製造不平衡的團隊。在樹中打印某些元素

例如：用戶輸入的數字：25，50，63，80

的糟糕的球隊是：25，50

良好的團隊將是：63，90。

我正在使用二叉搜索樹，所以時間是O(nlogn)。

到目前爲止，我的代碼接受數字，將它們放入樹中，確定團隊數量是否相等，但不能正確打印。我懷疑問題出在我的int main()當我打印功能或實際的打印功能。

#include <iostream> 
using namespace std; 

struct node 
{ 
    int data; 
    node *left; 
    node *right; 
}; 

node *createNode(int data) // creates nodes 
{ 
    node *newNode = NULL; 
    newNode = new node; 
    newNode->data=data; 
    newNode->left=NULL; 
    newNode->right=NULL; 
    return newNode; 
} 

node *insert(int data, node **tree) // inserts them into a tree 
{ 
    node *newNode=NULL; 
    if (*tree==NULL) 
    { 
     newNode = createNode(data); 
     *tree = newNode; 
    } 
    else if (data<(*tree)->data) 
    { 
     if ((*tree)->left==NULL) 
     { 
      newNode = createNode(data); 
      (*tree)->left=newNode; 
     } 
     else 
     { 
      newNode = insert(data, &((*tree)->left)); 
     } 
    } 
    else 
    { 
     if ((*tree)->right==NULL) 
     { 
      newNode = createNode(data); 
      (*tree)->right = newNode; 
     } 
     else 
      newNode = insert(data, &((*tree)->right)); 
    } 
    return newNode; 
} 

void destroy(node *tree) // destroy tree at the end 
{ 
    if (tree!=NULL) 
    { 
     if (tree->left!=NULL) 
      destroy(tree->left); 
     if (tree->right!=NULL) 
      destroy(tree->right); 
     delete tree; 
    } 
} 

int treeHeight(node *tree, int counter) // finds the height of the tree 
{ 
    if (tree==NULL) // if there is nothing in the tree, return 0 
     return counter; 

    int leftcount, rightcount; // leftcount counts the left side of the tree and right count counts the right side of the tree 
    counter++; // counter should go up by 1 for every node 
    rightcount = treeHeight(tree->right, counter); // searches the right side 
    leftcount = treeHeight(tree->left, counter); // searches the left side 

    if (rightcount > leftcount) // return the height 
     return rightcount; 
    else 
     return leftcount; 
} 

void printNode(node *Node) 
{ 
    if (Node!=NULL) 
    { 
     cout << Node->data << ", "; 
    } 
} 

void printLeft(node *tree) 
{ 
    if (tree!=NULL) 
    { 
     printLeft(tree->left); 
     printNode(tree); 
    } 
} 

void printRight(node *tree) 
{ 
    if (tree!=NULL) 
    { 
     printRight(tree->right); 
     printNode(tree); 
    } 
} 


int main() 
{ 
    node *root = NULL; 
    node *current = NULL; 
    int value; 

    while (true) 
    { 
     cout << "Enter a rating where the bigger the number, the better (zero to quit): "; 
     cin >> value; 
     if (value==0) 
      break; 
     current = insert(value, &root); 
    } 

    int height = treeHeight(root, 0); // call the function and display the height of the tree 

    if (height==0) 
    { 
     cout << "\nYou did not enter any players, the game cannot happen now. Thanks a lot." << endl; 
     return 0; 
    } 

    else if (height%2!=0) 
    { 
     cout << "Uneven amount of player, add one more player to make the teams equal in quantity" << endl; 
     cout << "Enter a rating: "; 
     cin >> value; 
     current = insert(value, &root); 
    } 

     cout << "\nThe bad team is: " ; 
     printLeft(root); // ??? 
     cout << "\nThe good team is: "; 
     printRight(root); // ??? 

    destroy(root); 
    return 0; 
}

來源

2014-04-24 user3519448

首先，你一定誤解了一些東西。使用此輸入的二進制搜索樹：25, 50, 63, 80不會按您寫的方式分割。看。這將是構建這樣的：

不這樣的：

而且不像

我勸你去模仿插入到BST：BST simulator online

現在，關於你的代碼。函數printLeft和printRight僅打印樹的最左側和最右側分支中的元素（並且printLeft將它頂到底部，而printRight從底部開始）。這就是爲什麼他們給結果25和80, 63, 50, 25。我不確切知道你的BST應該分爲「壞」和「好」團隊，但假設「壞」團隊由根節點和左子樹組成，「好」團隊只包含右子樹（根節點）。然後，你可以使用此功能：

void printSubTree(node *tree) { 
    if (tree) { 
     printSubTree(tree->left); 
     printNode(tree); 
     printSubTree(tree->right); 
    } 
}

，並修改代碼：

if (root) { 
    cout << "\nThe bad team is: " ; 
    printNode(root); 
    printSubTree(root->left); 
    cout << "\nThe good team is: "; 
    printSubTree(root->right); 
}

來源

2014-04-30 13:28:15

在樹中打印某些元素

回答

相關問題