Page 1 :
i 8.15 THREADED BINARY TREES, , Consider the linked representation of any binary tree, we notice that, half of the entries in, , the pointer fields LEFT and RIGHT will contain null entries. This, , space may be more, efficiently, , used by replacing the null entries by special pointers, called Threads, which, point to the nodes higher in the trees. Such trees are called Threaded Trees., , Note: A binary tree with n nodes, when n > 0 has exactly n + 1 null links., , Threads in a binary tree must be distinguished from normal pointers. In the graphical, representation of a threaded binary tree, the threads are shown by dotted lines. In computer, memory, an extra field, called tag or flag is used to distinguish a thread from a normal, pointer. Trees can be threaded using one-way threading or two-way threading. In a oneway threading a therad will appear in the right field of the node and will point to the, , , e; and in two-way threading of tree a thread, will also appear in the left field of a node and will point to the preceding node in the, inorder traversal of tree. So, there are many ways to threada bianry tree, These are:, , 1. The right NULL pointer of each node can be replaced by a thread to the successor of, that node under in-order traversal called a ri, , ht thread, and the tree will called a, right threaded tree, . anil Shp eae will, , 2. The left NULL pointer of each node can be replaced by, , that node under in-order traversal culled a loft-tt, threaded tree., , a thread to the predecessor of, ‘road and the tree will called a left, , , , Scanned with CamScanner
Page 2 :
pe a =, | g, Both left and right NULL pointers can b, , : e use! i, * that node, respectively, under in-order t (to point to predecessor and successor of, , Taversal. Such a tree is called a fully threaded, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | tree:, |, |, | . A J, ;, !, 1, ; _, B rs ' ‘* c ;, 1 iodo ", / j= tk \, a / 1 }, ee a, INULL] F a ° G a NULLI p “4 nut} e [Nutt, : ¥, I, t, i, f, é, wf, NULL] H e-T, (a) Right threaded binary tree, ° A e, f, !, 1, 1, !, 2 B e ‘ od c, 1 ~ = T, t \ \, : XN, / i NS, Nutt| F [NULL] /-t+-e | G [NULL » | o spo |e |NULL, z J Lo, 4, 4, ‘, ‘, 7, ¢, ‘, \ | H INULL, (b) Left threaded binary tree, , , , Scanned with CamScanner
Page 3 :
A |, ae, a, 'y, 'y, !, 1, * B ° a e c ., !, !, + ; rt it, 1 i Zt ot, a e 4 iN, V7 7 5 \ ot ‘S, NULL] F | eq |G] ¢ e]o]- Pr | E JNULL, £, 4 t, i :, i ', 1 ;, T, e H "|, , , , , , , , , , , , (c) Fully threaded binary tree, , Fig. 8.64., , To implement a right threaded binary tree an one extra field rthread is used. If, rthread is assigned to 1 then its corresponding right link represents a thread and if rthread, is assigned to 0 then right link represents an ordinary link connecting to the right sub-tree,, The C node structure can be defined as:, , struct node, , {, char info;, struct node * left;, struct node * right;, int rthread; /*1 indicate threaded link, 0 indicate ordinary link */, ie, , typedef struct node * NODE;, , Similarly to implement a left threaded binary tree, we need one extra field 1thread., It is assigned to 1 indicate the presence of thread and 0 indicate an ordinary link connecting, to the left sub-tree. The C node structure can be defined as:, , struct node, , {, char info;, struct node * left;, struct node * right;, int lthread;, , }, , typedef struct node * NODE;, , Scanned with CamScanner
Page 4 :
To implement fully threaded binary tree, we need t, cabread as defined earlier are used and the C node Sit ibe ane erdoicrd a ‘head ane, , struct node, , {, , char info;, , struct node * left;, struct node * right;, int lthread;, , int rthread;, , WA, , typedef struct node * NODE;, , a |} nobE +], , , , , , , , , , , , , , , , , , fr ft f 7, , INFO Left Right Ithread _—rthread, , Fig. 8.65 Node of a threaded binary tree, , Now, we have seen that if left or right pointer of a node is NULL then it is made a, thread pointing to the inorder predecessor or inorder successor of the node. First node in, inorder traversal has no predecessor and last node has no successor, sO the left pointer of, the left most node which is the first node in order traversal and the right pointer of the right, most node which is the last node in inorder traversal contains NULL. So we can take a, dummy node called the header node and we will represent are tree as the left sub-tree of, this header node. Left pointer of this header node will point to the root node of our tree., When our tree will be empty then left pointer of this header node will be a thread ponting to, , itself., So, now the left most node and right most node of our two-way threaded binary tree will, , not contain NULL, they will contain threads pointing to this header node., The structure of a node in a threaded binary tree will be as:, typedef enum{thread, link}boolean;, , struct node, , {, , struct node * leftptr;, boolean left;, int info;, , struct node * rightptr;, boolean right;, , };, , Here we have taken two boolean members left and right to differentiate between a thread, and link, These members can take values thread or link., , Scanned with CamScanner
Page 5 :
If left = link pointer leftptr points to the left child of the node., If left = thread pointer leftptr is a thread pointing to inorder predecessor of the ods, , If right = link pointer rightptr points to the rightchild of the node., If right = thread pointer rightptr is a thread pointing to inorder successor of the node,, , , , HEADER NODE, , , , , , , , WA a, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 1, |, \, 1, I, — A e |, !, ¥, ' ;, 1 ‘ I, 1 . 1, ' H !, I e, 2 B i —o Cc, cE ! 1 +4 1, I ! 1 \ i 4, if ; \ rant, , , \ . |, -j-- F eo’ e ev ‘wo D e- re E e4yf, ,, 4, /, ,, 4, x, [* a] +4, Fig. 8.66., , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , Scanned with CamScanner
