爲什麼我得到不同的輸出來查找Binary Search Tree的高度？

Question

我已經在這兩個函數寫兩個不同的程序查找二叉搜索樹，但兩者的高度給予不同的輸出作爲我的計算高度的邏輯是一樣的：

int findheight(Node* node) { 
    if (node == NULL) 
     return 0; 
    int lh = 0, rh = 0; 
    if (node->left != NULL) 
     lh = findheight(node->left); 
    if (node->right != NULL) 
     rh = findheight(node->right); 
    return max(lh, rh) + 1; 
} 

第二個函數計算的二進制heigth搜索樹：

int findheight(struct node* node) { 
    if (node == NULL) 
     return 0; 
    else { 
     int ldepth = findheight(node->left); 
     int rdepth = findheight(node->right); 

     if (ldepth > rdepth) 
      return (ldepth + 1); 
     else 
      return (rdepth + 1); 
    } 
} 

對於此測試情況下100 11 11 17 30 40 71 90 92 117 148 151 157 160 174 193 203 227 263 276 280 291 296 307 311 322 340 345 346 373 374 398 402 411 419 437 441 446 450 476 476 493 503 513 523 530 533 545 573 573 593 597 599 603 628 642 650 651 655 658 679 704 711 715 737 745 746 783 783 797 802 808 823 825 826 827 832 834 845 857 861 871 872 877 883 894 907 921 922 940 943 949 951 952 956 958 959 976 979 987 997第二函數給出輸出100而第一函數給出96

對於此測試的情況：100 7 10 29 32 40 52 55 76 83 103 116 122 123 135 162 163 170 184 192 193 205 221 226 235 253 257 259 298 305 310 338 349 388 396 397 399 408 412 419 429 443 443 461 481 485 490 504 508 509 515 517 522 545 547 564 580 596 601 611 616 622 635 664 665 676 684 687 688 689 695 703 724 734 764 771 775 815 816 819 827 849 852 855 864 882 887 893 902 911 937 940 941 943 965 966 968 984 985 993 998第2個功能使輸出：100和1函數給出99

整個代碼查找二叉搜索樹的高度：

#include <bits/stdc++.h> 
    using namespace std; 

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

    struct node *newnode(int item){ 
    struct node *temp = (struct node*)malloc(sizeof(struct node)); 
    temp->key = item; 
    temp->left = temp->right = NULL; 
    return temp; 
    } 

    struct node *insert(struct node *node,int key){ 
     if(node==NULL) return newnode(key); 

     if(key< node->key) 
      node->left = insert(node->left,key); 
     else 
      node->right = insert(node->right,key); 

     return node; 
    } 

    /*Insert any one of the functions mentioned above*/ 

    int main(){ 
     int n,m; 
     cin>>n; 
     struct node *root = NULL; 
     for(int i=0;i<n;i++){ 
      cin>>m; 
      root=insert(root,m); 
     } 
     cout<< maxdepth(root); 

    return 0; 
    } 

Answer 1

的功能都返回相同的值。你的代碼中有其他東西可以產生輸出差異。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
struct node{ 
    int key; 
    struct node *left; 
    struct node *right; 
}; 
int findheight(struct node* node) { 
    if (node == NULL) 
     return 0; 
    else { 
     int ldepth = findheight(node->left); 
     int rdepth = findheight(node->right); 

     if (ldepth > rdepth) 
      return (ldepth + 1); 
     else 
      return (rdepth + 1); 
    } 
} 
int findheight2(struct node* node) { 
    if (node == NULL) 
     return 0; 
    int lh = 0, rh = 0; 
    if (node->left != NULL) 
     lh = findheight(node->left); 
    if (node->right != NULL) 
     rh = findheight(node->right); 
    return (lh>rh ?lh : rh) + 1; 
} 
struct node *newnode(int item){ 
    struct node *temp = (struct node*)malloc(sizeof(struct node)); 
    temp->key = item; 
    temp->left = temp->right = NULL; 
    return temp; 
} 

struct node *insert(struct node *node,int key){ 
    if(node==NULL) return newnode(key); 

    if(key< node->key) 
     node->left = insert(node->left,key); 
    else 
     node->right = insert(node->right,key); 

    return node; 
} 

/*Insert any one of the functions mentioned above*/ 

int main(){ 
    int n,m; 
    n=100; 
    struct node *root = NULL; 
    for(int i=0;i<n;i++){ 
     m = n; 
     root=insert(root,m); 
    } 
    printf("%d", findheight(root)); 
    printf("%d", findheight2(root)); 
    return 0; 
}