Posted onEdited onInC++Word count in article: 4.8kReading time ≈17 mins.
Binary Tree Practice
#algorithm/binaryTree
Binary Search Tree
// Binary Search Tree - Implemenation in C++ // Simple program to create a BST of integers and search an element in it #include<iostream> usingnamespace std; //Definition of Node for Binary search tree structBstNode { int data; BstNode* left; BstNode* right; };
// Function to create a new Node in heap BstNode* GetNewNode(int data){ BstNode* newNode = newBstNode(); newNode->data = data; newNode->left = newNode->right = NULL; return newNode; }
// To insert data in BST, returns address of root node BstNode* Insert(BstNode* root,int data){ if(root == NULL) { // empty tree root = GetNewNode(data); } // if data to be inserted is lesser, insert in left subtree. elseif(data <= root->data) { root->left = Insert(root->left,data); } // else, insert in right subtree. else { root->right = Insert(root->right,data); } return root; } //To search an element in BST, returns true if element is found boolSearch(BstNode* root,int data){ if(root == NULL) { returnfalse; } elseif(root->data == data) { returntrue; } elseif(data <= root->data) { returnSearch(root->left,data); } else { returnSearch(root->right,data); } } intmain(){ BstNode* root = NULL; // Creating an empty tree /*Code to test the logic*/ root = Insert(root,15); root = Insert(root,10); root = Insert(root,20); root = Insert(root,25); root = Insert(root,8); root = Insert(root,12); // Ask user to enter a number. int number; cout<<"Enter number be searched\n"; cin>>number; //If number is found, print "FOUND" if(Search(root,number) == true) cout<<"Found\n"; else cout<<"Not Found\n"; }
Level Order Traversal
// Function to print Nodes in a binary tree in Level order voidLevelOrder(Node *root) { if (root == NULL) return; queue<Node *> Q; Q.push(root); // while there is at least one discovered node while (!Q.empty()) { Node *current = Q.front(); Q.pop(); // removing the element at front cout << current->data << " "; if (current->left != NULL) Q.push(current->left); if (current->right != NULL) Q.push(current->right); } }
Source Code
/* Binary tree - Level Order Traversal */ #include<iostream> #include<queue> usingnamespace std;
// Function to print Nodes in a binary tree in Level order voidLevelOrder(Node *root) { if (root == NULL) return; queue<Node *> Q; Q.push(root); // while there is at least one discovered node while (!Q.empty()) { Node *current = Q.front(); Q.pop(); // removing the element at front cout << current->data << " "; if (current->left != NULL) Q.push(current->left); if (current->right != NULL) Q.push(current->right); } } // Function to Insert Node in a Binary Search Tree Node *Insert(Node *root, char data) { if (root == NULL) { root = newNode(); root->data = data; root->left = root->right = NULL; } elseif (data <= root->data) root->left = Insert(root->left, data); else root->right = Insert(root->right, data); return root; }
intmain() { /*Code To Test the logic Creating an example tree M / \ B Q / \ \ A C Z */ Node *root = NULL; root = Insert(root, 'M'); root = Insert(root, 'B'); root = Insert(root, 'Q'); root = Insert(root, 'Z'); root = Insert(root, 'A'); root = Insert(root, 'C'); // Print Nodes in Level Order. LevelOrder(root); }
Binary Tree Traversal
PreOrder
// Function to visit nodes in Preorder voidPreorder(struct Node *root) { // base condition for recursion // if tree/sub-tree is empty, return and exit if (root == NULL) return;
printf("%c ", root->data); // Print data Preorder(root->left); // Visit left subtree Preorder(root->right); // Visit right subtree }
InOrder
// Function to visit nodes in Inorder voidInorder(Node *root) { if (root == NULL) return;
Inorder(root->left); // Visit left subtree printf("%c ", root->data); // Print data Inorder(root->right); // Visit right subtree }
PostOrder
// Function to visit nodes in Postorder voidPostorder(Node *root) { if (root == NULL) return;
Postorder(root->left); // Visit left subtree Postorder(root->right); // Visit right subtree printf("%c ", root->data); // Print data }
// Function to visit nodes in Preorder voidPreorder(struct Node *root) { // base condition for recursion // if tree/sub-tree is empty, return and exit if (root == NULL) return;
printf("%c ", root->data); // Print data Preorder(root->left); // Visit left subtree Preorder(root->right); // Visit right subtree }
// Function to visit nodes in Inorder voidInorder(Node *root) { if (root == NULL) return;
Inorder(root->left); // Visit left subtree printf("%c ", root->data); // Print data Inorder(root->right); // Visit right subtree }
// Function to visit nodes in Postorder voidPostorder(Node *root) { if (root == NULL) return;
Postorder(root->left); // Visit left subtree Postorder(root->right); // Visit right subtree printf("%c ", root->data); // Print data }
// Function to Insert Node in a Binary Search Tree Node *Insert(Node *root, char data) { if (root == NULL) { root = newNode(); root->data = data; root->left = root->right = NULL; } elseif (data <= root->data) root->left = Insert(root->left, data); else root->right = Insert(root->right, data); return root; }
intmain() { /*Code To Test the logic Creating an example tree M / \ B Q / \ \ A C Z */ Node *root = NULL; root = Insert(root, 'M'); root = Insert(root, 'B'); root = Insert(root, 'Q'); root = Insert(root, 'Z'); root = Insert(root, 'A'); root = Insert(root, 'C'); // Print Nodes in Preorder. cout << "Preorder: "; Preorder(root); cout << "\n"; // Print Nodes in Inorder cout << "Inorder: "; Inorder(root); cout << "\n"; // Print Nodes in Postorder cout << "Postorder: "; Postorder(root); cout << "\n"; }
//recursion classSolution { public: intmaxDepth(TreeNode* root){ if(!root)return0; int n = maxDepth(root->left); int m = maxDepth(root->right); returnmax(n, m) + 1; } };
struct Node{ int val; Node*left; Node*right; Node*next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */
