Convertir un árbol binario en un árbol binario con subprocesos | Conjunto 2 (eficiente)

La idea de Threaded Binary Tree es hacer que el recorrido en orden sea más rápido y hacerlo sin pila y sin recursividad. En un árbol binario de subprocesos simple, los punteros derechos NULL se utilizan para almacenar el sucesor en orden. Dondequiera que un puntero a la derecha sea NULL, se usa para almacenar el sucesor en orden.

C

struct Node
{
    int key;
    Node *left, *right;
  
    // Used to indicate whether the right pointer is a normal right 
    // pointer or a pointer to inorder successor.
    bool isThreaded; 
};

Java

static class Node
{
    int key;
    Node left, right;
  
    // Used to indicate whether the right pointer is a normal right 
    // pointer or a pointer to inorder successor.
    boolean isThreaded; 
};
  
// This code is contributed by umadevi9616

Python3

class Node: 
    def __init__(self, data):
        self.key = data; 
        self.left = none;
        self.right = none;
        self.isThreaded = false;
    # Used to indicate whether the right pointer is a normal right
    # pointer or a pointer to inorder successor.
  
# This code is contributed by umadevi9616 

C#

public class Node {
    public int key;
    public Node left, right;
  
    // Used to indicate whether the right pointer is a normal right
    // pointer or a pointer to inorder successor.
    public bool isThreaded;
};
  
  
// This code is contributed by umadevi9616 

Javascript

    
/* structure of a node in threaded binary tree */
 class Node {
        constructor(val) {
            this.data = val;
            this.left = null;
            this.right = null;
      
    
    // Used to indicate whether the right pointer 
    // is a normal right pointer or a pointer 
    // to inorder successor. 
    this.isThreaded = false;
    }
    }
      
    // This code is contributed by famously.

C++

/* C++ program to convert a Binary Tree to
    Threaded Tree */
#include <bits/stdc++.h>
using namespace std;
  
/* Structure of a node in threaded binary tree */
struct Node
{
    int key;
    Node *left, *right;
  
    // Used to indicate whether the right pointer
    // is a normal right pointer or a pointer
    // to inorder successor.
    bool isThreaded;
};
  
// Converts tree with given root to threaded
// binary tree.
// This function returns rightmost child of
// root.
Node *createThreaded(Node *root)
{
    // Base cases : Tree is empty or has single
    //              node
    if (root == NULL)
        return NULL;
    if (root->left == NULL &&
        root->right == NULL)
        return root;
  
    // Find predecessor if it exists
    if (root->left != NULL)
    {
        // Find predecessor of root (Rightmost
        // child in left subtree)
        Node* l = createThreaded(root->left);
  
        // Link a thread from predecessor to
        // root.
        l->right = root;
        l->isThreaded = true;
    }
  
    // If current node is rightmost child
    if (root->right == NULL)
        return root;
  
    // Recur for right subtree.
    return createThreaded(root->right);
}
  
// A utility function to find leftmost node
// in a binary tree rooted with 'root'.
// This function is used in inOrder()
Node *leftMost(Node *root)
{
    while (root != NULL && root->left != NULL)
        root = root->left;
    return root;
}
  
// Function to do inorder traversal of a threadded
// binary tree
void inOrder(Node *root)
{
    if (root == NULL) return;
  
    // Find the leftmost node in Binary Tree
    Node *cur = leftMost(root);
  
    while (cur != NULL)
    {
        cout << cur->key << " ";
  
        // If this Node is a thread Node, then go to
        // inorder successor
        if (cur->isThreaded)
            cur = cur->right;
  
        else // Else go to the leftmost child in right subtree
            cur = leftMost(cur->right);
    }
}
  
// A utility function to create a new node
Node *newNode(int key)
{
    Node *temp = new Node;
    temp->left = temp->right = NULL;
    temp->key = key;
    return temp;
}
  
// Driver program to test above functions
int main()
{
    /*       1
            / \
           2   3
          / \ / \
         4  5 6  7   */
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
  
    createThreaded(root);
  
    cout << "Inorder traversal of created "
            "threaded tree is\n";
    inOrder(root);
    return 0;
}

Java

/* Java program to convert a Binary Tree to 
    Threaded Tree */
import java.util.*;
class solution
{
   
    
/* structure of a node in threaded binary tree */
static class Node 
{ 
    int key; 
    Node left, right; 
    
