{"id":587,"date":"2013-05-16T15:38:19","date_gmt":"2013-05-16T14:38:19","guid":{"rendered":"http:\/\/oprsteny.cz\/?p=587"},"modified":"2013-05-16T15:38:19","modified_gmt":"2013-05-16T14:38:19","slug":"algorithms-binary-tree","status":"publish","type":"post","link":"https:\/\/oprsteny.cz\/?p=587","title":{"rendered":"Algorithms: Binary tree"},"content":{"rendered":"

Simple implementation of binary tree in C++<\/p>\n

\"\"<\/p>\n

#include<iostream.h>\r\n\/**************************************\r\n Tree Node structure - contains data, left and right children\r\n**************************************\/\r\ntemplate <class T>\r\n  struct TreeNode {\r\n  T data;\r\n  TreeNode *left;\r\n  TreeNode *right;\r\n\r\n  TreeNode() {\r\n    left = NULL;\r\n    right = NULL;\r\n    this->data = T();\r\n  }\r\n\r\n  TreeNode(T data) {\r\n    left = NULL;\r\n    right = NULL;\r\n    this->data = data;\r\n  }\r\n};\r\n\/**************************************\r\nBinary Tree class implementation\r\n**************************************\/\r\ntemplate <class T> class BinTree {\r\n  TreeNode<T> *root;\r\nprivate:\r\n  void Add(TreeNode<T> *node, T data){\r\n    if (data > node->data) {\r\n      if(node->right == NULL) {\r\n        TreeNode<T> *n = new TreeNode<T>(data);\r\n        node->right = n;\r\n      } else {\r\n      \/\/ go to right branch\r\n        Add(node->right, data);\r\n      }\r\n    } else if (data < node->data) {\r\n      if(node->left == NULL) {\r\n        TreeNode<T> *n = new TreeNode<T>(data);\r\n        node->left = n;\r\n      } else {\r\n      \/\/ go to left branch\r\n        Add(node->left, data);\r\n      }\r\n    } else {\r\n    \/\/ do nothing - we already have this node in tree\r\n    }\r\n  }\r\n\r\n  bool Find(TreeNode<T> *node, T data){\r\n    T nodeData = node->data;\r\n    cout << \" \" << nodeData;\r\n\r\n    if(nodeData == data) {\r\n      return true;\r\n    } else if(data > nodeData) {\r\n      if(node->right == NULL) {\r\n        return false;\r\n      } else {\r\n        return Find(node->right, data);\r\n      }\r\n    } else {\r\n      if(node->left == NULL) {\r\n        return false;\r\n      } else {\r\n        return Find(node->left, data);\r\n      }\r\n    }\r\n  }\r\npublic:\r\n  BinTree(){\r\n    root = NULL;\r\n  }\r\n\r\n  void Add(T data) {\r\n    if(root == NULL) {\r\n      TreeNode<int> *n = new TreeNode<int>(data);\r\n      root = n;\r\n    } else {\r\n      Add(root, data);\r\n    }\r\n  }\r\n\r\n  bool Find(T data) {\r\n    if(root->data == data){\r\n      cout << \" \" << data;\r\n      return true;\r\n    } else {\r\n      return Find(root, data);\r\n    }\r\n  }\r\n};\r\n\r\nint main (int argc, char *argv[]) {\r\n  BinTree<int> *tree = new BinTree<int>();\r\n\r\n  tree->Add(12);\r\n  tree->Add(15);\r\n  tree->Add(18);\r\n  tree->Add(14);\r\n  tree->Add(5);\r\n  tree->Add(8);\r\n  tree->Add(7);\r\n  tree->Add(2);\r\n  tree->Add(4);\r\n  tree->Add(1);\r\n\r\n  cout << \"Searching for 7:\";\r\n  cout << \" - \" << (tree->Find(7) ? \"FOUND\" : \"NOT FOUND\") << endl;\r\n}<\/pre>\n
Output (using the scenario on the picture above):<\/p>\n
Searching for 7: 12 5 8 7 - FOUND<\/pre>\n","protected":false},"excerpt":{"rendered":"
Simple implementation of binary tree in C++<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"Simple implementation of binary tree in C++","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[15,150,9],"tags":[148,156,149],"class_list":["post-587","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-c-development","category-development","tag-algorithms-2","tag-binary-tree","tag-cpp"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p3nYbe-9t","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/posts\/587","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=587"}],"version-history":[{"count":1,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/posts\/587\/revisions"}],"predecessor-version":[{"id":588,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=\/wp\/v2\/posts\/587\/revisions\/588"}],"wp:attachment":[{"href":"https:\/\/oprsteny.cz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oprsteny.cz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}