面试题,用Java实现二叉树

参考代码：public class BinaryTreeTest
{
public static void main(String args[])
{
BinaryTreeTest b=new BinaryTreeTest();
int data[]={12,11,34,45,67,89,56,43,22,98};
BinaryTree root =new BinaryTree(data[0]); System.out.print("二叉树的中的数据：　　");
for(int i=1;i{
root.insertTree(root,data[i]);
System.out.print(data[i-1]+";");
} System.out.println(data[data.length-1]); int key=Integer.parseInt(args[0]); if(b.searchkey(root,key))
{
System.out.println("找到了:"+key);
}
else
{
System.out.println("没有找到："+key);
}
} public boolean searchkey(BinaryTree root, int key)
{
boolean bl=false;
if(root==null)
{
bl=false;
return bl;
}
else if(root.data==key)
{
bl=true;
return bl;
}
else if(key>=root.data)
{
return searchkey(root.rightpoiter,key);
}
return searchkey(root.leftpoiter,key);
}
} class BinaryTree
{
int data;
BinaryTree leftpoiter;
BinaryTree rightpoiter; BinaryTree(int data)
{
this.data=data;
leftpoiter=null;
rightpoiter=null;
} public void insertTree(BinaryTree root, int data)
{
if(data>=root.data)
{
if(root.rightpoiter==null)
{
root.rightpoiter=new BinaryTree(data);
}
else
{
insertTree(root.rightpoiter,data);
}
}
else
{
if(root.leftpoiter==null)
{
root.leftpoiter=new BinaryTree(data);
}
else
{
insertTree(root.leftpoiter,data);
}
}
}
}
//end

1.定义员工类
2.定义结点类，属性为员工，以及左，右孩子结点
3.定义二叉树类，属性有根结点，方法为增加结点，查找结点，删除结点，遍历树等
//员工类
public class Employee {
   int id;
   String name;
   char gender;
   //getter,setter
}
//结点类
public class Node {
   Employyee emp;
   Node leftChild;
   Node rightChild;
   public void display() {
      //打印出自己与孩子结点的姓名或者其它
       System.out.println(name);
      if (leftChild != null) {
         System.out.println(leftChild.emp.name);
      }
      if (leftChild != null) {
         System.out.println(rightchild.emp.name);
      }
   }
   ....
}
//二叉树类，这是我以前写的二叉树，存储的数据类型为int,你把要它换成相应的员工类即可，查找条件，或是删除条件都要做相关修改，你自己改吧。
public class BTTree {
    Node root;
    int size;
    public Node find(int key) {
Node current = root;

if (root == null) //empty tree
return null;
else {
while (current.getKey()!=key) {
if (key < current.getKey()) {           //go left
current = current.getLeftChild();
} else {
current = current.getRightChild();  //go right
} if (current == null) {
return null;
}
}
}

return current;
}

/**
* ��ĳ��ֵ
* @param key
* @param data
*/
public void insert(int key, int data) {
Node newNode = new Node(key, data);

if (root == null) {  //��
root = newNode;
size++;
} else {             //not empty tree
Node current = root;
Node parent;     //��Ϊ��ĸ��

while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
size++;
return;
}
} //end if go left
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
size++;
return;
}
} //end if go right
} // end while (true)
}
} //end insert

/**
* ��,�÷��Ϊ��
* @param Node localRoot
*/
private void inOrder(Node localRoot) {
if (localRoot != null) {
inOrder(localRoot.getLeftChild());
localRoot.display();
inOrder(localRoot.getRightChild());
} else
return;
}

/**
* 中序遍历
*/
public void inOrder() {
inOrder(root);
}

public int getSize() {
return size;
} //删除某个结点
public boolean delete(int key) {
if (root == null) // empty tree
return false;
Node current = root;
Node parent = root;
boolean isLeftChild = false;
while (current.getKey() != key) {
parent = current;
if (key < current.getKey()) {
isLeftChild = true;
current = current.getLeftChild();
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null) { //not found
return false;
}
}
//found it
//删除的结点是叶子结点
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
root = null;
if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
} else if (current.getRightChild() == null) {//删除的结点只有左孩子结点
if (current == root) {
root = current.getLeftChild();
}
if (isLeftChild) {
parent.setLeftChild(current.getLeftChild());
} else {
parent.setRightChild(current.getRightChild());
}
} else if (current.getLeftChild() == null) {//删除的结点只有右孩子
if (current == root)
root = current.getRightChild();
if (isLeftChild) {
parent.setLeftChild(current.getRightChild());
} else {
parent.setRightChild(current.getRightChild());
}
} else {//删除的结点有左右孩子
Node successor = getSuccessor(current);
if (current == root) {
root = successor;
}
if (isLeftChild) {
parent.setLeftChild(successor);
} else {
parent.setRightChild(successor);
}
successor.setLeftChild(current.getLeftChild());
}

return true;
}

//从右子树中查找替代被删除结点位置的结点
private Node getSuccessor(Node delNode) {
Node successor = delNode;
Node parentSuccessor = delNode;
Node current = delNode.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}

if (successor != delNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(delNode.getRightChild());
}

return successor;
    }