    // Used to indicate whether the right pointer 
    // is a normal right pointer or a pointer 
    // to inorder successor. 
    boolean isThreaded; 
}; 
    
// Converts tree with given root to threaded 
// binary tree. 
// This function returns rightmost child of 
// root. 
static Node createThreaded(Node root) 
{ 
    // Base cases : Tree is empty or has single 
    //              node 
    if (root == null) 
        return null; 
    if (root.left == null && 
        root.right == null) 
        return root; 
    
    // Find predecessor if it exists 
    if (root.left != null) 
    { 
        // Find predecessor of root (Rightmost 
        // child in left subtree) 
        Node l = createThreaded(root.left); 
    
        // Link a thread from predecessor to 
        // root. 
        l.right = root; 
        l.isThreaded = true; 
    } 
    
    // If current node is rightmost child 
    if (root.right == null) 
        return root; 
    
    // Recur for right subtree. 
    return createThreaded(root.right); 
} 
    
// A utility function to find leftmost node 
// in a binary tree rooted with 'root'. 
// This function is used in inOrder() 
static Node leftMost(Node root) 
{ 
    while (root != null && root.left != null) 
        root = root.left; 
    return root; 
} 
    
// Function to do inorder traversal of a threadded 
// binary tree 
static void inOrder(Node root) 
{ 
    if (root == null) return; 
    
    // Find the leftmost node in Binary Tree 
    Node cur = leftMost(root); 
    
    while (cur != null) 
    { 
        System.out.print(cur.key + " "); 
    
        // If this Node is a thread Node, then go to 
        // inorder successor 
        if (cur.isThreaded) 
            cur = cur.right; 
    
        else // Else go to the leftmost child in right subtree 
            cur = leftMost(cur.right); 
    } 
} 
    
// A utility function to create a new node 
static Node newNode(int key) 
{ 
    Node temp = new Node(); 
    temp.left = temp.right = null; 
    temp.key = key; 
    return temp; 
} 
    
// Driver program to test above functions 
public static void main(String args[])
{ 
   /*       1 
            / \ 
           2   3 
          / \ / \ 
         4  5 6  7   */
    Node root = newNode(1); 
    root.left = newNode(2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
    root.right.left = newNode(6); 
    root.right.right = newNode(7); 
    
    createThreaded(root); 
    
    System.out.println("Inorder traversal of created "+"threaded tree is\n"); 
    inOrder(root);  
} 
}
//contributed by Arnab Kundu

Python3

# Python3 program to convert a Binary Tree to 
# Threaded Tree 
  
# A utility function to create a new node 
class newNode:
    def __init__(self, key):
        self.left = self.right = None
        self.key = key 
        self.isThreaded = None
          
# Converts tree with given root to threaded 
# binary tree. 
# This function returns rightmost child of 
# root. 
def createThreaded(root):
      
    # Base cases : Tree is empty or has  
    #               single node 
    if root == None: 
        return None
    if root.left == None and root.right == None: 
        return root 
  
    # Find predecessor if it exists 
    if root.left != None:
          
        # Find predecessor of root (Rightmost 
        # child in left subtree) 
        l = createThreaded(root.left) 
  
        # Link a thread from predecessor 
        # to root. 
        l.right = root 
        l.isThreaded = True
  
    # If current node is rightmost child 
    if root.right == None: 
        return root 
  
    # Recur for right subtree. 
    return createThreaded(root.right)
  
# A utility function to find leftmost node 
# in a binary tree rooted with 'root'. 
# This function is used in inOrder() 
def leftMost(root):
    while root != None and root.left != None: 
        root = root.left 
    return root
  
# Function to do inorder traversal of a 
# threaded binary tree 
def inOrder(root):
    if root == None:
        return
  
    # Find the leftmost node in Binary Tree 
    cur = leftMost(root) 
  
    while cur != None:
        print(cur.key, end = " ") 
  
        # If this Node is a thread Node, then
        # go to inorder successor 
        if cur.isThreaded: 
            cur = cur.right 
  
        else: # Else go to the leftmost child
              # in right subtree 
            cur = leftMost(cur.right)
  
# Driver Code
if __name__ == '__main__':
      
    #         1 
    #     / \ 
    #     2 3 
    #     / \ / \ 
    #     4 5 6 7 
    root = newNode(1) 
    root.left = newNode(2) 
    root.right = newNode(3) 
    root.left.left = newNode(4) 
    root.left.right = newNode(5) 
    root.right.left = newNode(6) 
    root.right.right = newNode(7) 
  
    createThreaded(root) 
  
    print("Inorder traversal of created",
                      "threaded tree is") 
    inOrder(root)
  
# This code is contributed by PranchalK

C#

using System;
  
/* C# program to convert a Binary Tree to  
    Threaded Tree */
public class solution
{
  
  
/* structure of a node in threaded binary tree */
public class Node
{
    public int key;
    public Node left, right;
  
