Binary Tree

3 Key excerpts on "Binary Tree"

• 

  eBook - ePub

  Hands-On Data Structures and Algorithms with Python

  Write complex and powerful code using the latest features of Python 3.7, 2nd Edition

  • Dr. Basant Agarwal(Author)
  • 2018(Publication Date)
  • Packt Publishing

    (Publisher)

  Trees

  A tree is a hierarchical form of data structure. In the case of other data structures such as lists, queues, and stacks that we have discussed till now, the items are stored in a sequential way. However, in the case of a tree data structure, there is a parent-child relationship between the items. The top of the tree's data structure is known as a root node . This is the ancestor of all other nodes in the tree.

  Tree data structures are very important owing to their use in various important applications. Trees are used for a number of things, such as parsing expressions, searches, storing data, manipulating data, sorting, priority queues, and so on. Certain document types, such as XML and HTML, can also be represented in a tree form. We shall look at some of the uses of trees in this chapter.

  In this chapter, we will cover the following topics:

  • Terms and definitions of trees
  • Binary Trees and binary search trees
  • Tree traversal
  • Ternary search tree

  Passage contains an image

  Technical requirements

  All of the source code discussed in this chapter is provided in the GitHub repository for this book at https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-3.x-Second-Edition/tree/master/Chapter06 .

  Passage contains an image

  Terminology

  Let's consider some terminology associated with tree data structures.

  To understand trees, we need to first understand the basic concepts related to them. A tree is a data structure in which data is organized in a hierarchical form. The following diagram contains a typical tree consisting of character nodes lettered A through to M :

  Here is a list of terms associated with a tree:

  • Node : Each circled letter in the preceding diagram represents a node. A node is any data structure that actually stores the data.
  • Root node

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structures Through C

  Learn the fundamentals of Data Structures through C

  • Yashavant Kanetkar(Author)
  • 2020(Publication Date)
  • BPB Publications

    (Publisher)

  Chapter 07

  Trees

  Of Herbs, Shrubs and Bushes

  Why This Chapter Matters?

  Nature is man’s best teacher. In every walk of life man has explored nature, learnt his lessons and then applied the knowledge that nature offered him to solve every-day problems that he faced at work- place. It isn’t without reason that there are data structures like Trees, Binary Trees, Search Trees, AVL Trees, Forests, etc. Trees are non-linear data structures. They have many applications in Computer Science, hence you must understand them comprehensively.

   

  I f large input data is stored in a linked list then time required to access the data is prohibitive. In such cases a data structure called Tree is used. This data structure is often used in constructing the file systems and evaluation of arithmetic expressions. This data structure gives a running time of O (log n) for most operations.

  Like linked lists, a tree also consists of several nodes. Each node may contain links that point to other nodes in the tree. So a tree can be used to represent a person and all of his descendants as shown in Figure 7-1 .

  Figure 7-1. A tree structure .

  Note that each node in this tree contains a name for data and one or more pointers to the other tree nodes. Although a tree may contain any number of pointers to the other tree nodes, a large number of have at the most two pointers to the other tree nodes. Such trees are called Binary Trees .

  Binary Trees

  Let us begin our study of Binary Trees by discussing some basic concepts and terminology.

  A Binary Tree is a finite set of elements that is either empty or is partitioned into three disjoint sub-sets. The first sub-set contains a single element called the root of the tree. The other two sub-sets are themselves Binary Trees, called the left and right sub-trees of the original tree. A left or right sub-tree can be empty.

  Each element of a Binary Tree is called a node of the tree. The tree shown in Figure 7-2(a) consists of nine nodes with A as its root. Its left sub-tree is rooted at B and its right sub-tree is rooted at C . This is indicated by the two branches emanating from A to B on the left and to C on the right. The absence of a branch indicates an empty sub-tree. For example, the left sub-tree of the Binary Tree rooted at C and the right sub-tree of the Binary Tree rooted at E are both empty. The Binary Trees rooted at D , G , H and I

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Essential Algorithms

  A Practical Approach to Computer Algorithms Using Python and C#

  • Rod Stephens(Author)
  • 2019(Publication Date)
  • Wiley

    (Publisher)

  ⌋ is also 2.

  This provides a concise format for storing any complete Binary Tree in an array. Working with this kind of tree can be a bit awkward and confusing, however, particularly if you need to resize the array frequently. For those reasons, you may want to stick to using classes to build trees.

  NOTE

  Now that you know more about trees, you may want to reread the section “Heapsort” in Chapter 6 to see how you can use classes instead of an array to build a heap.

  Tree Traversal

  One of the most basic and important tree operations is traversal. In a traversal, the goal is for the algorithm to visit all the nodes in the tree in some order and perform an operation on them. The most basic traversal simply enumerates the nodes so that you can see their ordering in the traversal.

  TRAVERSAL AND SEARCHING

  Many algorithms search a tree for a particular node. In general, these searches are traversals, and you can use any traversal as the basis for a search.

  Chapter 11 describes some special cases in which you can use the structure of the data in a tree to search it efficiently.

  Binary Trees have four kinds of traversals.

  • Preorder: This traversal visits a node before visiting its children.
  • Inorder: This traversal visits a node's left child, then the node, then its right child.
  • Postorder: This traversal visits a node's children before visiting the node.
  • Breadth-first: This traversal visits all the nodes at a given level in the tree before visiting any nodes at lower levels.

  Preorder, postorder, and breadth-first traversals make sense for any kind of tree. Inorder traversals are usually only defined for Binary Trees.

  Sign up to read

  Learn more about book