ITEC33(finals) Flashcards
It is a pictorial representation of a set of objects where some of objects are connected by links.
Graph
The interconnected objects are represented by points.
Vertices
Links that connect the vertices.
Edges
Two nodes or vertices are adjacent of they are connected to each other through an edge.
Adjacency
It represents a sequence of edges between the two vertices.
Path
Adds a vertex to the graph
Add Vertex
Adds an edge between the two vertices of the graph.
Add Edge
Displays a vertex of the graph.
Display Vertex
Algorithm traverse a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search.
Depth First Search (DFS)
Algorithm traverse a graph in a breadthward motion and uses a queue to remember to get the next vertex to start a search.
Bread First Search(BFS)
Represents the nodes connected by edges.
Tree
Refers to the sequence of nodes along the edges of a tree.
Path
The node at the top of the tree.
Root
Any node except the root node has one edge upward to a node.
Parent
The node below a given node connected by each edge downward.
Child
The node which does not have any child node.
Leaf
Represents the descendants of a node.
Subtree
Refers to the checking the value of a node when control is on a node.
Visiting
It means passing through nodes in a specific order.
Traversing
It represents the generation of a node.
Levels
It represents a value of a node based on which operation is to be carried out for a node.
Keys
Inserts an element in a tree/ create a tree.
Insert
Searches an element in a tree.
Search
Traverses a tree in a pre-order manner.
Preorder Traversal
Traverses a tree in a in-order manner.
Inorder Traversal
Traverses a tree in a post-order manner.
Postorder Traversal
Is a process to visit all the nodes of a tree and may print their values too.
Tree Traversal
In this traversal method, the first subtree is visited first, then the root and later the right subtree.
In-Order Tree Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
Pre-Order Traversal
In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.
Post-Order Traversal
It is a hierarchical data structure in which node has at most two children generally referred as left child and right child.
Binary Tree
It has a root node and every node has at most 2 children.
Rooted Binary Tree
It is a tree in which every node in the tree has either 0 or 2 children.
Full Binary Tree
It is a binary tree in which all interior nodes have two children and all levels have the same depth or same level.
Perfect Binary Tree
It is a binary tree in which every level, except possible the last, is completely filled, and all nodes are as far left as possible.
Complete Binary Tree
A binary tree is height balanced if it satisfies the following concept.
Balance Binary Tree
It is a tree where each parent node has only 1 child node. It behaves like a linked list.
Degenerate Tree
A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically named them the left and right child.
Binary Tree Data Structure
Always initiate analyzing tree at the root node and then move further to either the right or left subtree of the root node depending upon the elements to be located is either less or greater than the root.
Search Operation
First, the root node is inserted, then the next value is compared with the root node. If the value is greater than root, it is added to the right subtree, and if it is lesser than the root, it is added to the left subtree.
Insert Operation
It is the most advanced and complex among all other operation.
Delete Operation
