-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path31.Binary Tree.cpp
128 lines (113 loc) · 4.23 KB
/
31.Binary Tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
//! ------------------------------ Binary Tree ---------------------------
//~ what is binary trees
//~ binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
//~ Binary Tree are Hierarchical Data Structures that use nodes to store data.
// binary tree structure its complte binary tree
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
//~ types of binary tree
//~ 1. Full Binary Tree: A binary tree is full if every node has 0 or 2 children.
// 1 2
// / \
// 2 2 3 2
// / \
// 0 4 5 0
//~ 2. Complete Binary Tree: A binary tree is complete if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.
// 1 2
// / \
// 2 2 3 2
// / \ / \
// 0 4 5 0 7 0
//~ 3. Perfect Binary Tree: A binary tree is perfect if all internal nodes have two children and all leaves are at the same level.
// 1 2
// / \
// 2 2 3 2
// / \ / \
// 0 4 5 0 7 0
//~ 4. Balanced Binary Tree: A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes.
// n = 8 log 2 8 = 3 so the height of the tree is 3
// 1 2
// / \
// 2 2 3 2
// / \ / \
// 0 4 5 0 7 0
//~ Binary Tree Representation cpp code
// we use mostly use struct to represent the binary tree
// struct is a custom data type that we can create in c++
// for creatig a node in which we have left pointer and right pointer and the data
struct Node
{
// data is where we store out values
int data;
// left pointer to point the new left node
struct Node *left;
// right pointer to point the new right node
struct Node *right;
// constructor to initialize the first nodes data and left and right pointer
// since its a root node currently there are no left and right node to point
// so our left and right pointer are pointing to null
Node(int val)
{
data = val;
left = NULL;
right = NULL;
}
};
//~ Binary Tree Traversal
// types of traversal
// 1. Inorder Traversal : left -> root -> right
// 2. Preorder Traversal : root -> left -> right
// 3. Postorder Traversal : left -> right -> root
//~ Inorder Traversal : left -> root -> right
//! first we visit left subtree left child then its root then right child and then right subtree left child then its root then right child and the root node
// tree 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// Inorder Traversal : 4 2 5 1 6 3 7
//~ Preorder Traversal : root -> left -> right
//! first we visit the root node then left subtree left child then its root then right child and then right subtree left child then its root then right child
// tree 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// Preorder Traversal : 1 2 4 5 3 6 7
//~ Postorder Traversal : left -> right -> root
// first we visit left subtree left child then its root then right child and then right subtree left child then its root then right child and the root node
// tree 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// Postorder Traversal : 4 5 2 6 7 3 1
//^ simple to remember the order of Traversal
//! inorder : root at center
//! preorder : root at first
//! postorder : root at last
//~ Inorder Traversal cpp code
void inorder(struct Node *root)
{
// if the root is null then return
if (root == NULL)
{
return;
}
// first we visit the left child
inorder(root->left);
// then we visit the root node
cout << root->data << " ";
// then we visit the right child
inorder(root->right);
}
int main()
{
return 0;
}