Forums
New posts
Search forums
News
Security News
Technology News
Giveaways
Giveaways, Promotions and Contests
Discounts & Deals
Reviews
Users Reviews
Video Reviews
Support
Windows Malware Removal Help & Support
Mac Malware Removal Help & Support
Mobile Malware Removal Help & Support
Blog
Log in
Register
What's new
Search
Search titles only
By:
Search titles only
By:
Reply to thread
Menu
Install the app
Install
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Guides
Programming Guides & Questions
Binary tree threaded
Message
<blockquote data-quote="Bot" data-source="post: 1037723" data-attributes="member: 52014"><p>Yes, using a phoney head node (also known as a dummy node) is a common and convenient approach to simplify the construction of threaded binary trees. It helps in handling edge cases and provides a consistent starting point for traversals.</p><p></p><p>Here's a step-by-step explanation on how to construct the `ThreadedNode` class and thread the binary tree:</p><p></p><p>1. Define the `ThreadedNode` class, which should have a reference to a `BinaryNode` object, left and right pointers (which can also be of `ThreadedNode` type), and two boolean variables `leftThread` and `rightThread` to indicate if the left and right pointers are threads or not.</p><p></p><p>```java</p><p>public class ThreadedNode {</p><p> BinaryNode node;</p><p> ThreadedNode left, right;</p><p> boolean leftThread, rightThread;</p><p></p><p> public ThreadedNode(BinaryNode node) {</p><p> this.node = node;</p><p> left = null;</p><p> right = null;</p><p> leftThread = false;</p><p> rightThread = false;</p><p> }</p><p>}</p><p>```</p><p></p><p>2. Create the constructor `ThreadedNode(BinaryNode root)` that accepts a `BinaryNode` as the root of the binary tree to be threaded.</p><p></p><p>3. Initialize a dummy head node with null values and set its `rightThread` as false. This head node will serve as the starting point for the threaded tree construction.</p><p></p><p>```java</p><p>public ThreadedNode(BinaryNode root) {</p><p> this.node = null;</p><p> left = this;</p><p> right = this;</p><p> leftThread = true;</p><p> rightThread = false;</p><p></p><p> if (root == null) {</p><p> return;</p><p> }</p><p></p><p> // Continue with the threading process</p><p>}</p><p>```</p><p></p><p>4. Start the threading process. Perform an inorder traversal on the binary tree, and for each null left or right child, create a thread pointing to the inorder predecessor or successor, respectively.</p><p></p><p>You can create a helper function called `threadInOrder` that recursively threads the tree.</p><p></p><p>```java</p><p>private ThreadedNode prevNode = null;</p><p></p><p>private void threadInOrder(BinaryNode root) {</p><p> if (root == null) {</p><p> return;</p><p> }</p><p></p><p> // Traverse the left subtree</p><p> threadInOrder(root.left);</p><p></p><p> // Create a new ThreadedNode for the current BinaryNode</p><p> ThreadedNode currThreadedNode = new ThreadedNode(root);</p><p></p><p> // If the previous ThreadedNode exists</p><p> if (prevNode != null) {</p><p> // Set the right pointer of the previous ThreadedNode to the current ThreadedNode</p><p> prevNode.right = currThreadedNode;</p><p> prevNode.rightThread = true;</p><p></p><p> // Set the left pointer of the current ThreadedNode to the previous ThreadedNode</p><p> currThreadedNode.left = prevNode;</p><p> currThreadedNode.leftThread = true;</p><p> }</p><p></p><p> // Update the previous ThreadedNode to the current ThreadedNode</p><p> prevNode = currThreadedNode;</p><p></p><p> // Traverse the right subtree</p><p> threadInOrder(root.right);</p><p>}</p><p>```</p><p></p><p>5. Call the `threadInOrder` function in the constructor, passing the root of the binary tree as an argument.</p><p></p><p>```java</p><p>public ThreadedNode(BinaryNode root) {</p><p> // ...</p><p> // Initialize the dummy head node</p><p> // ...</p><p></p><p> // Start the threading process</p><p> threadInOrder(root);</p><p>}</p><p>```</p><p></p><p>Now, you should be able to construct a threaded binary tree using the `ThreadedNode(BinaryNode root)` constructor.</p></blockquote><p></p>
[QUOTE="Bot, post: 1037723, member: 52014"] Yes, using a phoney head node (also known as a dummy node) is a common and convenient approach to simplify the construction of threaded binary trees. It helps in handling edge cases and provides a consistent starting point for traversals. Here's a step-by-step explanation on how to construct the `ThreadedNode` class and thread the binary tree: 1. Define the `ThreadedNode` class, which should have a reference to a `BinaryNode` object, left and right pointers (which can also be of `ThreadedNode` type), and two boolean variables `leftThread` and `rightThread` to indicate if the left and right pointers are threads or not. ```java public class ThreadedNode { BinaryNode node; ThreadedNode left, right; boolean leftThread, rightThread; public ThreadedNode(BinaryNode node) { this.node = node; left = null; right = null; leftThread = false; rightThread = false; } } ``` 2. Create the constructor `ThreadedNode(BinaryNode root)` that accepts a `BinaryNode` as the root of the binary tree to be threaded. 3. Initialize a dummy head node with null values and set its `rightThread` as false. This head node will serve as the starting point for the threaded tree construction. ```java public ThreadedNode(BinaryNode root) { this.node = null; left = this; right = this; leftThread = true; rightThread = false; if (root == null) { return; } // Continue with the threading process } ``` 4. Start the threading process. Perform an inorder traversal on the binary tree, and for each null left or right child, create a thread pointing to the inorder predecessor or successor, respectively. You can create a helper function called `threadInOrder` that recursively threads the tree. ```java private ThreadedNode prevNode = null; private void threadInOrder(BinaryNode root) { if (root == null) { return; } // Traverse the left subtree threadInOrder(root.left); // Create a new ThreadedNode for the current BinaryNode ThreadedNode currThreadedNode = new ThreadedNode(root); // If the previous ThreadedNode exists if (prevNode != null) { // Set the right pointer of the previous ThreadedNode to the current ThreadedNode prevNode.right = currThreadedNode; prevNode.rightThread = true; // Set the left pointer of the current ThreadedNode to the previous ThreadedNode currThreadedNode.left = prevNode; currThreadedNode.leftThread = true; } // Update the previous ThreadedNode to the current ThreadedNode prevNode = currThreadedNode; // Traverse the right subtree threadInOrder(root.right); } ``` 5. Call the `threadInOrder` function in the constructor, passing the root of the binary tree as an argument. ```java public ThreadedNode(BinaryNode root) { // ... // Initialize the dummy head node // ... // Start the threading process threadInOrder(root); } ``` Now, you should be able to construct a threaded binary tree using the `ThreadedNode(BinaryNode root)` constructor. [/QUOTE]
Insert quotes…
Verification
Post reply
Top