درخت ها

[hamidli87]

لطفا اگر کسی این برنامه ها را به زبان c++ داره برام بفرسته ممنون می شم
.تابعی بنویسید که پیمایش preorder درخت را که به صورت لیست پیوندی میباشد، چاپ کند.
2.تابعی بنویسید که max یک درخت دودویی عددی را برگرداند.
3.درخت جستجوی دودویی را به صورت بازگشتی بنویسید.

[آرین]

کد:

   1.
      #ifndef QUEUE_H
   2.
      #define QUEUE_H
   3.
      #include <iostream>
   4.
      using namespace std;
   5.
       
   6.
      template <class ItemType>
   7.
      struct TreeNode
   8.
      {
   9.
      ItemType info;
  10.
      TreeNode* left;
  11.
      TreeNode* right;
  12.
      };
  13.
       
  14.
       
  15.
      template <class ItemType>
  16.
      class TreeType
  17.
      {
  18.
      public:
  19.
      TreeType(); // constructor
  20.
      ~TreeType(); // destructor
  21.
      TreeType(const TreeType& originalTree); // copy constructor
  22.
      void operator=(const TreeType& originalTree); // assignment operator
  23.
      void Clear(); // clear the tree
  24.
      bool IsEmpty() const; // test for empty tree
  25.
      bool IsFull() const; // test for full tree
  26.
      int LengthIs() const; // return number of items in tree
  27.
      void Find(ItemType& item, bool& found) const; // retrieve an item
  28.
      void InsertItem(ItemType item); // insert an item
  29.
      void DeleteItem(ItemType item); // delete an item
  30.
      void PrintInOrder(std::ostream& outFile) const; // print the tree in order
  31.
      void PrintPreOrder(std::ostream& outFile) const; // print the tree in preorder
  32.
      void PrintPostOrder(std::ostream& outFile) const; // print the tree in post order
  33.
       
  34.
      private:
  35.
      TreeNode* root;
  36.
      void Destroy(TreeNode*& tree);
  37.
      void CopyTree(TreeNode*& copy, const TreeNode* originalTree);
  38.
      void Insert(TreeNode*& tree, ItemType item);
  39.
      void DeleteNode(TreeNode*& tree);
  40.
      void Delete(TreeNode*& tree, ItemType item);
  41.
      int CountNodes(TreeNode* tree);
  42.
      void Retrieve(TreeNode* tree, ItemType& item, bool& found);
  43.
      }
  44.
       
  45.
      //-----------------------------------------------------------------------------
  46.
      //CONSTRUCTOR
  47.
      //-----------------------------------------------------------------------------
  48.
      template <class ItemType>
  49.
      TreeType<ItemType>::TreeType()
  50.
      {
  51.
      root = NULL;
  52.
      }
  53.
       
  54.
       
  55.
      //-----------------------------------------------------------------------------
  56.
      //DECONSTRUCTOR
  57.
      //-----------------------------------------------------------------------------
  58.
      void Destroy(TreeNode*& tree);
  59.
       
  60.
      template <class ItemType>
  61.
      TreeType<ItemType>::~TreeType()
  62.
      {
  63.
      destroy(root);
  64.
      }
  65.
       
  66.
      void Destroy(TreeNode*& tree)
  67.
      {
  68.
      if (tree != NULL)
  69.
      {
  70.
      Destroy(tree->left);
  71.
      Destroy(tree->right);
  72.
      delete tree;
  73.
      }
  74.
      }
  75.
       
  76.
      //------------------------------------------------------------------------------
  77.
      //COPY CONSTRUCTOR
  78.
      //-----------------------------------------------------------------------------
  79.
      void CopyTree(TreeNode*& copy, const TreeNode* originalTree);
  80.
       
  81.
      template <class ItemType>
  82.
      TreeType<ItemType>::TreeType(const TreeType& originalTree)
  83.
      {
  84.
      CopyTree(root, originalTree.root);
  85.
      }
  86.
       
  87.
      template <class ItemType>
  88.
      void TreeType<ItemType>::operator=(const TreeType& originalTree)
  89.
      {
  90.
      if (&originalTree == this)
  91.
      return;
  92.
      Destroy(root);
  93.
      CopyTree(root, originalTree.root);
  94.
      }
  95.
       
  96.
      void CopyTree(TreeNode*& copy, const TreeNode* originalTree)
  97.
      {
  98.
      if (originalTree == NULL)
  99.
      copy = NULL;
 100.
      else
 101.
      {
 102.
      copy = new TreeNode;
 103.
      copy->info=originalTree->info;
 104.
      CopyTree(copy->left, originalTree->left);
 105.
      CopyTree(copy->right, originalTree->right);
 106.
      }
 107.
      }
 108.
       
 109.
      //-----------------------------------------------------------------------------
 110.
      //INSERT ITEM
 111.
      //-----------------------------------------------------------------------------
 112.
      void Insert(TreeNode*& tree, ItemType item);
 113.
       
 114.
      template <class ItemType>
 115.
      void TreeType<ItemType>::InsertItem(ItemType item)
 116.
      {
 117.
      Insert(root, item);
 118.
      }
 119.
       
 120.
      void Insert(TreeNode*& tree, ItemType item)
 121.
      {
 122.
      if (tree == NULL)
 123.
      {
 124.
      tree = new TreeNode;
 125.
      tree->right = NULL;
 126.
      tree->left = NULL;
 127.
      tree->info = item;
 128.
      }
 129.
      else if (item < tree->info)
 130.
      Insert(tree->left, item);
 131.
      else
 132.
      Insert(tree->right, item);
 133.
      }
 134.
       
 135.
      //-----------------------------------------------------------------------------
 136.
      //DELETE ITEM
 137.
      //-----------------------------------------------------------------------------
 138.
      void DeleteNode(TreeNode*& tree);
 139.
       
 140.
      void Delete(TreeNode*& tree, ItemType item);
 141.
       
 142.
      template <class ItemType>
 143.
      void TreeType<ItemType>::DeleteItem(ItemType item)
 144.
      {
 145.
      Delete(root, item);
 146.
      }
 147.
       
 148.
      void Delete(TreeNode*& tree, ItemType item)
 149.
      {
 150.
      if (item < tree->info)
 151.
      Delete(tree->left, item);
 152.
      else if (item > tree->info)
 153.
      Delete(tree->right, item);
 154.
      else
 155.
      DeleteNode(tree);
 156.
      }
 157.
       
 158.
      //-----------------------------------------------------------------------------
 159.
      //IS FULL
 160.
      //-----------------------------------------------------------------------------
 161.
      template <class ItemType>
 162.
      bool TreeType<ItemType>::IsFull() const
 163.
      {
 164.
      TreeNode* location;
 165.
       
 166.
      try
 167.
      {
 168.
      location = new TreeNode;
 169.
      delete location;
 170.
      return false;
 171.
      }
 172.
      catch(std::bad_alloc exception)
 173.
      {
 174.
      return true;
 175.
      }
 176.
      }
 177.
       
 178.
      //-----------------------------------------------------------------------------
 179.
      //IS EMPTY
 180.
      //-----------------------------------------------------------------------------
 181.
      template <class ItemType>
 182.
      bool TreeType<ItemType>::IsEmpty() const
 183.
      {
 184.
      return root == NULL;
 185.
      }
 186.
       
 187.
      //-----------------------------------------------------------------------------
 188.
      //LENGTH IS
 189.
      //-----------------------------------------------------------------------------
 190.
      int CountNodes(TreeNode* tree);
 191.
       
 192.
      template <class ItemType>
 193.
      int TreeType<ItemType>::LengthIs() const
 194.
      {
 195.
      return CountNodes(root);
 196.
      }
 197.
       
 198.
      int CountNodes(TreeNode* tree)
 199.
      {
 200.
      if (tree == NULL)
 201.
      return 0;
 202.
      else
 203.
      return CountNodes(tree->left)+CountNodes(tree->right)+1;
 204.
      }
 205.
      //-----------------------------------------------------------------------------
 206.
      //FIND
 207.
      //-----------------------------------------------------------------------------
 208.
      void Retrieve(TreeNode* tree, ItemType& item, bool& found);
 209.
      template <class ItemType>
 210.
      void TreeType<ItemType>::Find(ItemType& item, bool& found) const
 211.
      {
 212.
      Retrieve(root, item, found)
 213.
      }
 214.
       
 215.
      void Retrieve(TreeNode* tree, ItemType& item, bool& found)
 216.
      {
 217.
      if (tree == NULL)
 218.
      found = false;
 219.
      else if (item < tree->info)
 220.
      Retrieve(tree->left, item, found);
 221.
      else if (item > tree->info)
 222.
      Retrieve(tree->right, item, found);
 223.
      else
 224.
      {
 225.
      item = tree->info;
 226.
      found = true;
 227.
      }
 228.
      }
 229.
      //-----------------------------------------------------------------------------
 230.
      //Clear
 231.
      //-----------------------------------------------------------------------------
 232.
      template <class ItemType>
 233.
      void TreeType<ItemType>::Clear()
 234.
      {
 235.
      ~TreeType():
 236.
      }
 237.
       
 238.
      #endif

