Двоичное дерево в java, используя связанный список

Question

Мне интересно, могу ли я получить некоторую помощь в создании двоичного дерева с помощью связанного списка. В каждом узле имеется меньший связанный список для хранения информации для этого конкретного узла. Я ищу подсказку о том, как заставить каждый узел удерживать другой связанный список. Это для домашней работы.

Answer 1

Если вы хотите дерево узлов данных в виде связанного списка, а не целое, то вы можете использовать этот

public class Tree { 
    static class LinkedList{ 
     int data; 
     LinkedList next; 
     public LinkedList(int data, LinkedList next){ 
      this.data = data; 
      this.next = next; 
     } 
    } 
    LinkedList node; 
    Tree left; 
    Tree right; 
    public Tree(LinkedList node, Tree left, Tree right){ 
     this.node = node; 
     this.left = left; 
     this.right = right; 

    } 
    public static void main(String[] args) { 
     LinkedList l3 = new LinkedList(3,null); 
     Tree node3 = new Tree(l3,null, null);//left child 
     LinkedList l4 = new LinkedList(4,null); 
     Tree node4 = new Tree(l4,null, null);//right child 
     LinkedList l1 = new LinkedList(1,null); 
     LinkedList l2 = new LinkedList(2, l1); 
     Tree node1 = new Tree(l2,node3, node4);//node1 be the root of tree 
    } 
} 

Здесь каждый узел дерева будет держать связанный список.

Answer 2

Существует различие между LinkedList и деревом двоичного поиска Difference between a LinkedList and a Binary Search Tree. Принцип для BST называется «композиция». например состав ≠ наследование Difference between Inheritance and Composition. Двоичное дерево поиска - это просто упорядоченное двоичное дерево для хранения элементов композиции. Поскольку он двоичный, вы можете идти либо влево, либо вправо в каждом узле. Поэтому каждый объект узла должен иметь leftNode и rightNode в качестве композиции. Это должно заставить вас начать делать домашнее задание самостоятельно.

Answer 3

Вы можете видеть, отвечает ли это на ваш вопрос? Я получил это от другого человека от geeksforgeeks.org

/* 
The structure of Link list node is as follows 
struct node 
{ 
    int data; 
    struct node* next; 
}; 

The structure of TreeNode is as follows 
struct TreeNode 
{ 
    int data; 
    TreeNode *left; 
    TreeNode *right; 
}; 
*/ 

TreeNode* newTreeNode(int data) 
{ 
    TreeNode *temp = new TreeNode; 
    temp->data = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
/*You are required to complete this method*/ 
void convert(node *head,TreeNode * &root) 
{ 
queue<TreeNode *> q; 
    root=newTreeNode(head->data); 
    head=head->next; 
    q.push(root); 
    while(!q.empty()){ 
     TreeNode *tmp=q.front(); 
     q.pop(); 
     if(head){ 
      tmp->left=newTreeNode(head->data); 
      q.push(tmp->left); 
      head=head->next; 
     } 
     if(head){ 
      tmp->right=newTreeNode(head->data); 
      q.push(tmp->right); 
      head=head->next; 
     } 
     if(!head) 
      break; 
    } 

}