189 8069 5689
从键盘接受输入(先序)，以二叉链表作为存储结构，建立二叉树(以先序来建立)
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：空间域名、网络空间、营销软件、网站建设、弥渡网站维护、网站推广。
结果不是唯一
public class NodeE {
int key; // data used as key value
E data; // other data
NodeE leftChild; // this node's left child
NodeE rightChild; // this node's right child
public Node(int key, E o) {
this.key = key;
this.data = o;
}
public void displayNode() {
System.out.printf("%d, %s\n", key, data.toString());
}
}
===============================================================
package net.acoder.adt.tree;
public class TreeE {
private NodeE root;
public Tree(NodeE root) {
if (root == null) {
throw new NullPointerException("root can't be null");
}
this.root = root;
}
public Tree(int key, E o) {
this(new NodeE(key, o));
}
public NodeE getRoot() {
return root;
}
/**
* find a node by its key
*
* @param key
* @return
*/
public NodeE find(int key) {
NodeE current = root;
while (current.key != key) {
if (key current.key) {
current = root.leftChild;
} else {
current = root.rightChild;
}
if (current == null) {
return null;
}
}
return current;
}
/**
* insert a node to this tree
*
* @param key
* @param o
*/
public void insert(int key, E o) {
NodeE aNode = new NodeE(key, o);
if (root == null) {
this.root = aNode;
return;
}
NodeE current = root;
NodeE parent = root;
while (true) {
parent = current;
if (key parent.key) {
current = parent.leftChild;
if (current == null) {
parent.leftChild = aNode;
return;
}
} else {
current = parent.rightChild;
if (current == null) {
parent.rightChild = aNode;
return;
}
}
}
}
public boolean delete(int key) {
NodeE current = root;
NodeE parent = root;
boolean isLeftChild = true;
// search for node
while (current.key != key) {
parent = current;
if (key current.key) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}
// if no children, simply delete it
if (current.leftChild == null current.rightChild == null) {
if (current == parent) {
root = null;
} else if (isLeftChild == true) {
parent.leftChild = null;
} else if (isLeftChild == false) {
parent.rightChild = null;
}
return true;
}
// if no left children, replace with right subtree
if (current.leftChild == null) {
if (current == root) {
root = current.rightChild;
} else if (isLeftChild) {
parent.leftChild = current.rightChild;
} else if (!isLeftChild) {
parent.leftChild = current.rightChild;
}
return true;
}
// if no right children, replace with left subtree
if (current.rightChild == null) {
if (current == root) {
root = current.leftChild;
} else if (isLeftChild) {
parent.leftChild = current.leftChild;
} else if (!isLeftChild) {
parent.leftChild = current.leftChild;
}
return true;
}
// get successor of node to delete
NodeE successor = getSuccessor(current);
if (current == root) {
current = successor;
} else if (isLeftChild) {
parent.leftChild = successor;
} else {
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
return true;
}
private NodeE getSuccessor(NodeE delNode) {
NodeE successorParent = delNode;
NodeE successor = delNode;
NodeE current = delNode.rightChild;
while (current != null) {
successorParent = successor;
successor = current;
current = current.leftChild;
}
if (successor != delNode.rightChild) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
public void inOrder(NodeE aNode) {
if (aNode != null) {
inOrder(aNode.leftChild);
aNode.displayNode();
inOrder(aNode.rightChild);
}
}
public void preOrder(NodeE aNode) {
if (aNode != null) {
aNode.displayNode();
inOrder(aNode.leftChild);
inOrder(aNode.rightChild);
}
}
public void backOrder(NodeE aNode) {
if (aNode != null) {
inOrder(aNode.leftChild);
inOrder(aNode.rightChild);
aNode.displayNode();
}
}
public NodeE minimum() {
NodeE current = this.root;
NodeE result = null;
while (current != null) {
result = current;
current = current.leftChild;
}
return result;
}
public NodeE maximum() {
NodeE current = this.root;
NodeE result = null;
while (current != null) {
result = current;
current = current.rightChild;
}
return result;
}
}
以前的代码, 记得没写完, 好像就是BST
你好，很高兴回答你的问题。
目前已经有了二叉树以及二叉树节点的类。
需要一个main方法，在其中创建节点（通过节点类的构造方法），构建树（通过树的构造方法以及insert方法）。可以执行查询的方法以及展示的方法。
如果有帮助到你，请点击采纳。
做了很多年的程序员，觉得什么树的设计并不是非常实用。二叉树有顺序存储，当一个insert大量同时顺序自增插入的时候，树就会失去平衡。树的一方为了不让塌陷，会增大树的高度。性能会非常不好。以上是题外话。分析需求在写代码。
import java.util.List;
import java.util.LinkedList;
public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static ListNode nodeList = null;
private static class Node {
Node leftChild;
Node rightChild;
int data;
Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}
// 创建二叉树
public void createBintree() {
nodeList = new LinkedListNode();
// 将数组的值转换为node
for (int nodeIndex = 0; nodeIndex array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}
// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树
for (int parentIndex = 0; parentIndex array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
}
// 最后一个父节点
int lastParentIndex = array.length / 2 - 1;
// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);
// 如果为奇数，建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
}
}
// 前序遍历
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
// 中序遍历
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}
inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}
// 后序遍历
public static void postOrderTraverse(Node node) {
if (node == null) {
return;
}
postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}
public static void main(String[] args) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
Node root = nodeList.get(0);
System.out.println("前序遍历：");
preOrderTraverse(root);
System.out.println();
System.out.println("中序遍历：");
inOrderTraverse(root);
System.out.println();
System.out.println("后序遍历：");
postOrderTraverse(root);
}
}
public class BinaryNode {
Object element;
BinaryNode left;
BinaryNode right;
}
import java.util.*;
public class Queue {
protected LinkedList list;
// Postcondition: this Queue object has been initialized.
public Queue() {
list = new LinkedList();
} // default constructor
// Postcondition: the number of elements in this Queue object has been
// returned.
public int size() {
return list.size();
} // method size
// Postcondition: true has been returned if this Queue object has no
// elements. Otherwise, false has been returned.
public boolean isEmpty() {
return list.isEmpty();
} // method isEmpty
// Postconditon: A copy of element has been inserted at the back of this
// Queue object. The averageTime (n) is constant and
// worstTime (n) is O (n).
public void enqueue(Object element) {
list.addLast(element);
} // method enqueue
// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: The element that was at the front of this Queue object -
// just before this method was called -- has been removed
// from this Queue object and returned.
public Object dequeue() {
return list.removeFirst();
} // method dequeue
// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: the element at index 0 in this Queue object has been
// returned.
public Object front() {
return list.getFirst();
} // method front
} // Queue class
import java.io.IOException;
public class BinaryTree {
BinaryNode root;
public BinaryTree() {
super();
// TODO 自动生成构造函数存根
root=this.createPre();
}
public BinaryNode createPre()
//按照先序遍历的输入方法，建立二叉树
{
BinaryNode t=null;
char ch;
try {
ch = (char)System.in.read();
if(ch==' ')
t=null;
else
{
t=new BinaryNode();
t.element=(Object)ch;
t.left=createPre();
t.right=createPre();
}
} catch (IOException e) {
// TODO 自动生成 catch 块
e.printStackTrace();
}
return t;
}
public void inOrder()
{
this.inOrder(root);
}
public void inOrder(BinaryNode t)
//中序遍历二叉树
{
if(t!=null)
{
inOrder(t.left);
System.out.print(t.element);
inOrder(t.right);
}
}
public void postOrder()
{
this.postOrder(root);
}
public void postOrder(BinaryNode t)
//后序遍历二叉树
{
if(t!=null)
{
postOrder(t.left);
System.out.print(t.element);
postOrder(t.right);
}
}
public void preOrder()
{
this.preOrder(root);
}
public void preOrder(BinaryNode t)
//前序遍历二叉树
{
if(t!=null)
{
System.out.print(t.element);
preOrder(t.left);
preOrder(t.right);
}
}
public void breadthFirst()
{
Queue treeQueue=new Queue();
BinaryNode p;
if(root!=null)
treeQueue.enqueue(root);
while(!treeQueue.isEmpty())
{
System.out.print(((BinaryNode)(treeQueue.front())).element);
p=(BinaryNode)treeQueue.dequeue();
if(p.left!=null)
treeQueue.enqueue(p.left);
if(p.right!=null)
treeQueue.enqueue(p.right);
}
}
}
public class BinaryTreeTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成方法存根
BinaryTree tree = new BinaryTree();
System.out.println("先序遍历：");
tree.preOrder();
System.out.println();
System.out.println("中序遍历：");
tree.inOrder();
System.out.println();
System.out.println("后序遍历：");
tree.postOrder();
System.out.println();
System.out.println("层次遍历：");
tree.breadthFirst();
System.out.println();
}
}
试试这些代码:
private BinaryNodeT remove(T x,BinaryNodeT p,BinaryNodeT parent){
if(p==null){
return null;
}
if(x.compareTo(p.data)0){
return remove(x,p.left,p);
}
if(x.compareTo(p.data)0){
return remove(x,p.right,p);
}
if(p.left!=nullp.right!=null){
BinaryNodeT insucc=p.right;
while(insucc.left!=null){
insucc=insucc.left;
}
p.data=insucc.data;
return remove(p.data,p.right,p);
}
if(parent==null){
if(p.left!=null){
root=p.left;
}
else root=p.right;
return p;
}
if(p==parent.left){
if(p.left!=null){
parent.left=p.left;
}
else{
parent.left=p.right;
}
}
else{
if(p.left!=null){
parent.right=p.left;
}
else{
parent.right=p.right;
}
}
return p;
}