[آرین]

کد:

         #include<iostream.h>
          #include<conio.h>
          #include<stdio.h>
          #include<stdlib.h>
          struct node
          {
               int data;
               node *left;
               node *right;
          };

          node *tree=NULL;
          node *insert(node *tree,int ele);

          void preorder(node *tree);
          void inorder(node *tree);
          void postorder(node *tree);
          int count=1;

          void main()
          {
               clrscr();
               int ch,ele;
               do
               {
                    clrscr();
                    cout<<"\n\t\a\a1----INSERT A NODE IN A BINARY TREE.\a\a";
                    cout<<"\n\t\a\a2----PRE-ORDER TRAVERSAL.\a\a";
                    cout<<"\n\t\a\a3----IN-ORDER TRAVERSAL.\a\a";
                    cout<<"\n\t\a\a4----POST-ORDER TRAVERSAL.\a\a";
                    cout<<"\n\t\a\a5----EXIT.\a\a";
                    cout<<"\n\t\a\aENTER CHOICE::\a\a";
                    cin>>ch;
                    switch(ch)
                    {
                         case 1:
                         cout<<"\n\t\a\aENTER THE ELEMENT::\a\a";
                         cin>>ele;
                         tree=insert(tree,ele);
                         break;

                         case 2:
                         cout<<"\n\t\a\a****PRE-ORDER TRAVERSAL OF A TREE****\a\a";
                         preorder(tree);
                         break;

                         case 3:
                         cout<<"\n\t\a\a****IN-ORDER TRAVERSAL OF A TREE****\a\a";
                         inorder(tree);
                         break;

                         case 4:
                         cout<<"\n\t\a\a****POST-ORDER TRAVERSAL OF A TREE****\a\a";
                         postorder(tree);
                         break;

                         case 5:
                         exit(0);
                    }
               }while(ch!=5);
          }

          node *insert(node *tree,int ele)
          {
               if(tree==NULL)
               {
                    tree=new node;
                    tree->left=tree->right=NULL;
                    tree->data=ele;
                    count++;
               }
               else
               if(count%2==0)
               tree->left=insert(tree->left,ele);
               else
               tree->right=insert(tree->right,ele);
               return(tree);
          }

          void preorder(node *tree)
          {
               if(tree!=NULL)
               {
                    cout<<tree->data;
                    preorder(tree->left);
                    preorder(tree->right);
                    getch();
               }
          }

          void inorder(node *tree)
          {
               if(tree!=NULL)
               {
                    inorder(tree->left);
                    cout<<tree->data;
                    inorder(tree->right);
                    getch();
               }
          }

          void postorder(node *tree)
          {
               if(tree!=NULL)
               {
                    postorder(tree->left);
                    postorder(tree->right);
                    cout<<tree->data;
                    getch();
               }
          }