//test Tree.java
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(23, 23);
tree.insert(20, 20);
tree.insert(24, 24);
tree.insert(15, 15);
tree.insert(30, 30);
System.out.println(tree.getSize());
tree.inOrder();
Node find = tree.find(14);
if (find != null)
System.out.println(find);
else
System.out.println("not found.");
boolean flag = tree.delete(20);
if (flag) {
System.out.println("delete success");
tree.inOrder();
}
}

树节点定义:class TreeNode {
    public TreeNode left;    public TreeNode right;    public int value;    public TreeNode(TreeNode left, TreeNode right, int value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }
}二叉树及其操作:public class BinaryTree {    public static int getTreeHeight(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null && root.right == null)
            return 1;
        return 1 + Math
                .max(getTreeHeight(root.left), getTreeHeight(root.right));
    }    public static void recursePreOrder(TreeNode root) {
        if (root == null)
            return;
        System.out.println(root.value);
        if (root.left != null)
            recursePreOrder(root.left);
        if (root.right != null)
            recursePreOrder(root.right);
    }    public static void stackPreOrder(TreeNode root) {
        Stack stack = new Stack();
        if (root == null)
            return;
        stack.push(root);
        System.out.println(root.value);
        TreeNode temp = root.left;
        while (temp != null) {
            stack.push(temp);
            System.out.println(temp.value);
            temp = temp.left;
        }
        temp = (TreeNode) stack.pop();
        while (temp != null) {
            temp = temp.right;
            while (temp != null) {
                stack.push(temp);
                System.out.println(temp.value);
                temp = temp.left;
            }
            if (stack.empty())
                break;
            temp = (TreeNode) stack.pop();
        }
    }    public static void recurseInOrder(TreeNode root) {
        if (root == null)
            return;
        if (root.left != null)
            recurseInOrder(root.left);
        System.out.println(root.value);
        if (root.right != null)
            recurseInOrder(root.right);
    }    public static void stackInOrder(TreeNode root) {
        Stack stack = new Stack();
        if (root == null)
            return;
        else
            stack.push(root);
        TreeNode temp = root.left;
        while (temp != null) {
            stack.push(temp);
            temp = temp.left;
        }
        temp = (TreeNode) stack.pop();
        while (temp != null) {
            System.out.println(temp.value);
            temp = temp.right;
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            if (stack.empty())
                break;
            temp = (TreeNode) stack.pop();
        }
    }    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(null, null, 1);
        TreeNode node2 = new TreeNode(null, node1, 2);
        TreeNode node3 = new TreeNode(null, null, 3);
        TreeNode node4 = new TreeNode(node2, node3, 4);
        TreeNode node5 = new TreeNode(null, null, 5);
        TreeNode root = new TreeNode(node4, node5, 0);
        System.out.println("Tree Height is " + getTreeHeight(root));
        System.out.println("Recurse In Order Traverse");
        recurseInOrder(root);
        System.out.println("Stack In Order Traverse");
        stackInOrder(root);
        System.out.println("Recurse Pre Order Traverse");
        recursePreOrder(root);
        System.out.println("Stack Pre Order Traverse");
        stackPreOrder(root);
    }
}用LinkedList重写的Stack:import java.util.EmptyStackException;
import java.util.LinkedList;public class Stack {    private LinkedList list;    public Stack() {
        this.list = new LinkedList();
    }    public boolean empty() {
        return list.isEmpty();
    }    public Object peek() {
        if (empty())
            throw new EmptyStackException();
        return list.getLast();
    }    public Object pop() {
        if (empty())
            throw new EmptyStackException();
        return list.removeLast();
    }    public void push(Object o) {
        list.add(o);
    }    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(new Integer(1));
        stack.push(new Integer(11));
        stack.push(new Integer(1111));
        stack.push(new Integer(22));
        stack.push(new Integer(222));
        stack.push(new Integer(31));
        stack.push(new Integer(221));
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }
}

本人blog里面有一篇实现二叉树前序遍历的例子可以去查看

public class BTNode<E> {
private E data; //存储在结点的数据
private BTNode<E> left; //左孩子
private BTNode<E> right; //右孩子

public BTNode(E initialData, BTNode<E> initialLeft, BTNode<E> initialRight ){
data = initialData;
left = initialLeft;
right = initialRight;
}
public void print(int deep){
for(int i = 1; i <= deep; i++){
System.out.print("-");
}
System.out.print( data + "\n");
if(left != null)
left.print(deep + 1);
if(right != null)
right.print(deep + 1);
}
public static void main(String[] args) {
BTNode<String> a = new BTNode<String>("A", null, null);
BTNode<String> b = new BTNode<String>("B", null, null);
BTNode<String> c = new BTNode<String>("C", null, null);
BTNode<String> d = new BTNode<String>("D", null, null);
BTNode<String> e = new BTNode<String>("E", null, null);
BTNode<String> f = new BTNode<String>("F", null, null);

a.setLeft(b);
a.setRight(c);
b.setLeft(d);
b.setRight(e);
c.setLeft(f);

a.print(0);
}
}

调试易

面试题,用Java实现二叉树

解决方案 »