#include using namespace std; // input to enter: Number to search in tree class Node { public: Node* next = NULL; int num; Node(int n) : num(n) {} void SetNext(Node* n) { next = n; } }; ///////////////////////// class IntBinTreeNode { public: IntBinTreeNode* LeftNode = NULL; IntBinTreeNode* RightNode = NULL; int num; IntBinTreeNode(int n) : num(n) {} void SetLeft(IntBinTreeNode* next) { LeftNode = next; } void SetRight(IntBinTreeNode* next) { RightNode = next; } }; int GetChainSum(Node first) { if (first.next != NULL) return first.num + GetChainSum(*first.next); return first.num; } void ShowTreeValues(IntBinTreeNode b) // The function checks all left nodes first , after finished, goes back and checks the right nodes { cout << b.num << endl; if (b.LeftNode != NULL) ShowTreeValues(*b.LeftNode); if (b.RightNode != NULL) ShowTreeValues(*b.RightNode); } int GetSumInTree(IntBinTreeNode b) { if (b.LeftNode != NULL && b.RightNode != NULL) return b.num + GetSumInTree(*b.LeftNode) + GetSumInTree(*b.RightNode); else if (b.LeftNode != NULL && b.RightNode == NULL) return b.num + GetSumInTree(*b.LeftNode); else if (b.LeftNode == NULL && b.RightNode != NULL) return b.num + GetSumInTree(*b.RightNode); else return b.num; } bool FindValueInTree(IntBinTreeNode b, int searchNum) { bool check = (b.num == searchNum); if (check) return true; if (b.LeftNode != NULL && b.RightNode != NULL) return FindValueInTree(*b.LeftNode, searchNum) + FindValueInTree(*b.RightNode, searchNum); else if (b.LeftNode != NULL && b.RightNode == NULL) return FindValueInTree(*b.LeftNode, searchNum); else if (b.LeftNode == NULL && b.RightNode != NULL) return FindValueInTree(*b.RightNode, searchNum); else return false; } //////////////////////////// int main() { //Normal Node Node* p; //Points to each node in the chain Node e(1); Node another(2); Node last(3); e.SetNext(&another); another.SetNext(&last); last.SetNext(new Node(10)); p = &e; // 1 --- > 2 --- > 3 --- > NULL cout << "Normal node : " << endl; while (p->next != NULL) { cout << p->num << endl; p = p->next; } if (p != NULL) cout << p->num << endl; // last 1 int chainSum = GetChainSum(e); cout << "\nChain sum : " << chainSum << "\n\n"; //Binary tree of integers /* 1 2 3 4 5 6 */ //IntBinTreeNode first IntBinTreeNode first(1); IntBinTreeNode second(2); IntBinTreeNode third(3); IntBinTreeNode fourth(4); IntBinTreeNode fifth(5); IntBinTreeNode sixth(6); first.SetLeft(&second); first.SetRight(&third); second.SetLeft(&fourth); third.SetLeft(&fifth); third.SetRight(&sixth); cout << "All tree values : \n"; ShowTreeValues(first); int sum = GetSumInTree(first); int search; cout << "\nSum of tree values : " << sum << "\n\n"; cout << "Enter number to search : "; cin >> search; bool check = FindValueInTree(first, search); if (check) cout << "\n" << "True" << "\n"; else cout << "\n" << "False" << "\n"; return 1; }

Linked lists and binary tree functions