    // Used to indicate whether the right pointer  
    // is a normal right pointer or a pointer  
    // to inorder successor.  
    public bool isThreaded;
}
  
// Converts tree with given root to threaded  
// binary tree.  
// This function returns rightmost child of  
// root.  
public static Node createThreaded(Node root)
{
    // Base cases : Tree is empty or has single  
    //              node  
    if (root == null)
    {
        return null;
    }
    if (root.left == null && root.right == null)
    {
        return root;
    }
  
    // Find predecessor if it exists  
    if (root.left != null)
    {
        // Find predecessor of root (Rightmost  
        // child in left subtree)  
        Node l = createThreaded(root.left);
  
        // Link a thread from predecessor to  
        // root.  
        l.right = root;
        l.isThreaded = true;
    }
  
    // If current node is rightmost child  
    if (root.right == null)
    {
        return root;
    }
  
    // Recur for right subtree.  
    return createThreaded(root.right);
}
  
// A utility function to find leftmost node  
// in a binary tree rooted with 'root'.  
// This function is used in inOrder()  
public static Node leftMost(Node root)
{
    while (root != null && root.left != null)
    {
        root = root.left;
    }
    return root;
}
  
// Function to do inorder traversal of a threadded  
// binary tree  
public static void inOrder(Node root)
{
    if (root == null)
    {
        return;
    }
  
    // Find the leftmost node in Binary Tree  
    Node cur = leftMost(root);
  
    while (cur != null)
    {
        Console.Write(cur.key + " ");
  
        // If this Node is a thread Node, then go to  
        // inorder successor  
        if (cur.isThreaded)
        {
            cur = cur.right;
        }
  
        else // Else go to the leftmost child in right subtree
        {
            cur = leftMost(cur.right);
        }
    }
}
  
// A utility function to create a new node  
public static Node newNode(int key)
{
    Node temp = new Node();
    temp.left = temp.right = null;
    temp.key = key;
    return temp;
}
  
// Driver program to test above functions  
public static void Main(string[] args)
{
   /*       1  
            / \  
           2   3  
          / \ / \  
         4  5 6  7   */
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right.left = newNode(6);
    root.right.right = newNode(7);
  
    createThreaded(root);
  
    Console.WriteLine("Inorder traversal of created " + "threaded tree is\n");
    inOrder(root);
}
}
  
  // This code is contributed by Shrikant13

Javascript

<script>
/* javascript program to convert a Binary Tree to 
    Threaded Tree */
    
/* structure of a node in threaded binary tree */
 class Node {
        constructor(val) {
            this.data = val;
            this.left = null;
            this.right = null;
      
    
    // Used to indicate whether the right pointer 
    // is a normal right pointer or a pointer 
    // to inorder successor. 
    this.isThreaded = false;
    }
    }
  
    
// Converts tree with given root to threaded 
// binary tree. 
// This function returns rightmost child of 
// root. 
function createThreaded(root) 
{ 
    // Base cases : Tree is empty or has single 
    //              node 
    if (root == null) 
        return null; 
    if (root.left == null && 
        root.right == null) 
        return root; 
    
    // Find predecessor if it exists 
    if (root.left != null) 
    { 
        // Find predecessor of root (Rightmost 
        // child in left subtree) 
        var l = createThreaded(root.left); 
    
        // Link a thread from predecessor to 
        // root. 
        l.right = root; 
        l.isThreaded = true; 
    } 
    
    // If current node is rightmost child 
    if (root.right == null) 
        return root; 
    
    // Recur for right subtree. 
    return createThreaded(root.right); 
} 
    
// A utility function to find leftmost node 
// in a binary tree rooted with 'root'. 
// This function is used in inOrder() 
function leftMost(root) 
{ 
    while (root != null && root.left != null) 
        root = root.left; 
    return root; 
} 
    
// Function to do inorder traversal of a threadded 
// binary tree 
function inOrder(root) 
{ 
    if (root == null) return; 
    
    // Find the leftmost node in Binary Tree 
    var cur = leftMost(root); 
    
    while (cur != null) 
    { 
        document.write(cur.key + " "); 
    
        // If this Node is a thread Node, then go to 
        // inorder successor 
        if (cur.isThreaded) 
            cur = cur.right; 
    
        else // Else go to the leftmost child in right subtree 
            cur = leftMost(cur.right); 
    } 
} 
    
// A utility function to create a new node 
function newNode(key) 
{ 
    var temp = new Node(); 
    temp.left = temp.right = null; 
    temp.key = key; 
    return temp; 
} 
    
// Driver program to test above functions 
   
   /*       1 
            / \ 
           2   3 
          / \ / \ 
         4  5 6  7   */
    var root = newNode(1); 
    root.left = newNode(2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
    root.right.left = newNode(6); 
    root.right.right = newNode(7); 
    
    createThreaded(root); 
    
    document.write("Inorder traversal of created "+"threaded tree is<br/>"); 
    inOrder(root);  
  
// This code contributed by aashish1995
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *