我必须将单链表、双链表和循环链表转换为二叉树。
我已经制作了一个单独链接的列表，我很难理解如何将其转换为树。
我的单链表节点如下：
public class Node {
Node next;
Object data;
public Node(Object _data)
{
next = null;
data = _data;
}
public Node(Object _data, Node _next)
{
next = _next;
data = _data;
}
public Object getData()
{
return data;
}
public void setData(Object _data)
{
data = _data;
}
public Node getNext()
{
return next;
}
public void setNext(Node _next)
{
next = _next;
}
}
这是我的单链表类：
import java.util.Collection;
import java.util.Collections;
public class LinkedList {
private Node head;
private int listCount;
public LinkedList()
{
head = new Node(null);
listCount = 0;
}
public void add(Object data)
{
Node temp = new Node(data);
Node current = head;
head.setData(temp.getData());
while(current.getNext() != null)
{
current = current.getNext();
}
current.setNext(temp);
listCount++;
}
public void add(Object data, int index)
{
Node temp = new Node(data);
Node current = head;
head.setData(temp.getData());
for (int i = 1; i < index && current.getNext() != null; i++)
{
current = current.getNext();
}
temp.setNext(current.getNext());
current.setNext(temp);
listCount++;
}
public Object get(int index)
{
if(index <= 0)
{
return null;
}
Node current = head.getNext();
for(int i = 1; i < index; i++)
{
if(current.getNext() == null)
{
return null;
}
current = current.getNext();
}
return current.getData();
}
public int size()
{
return listCount;
}
public boolean remove(int index)
{
if(index < 1 || index > size())
{
return false;
}
Node current = head;
for(int i = 1; i < index; i++)
{
if(current.getNext() == null)
{
return false;
}
current = current.getNext();
}
current.setNext(current.getNext().getNext());
listCount--;
return true;
}
public boolean contains(Object data)
{
Node temp = new Node(data);
Node current = head;
for(int i = 0; i < size(); i++)
{
if(temp.getData().equals(current.getData()))
{
return true;
}
else
{
current = current.getNext();
}
}
return false;
}
public Node inserAfter(Object data, Node n)
{
Node temp = new Node(data);
Node current = n.getNext();
temp.setNext(current);
n.setNext(temp);
return temp;
}
public void rotateLeft()
{
Node temp = head;
if (head != null) { //otherwise it is empty list
if (head.getNext() != null) { //otherwise it is single item list
head = head.getNext();
}
}
Node tail;
if (head.getNext() != null) {
tail = head.getNext();
} else {
tail = head;
}
while(tail.getNext() != null)
{
if (tail.getNext() != null) {
tail = tail.getNext();
}
}
tail.setNext(temp);
temp.setNext(null);
}
public void rotateRight()
{
Node temp = null;
Node current = head;
while(current.getNext() != null)
{
temp = current;
current = current.getNext();
}
current.setNext(head);
head = current;
temp.setNext(null);
}
public void reverse()
{
Node reversedPart = null;
Node current = head;
while(current != null)
{
Node next = current.next;
current.next = reversedPart;
reversedPart = current;
current = next;
}
head = reversedPart;
}
public Node copyList(Node source)
{
Node copyHead = null;
Node copyTail = null;
Node temp = new Node(source);
Node current = head.getNext();
for(int i = 0; i < size(); i++)
{
Node newNode = new Node(temp.getData());
if(copyHead == null)
{
copyHead = newNode;
copyTail = copyHead;
}
else
{
copyTail.setNext(newNode);
copyTail = copyTail.getNext();
}
}
return copyHead;
}
public Object setDataIndexOf(Object data, int index)
{
Node node = nodeAt(index);
if(node == null)
{
return null;
}
else
{
Object old = node.getData();
node.setData(data);
return old;
}
}
public Object dataAt(int index)
{
Node current = head.getNext();
if(index < 1 || index > size())
{
return null;
}
for(int i = 0; i < index; i ++)
{
if(i != index - 1)
{
current = current.getNext();
}
}
return current.getData();
}
public Node nodeAt(int index)
{
Node current = head.getNext();
if(index < 1 || index > size())
{
return null;
}
for(int i = 0; i < index; i++)
{
if(i != index - 1)
{
current = current.getNext();
}
}
return current;
}
public int indexOf(Object data)
{
Node temp = new Node(data);
Node current = head.getNext();
for(int i = 0; i < size(); i++)
{
if(current.getData().equals(temp.getData()))
{
return i;
}
current = current.getNext();
}
return -1;
}
public Object min()
{
Integer min = (Integer)head.getData();
Node current = head;
while(current.getNext() != null)
{
if((Integer)current.getData() < min)
{
min = (Integer)current.getData();
}
current = current.getNext();
}
return min;
}
public Object max()
{
Integer max = (Integer)head.getData();
Node current = head;
while(current.getNext() != null)
{
if((Integer)current.getData() > max)
{
max = (Integer)current.getData();
}
current = current.getNext();
}
return max;
}
public void removeSecondAppear(Object data)
{
Node temp = new Node(data);
Node current = head;
Node previous = null;
boolean found = false;
while(current != null)
{
if(current.getData().equals(temp.getData()) && current.getData() != null)
{
if(found == true)
{
previous.setNext(current.getNext());
break;
}
else if(found == false)
{
found = true;
}
}
else{
found = false;
}
previous = current;
current = current.getNext();
}
}
public String toString()
{
Node current = head.getNext();
String output = "";
while(current != null)
{
output += "[" + current.getData().toString() + "]";
current = current.getNext();
}
return output;
}
}
创建了单独链接的列表后，我必须基于该列表创建一个新的树。我完全迷路了，不知道该怎么开始。以前从未做过类似的事情。任何帮助都将不胜感激。
首先需要实现一个二进制搜索树。我刚用了一个谷歌，有很多Java实现的例子可以学习。您的二进制搜索树应该有一个接受一个参数的insert方法，理想情况下是一个无界类型，但考虑到您的列表实现，现在只使用Object：
public void insert(Object element);
一旦构建了BST，就遍历列表并将元素添加到树中，如下所示：
LinkedList list = new LinkedList();
list.add("foo");
list.add("bar");
list.add("baz");
list.add("etc");
BinarySearchTree bst = new BinarySearchTree();
for(Object o:list) {
bst.add(o);
}