歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

構造一個二叉查找樹-C++實現

根據輸入的數組元素,構造一個二叉查找樹。

  1. #include <iostream>  
  2. using namespace std; 
  3. /*二叉查找樹結構*/ 
  4. typedef struct BSTree 
  5.     int node_value; 
  6.     struct BSTree * left; 
  7.     struct BSTree * right; 
  8. }Tree; 
  9. /*****構造二叉查找樹**********************************************/ 
  10. void  CreateBSTree(Tree * root,int node_value); 
  11. Tree * CreateBSTree(int * array_list,int array_length); 
  12.  
  13. void Print(Tree* root); 
  14.  
  15. /***************************************************************/ 
  16.  
  17. /***************************************************************/ 
  18. int main(int argc,char * argv) 
  19.     Tree * root = NULL; 
  20.     int list[]={5,3,4,9,1,7,11}; 
  21.     root = CreateBSTree(list,7); 
  22.     std::cout<<"Cearte BSTree."<<std::endl; 
  23.     Print(root); 
  24.     return 0; 
  25.  
  26. /*生成二叉查找樹*/ 
  27. Tree * CreateBSTree(int * array_list,int array_length) 
  28.     if(array_length <= 0) 
  29.     { 
  30.         return false
  31.     } 
  32.     Tree * root = NULL; 
  33.     root = new BSTree(); 
  34.     root->left = NULL; 
  35.     root->right = NULL; 
  36.     root->node_value = array_list[0]; 
  37.     for(int i=1;i<array_length;i++) 
  38.     { 
  39.         CreateBSTree(root,array_list[i]); 
  40.     } 
  41.     return root; 
  42. void  CreateBSTree(Tree * root,int node_value) 
  43.     if(root == NULL) 
  44.     { 
  45.         return ; 
  46.     } 
  47.     if(root->node_value > node_value) 
  48.     { 
  49.         if(root->left == NULL) 
  50.         { 
  51.             Tree * node = new Tree(); 
  52.             node->left = NULL; 
  53.             node->right = NULL; 
  54.             node->node_value = node_value; 
  55.             root->left = node; 
  56.         } 
  57.         else 
  58.         { 
  59.              CreateBSTree(root->left,node_value); 
  60.         } 
  61.     } 
  62.     else 
  63.     { 
  64.         if(root->right == NULL) 
  65.         { 
  66.             Tree * node = new Tree(); 
  67.             node->left = NULL; 
  68.             node->right = NULL; 
  69.             node->node_value = node_value; 
  70.             root->right = node; 
  71.         } 
  72.         else 
  73.         { 
  74.              CreateBSTree(root->right,node_value); 
  75.         } 
  76.     } 
  77. /*中序排序輸出二叉查找樹*/ 
  78. void Print(Tree* root) 
  79.     if(root == NULL) 
  80.     { 
  81.         return ; 
  82.     } 
  83.     Print(root->left); 
  84.     std::cout<<root->node_value<<"\t"; 
  85.     Print(root->right); 
Copyright © Linux教程網 All Rights Reserved