Käynnissä

modify binary tree

The null links in a binary tree can be used to facilitate non-recursive traversal of the tree. For example, if we set each null right link ( except for the right link of the rightmost node) to point to its successor under inorder traversal, we have a right threaded binary tree. We can now do a non recursive inorder traversal of the tree in the following way:

Start from the root and go to the leftmost node by tracing the left links. Visit the node and go to its successor via its right link. If the right link is a thread link, it gives the successor; otherwise, move as far left as possible to locate the successor. Terminatewhen a null right link is reached.

This project is to modify the BinaryTree class to accommodate right-threaded binary trees. You need to add a flag variable to each node to indicate if a right link is a thread, write a method to turn an ordinary binaray tree into a right-threaded binary tree and write another mothod to demonstrate non-recursive inorder traversal.

Note that in a right-threaded binary tree, a node that has no right child and is itself the root of a left subtree should have its right link point to its parent. On the other hand, a node that has no right child and is itself the root of a right subtree should have its right link point to the parent of its highest ancestor. The parent of the root is set to null.

You will be given a test data file that contains several sequences of numbers. The numbers in each sequence are on the same line and separated by a space. You program should reach each sequence, build an ordinary binary search tree using simple insertion, right-threaded the tree and show each thread (i.e. if there is a thread from node 17 to node 41, then produce an output saying something like 17 -> 41), and print the numbers using non-recursive inorder traversal. Specifically, the main method must look like:

BinaryTree T;

While( not end of input ) {

Build an ordinary binary search tree T;

right-threaded T and show each thread;

print numbers in T via non-recursive inorder traversal;

}

The method for right-threading takes a pointer to a non-empty node N and a pointer to its parent P (or the parent of its highest ancestor as defined above). It starts with N being the root node of an ordinary binary search tree and P being null. If the current node has left child, use this left node and the current node to make a recursive call. If the current node has a right child, use this right node and P to make a recursive call. Otherwise, set its right pointer to P.

[url removed, login to view] file:

27 14 6

2 4 7 1 3 16 8

1 5 4 2 77 3

15 3 16 2 1 4 19 17 28 18

80 70 75 97 90 95 96 85 64 3 87 99 82

37 41 51 45 22 61 43 11 38 15 7 81 16 44 3 57

50 40 60 41 42 30 70 43 35 65 44 20 37 66 67 68

Taidot: Java

Näytä lisää: modify binary tree, right threaded binary tree, write a program for binary search, using binary search in java, use of binary search tree, use of binary, trees search, tree node, tree insertion, tree binary search, tree ancestor, the ancestor tree, simple binary tree, simple binary search tree program in java, simple binary search program in java, simple binary, search trees, search in tree, search in binary tree, search for trees, search binary tree, search binary search tree, search binary, search a tree, same ancestor

About the Employer:
( 2 reviews ) bronx, United States

Projektin tunnus: #477430

Myönnetty käyttäjälle:

interpb

Hey please check PMB Thanks

40 $ USD 0 päivässä
(54 arvostelua)
6.1

5 freelanceria on tarjonnut keskimäärin 46 $ tähän työhön

is00hcw

Hi, I am ready to start.

30 $ USD 0 päivässä
(46 arvostelua)
5.3
coderTim

hi, please check your pmb.

70 $ USD 1 päivässä
(50 arvostelua)
5.2
bup

I can do it.

60 $ USD 3 päivässä
(4 arvostelua)
1.0
programmingboy

Hello. I have a 8+ year experience of programming. This is McTechPro company in India. We have a powerful infrastructure and great software teams here. Your project looks so easy for me. We have many programmers an Lisää

30 $ USD 0 päivässä
(0 arvostelua)
0.0