创新工厂笔试题：输入一个数组，生成一个二叉排序树。

Question

看大家能否与李开复成为同事。

Answer 1

package com.yaowei.datastructure;public class BinTreeNode <T> implements Comparable<BinTreeNode<T>>{
private BinTreeNode<T> leftNode;
private BinTreeNode<T> rightNode;
private T value;
private int balanceFactor;
public BinTreeNode(){
this.leftNode = null;
this.rightNode = null;
this.value = null;
this.balanceFactor = 0;
}
public BinTreeNode(T value){
this.leftNode = null;
this.rightNode = null;
this.value = value;
this.balanceFactor = 0;
}
public BinTreeNode(BinTreeNode <T>leftNode,BinTreeNode<T> rightNode,T value){
this.leftNode = leftNode;
this.rightNode = rightNode;
this.value = value;
}
public void setLeftNode(BinTreeNode <T>leftNode){
this.leftNode = leftNode;
}
public BinTreeNode<T> getLeftNode(){
return this.leftNode;
}
public void setRightNode(BinTreeNode <T>rightNode){
this.rightNode = rightNode;
}
public BinTreeNode<T> getRightNode(){
return this.rightNode;
}
public void setValue(T value){
this.value = value;
}
public T getValue(){
return this.value;
}
public void setBalanceFactor(int balanceFactor){
this.balanceFactor = balanceFactor;
}
public int getBalanceFactor(){
return this.balanceFactor;
}
public int calcBalanceFactor(BinTreeNode<T>node){
if(node.getLeftNode()==null&&node.getRightNode()==null){
return 0;
}else{
return max(calcBalanceFactor(node.getLeftNode()),calcBalanceFactor(node.getRightNode()));
}
}
public int max(int a,int b){
if(a>b){
return a;
}
return b;
}
public boolean isLeaf(){
return (null == this.leftNode && null == this.rightNode);
}
public int compareTo(BinTreeNode<T>node) {
T obj = node.getValue();
// TODO Auto-generated method stub
if(value instanceof String){
return ((String)value).compareTo((String)obj);
}else if(value instanceof Character){
return (String.valueOf(value)).compareTo(String.valueOf(obj));
}else if((value instanceof Byte)){
if(((Byte)value)>((Byte)obj)){
return 1;
}else if(((Byte)value) == ((Byte)obj)){
return 0;
}else{
return -1;
}
}else if(value instanceof Short){
if(((Short)value)>((Short)obj)){
return 1;
}else if(((Short)value) == ((Short)obj)){
return 0;
}else{
return -1;
}
}else if(value instanceof Integer){
if(((Integer)value)>((Integer)obj)){
return 1;
}else if(((Integer)value) == ((Integer)obj)){
return 0;
}else{
return -1;
}
}else if(value instanceof Float){
if(((Float)value)>((Float)obj)){
return 1;
}else if(((Float)value) == ((Float)obj)){
return 0;
}else{
return -1;
}
}else if(value instanceof Long){
if(((Long)value)>((Long)obj)){
return 1;
}else if(((Long)value) == ((Long)obj)){
return 0;
}else{
return -1;
}
}else if(value instanceof Double){
if(((Double)value)>((Double)obj)){
return 1;
}else if(((Double)value) == ((Double)obj)){
return 0;
}else{
return -1;
}
}
return 0;
}}

Answer 2

package com.yaowei.datastructure;
import java.util.ArrayList;
import java.util.Stack;
public class BinTree<T> {
private BinTreeNode<T> rootNode;
public BinTree(){
this.rootNode = null;
}
/**
 * 根据一个数组来构造二叉树
 * 数组中放的是每个结点的value
 * @param array
 */
public BinTree(T[]array){
if(array[0] == null){
this.rootNode = null;
return;
}else{
ArrayList<BinTreeNode<T>> tempList = new ArrayList<BinTreeNode<T>>();
int len = array.length;
int lev = (int)(Math.log(len)/Math.log(2))+1;
//System.out.println("树共有"+lev+"层");
this.rootNode = new BinTreeNode<T>(array[0]);
tempList.add(rootNode);
for(int i=1;i<lev;i++){
if(i<len){
//System.out.println("one:"+((int)Math.pow(2, i)-1));
//System.out.println("two:"+((int)Math.pow(2, i+1)-1));
for(int j=(int)Math.pow(2, i)-1;(j<(int)Math.pow(2, i+1)-1)&&(j<len);j++){
//System.out.println(j);
if(array[j]!=null){
if((j+1)%2==0){
if(j<len&&array[j+1]!=null){
//下一个还有值，表明父结点有两个子结点
BinTreeNode<T> node = tempList.get(0);
BinTreeNode<T> leftNode = new BinTreeNode<T>(array[j]);
node.setLeftNode(leftNode);
tempList.add(leftNode);
}else{
BinTreeNode<T> node = tempList.get(0);
BinTreeNode<T> leftNode = new BinTreeNode<T>(array[j]);
node.setLeftNode(leftNode);
tempList.add(leftNode);
tempList.remove(0);
}
}else{
BinTreeNode<T> node = tempList.get(0);
BinTreeNode<T> rightNode = new BinTreeNode<T>(array[j]);
node.setRightNode(rightNode);
tempList.add(rightNode);
tempList.remove(0);
}
}
}
}
}
tempList = null;
}
}
public ArrayList<T> getObjectArray(){
ArrayList<T> result = new ArrayList<T>();
if(this.getRootNode()==null){
return result;
}else{
ArrayList<BinTreeNode<T>> levList1 = new ArrayList<BinTreeNode<T>>();
ArrayList<BinTreeNode<T>> levList2 = new ArrayList<BinTreeNode<T>>();
levList1.add(this.getRootNode());
result.add(this.getRootNode().getValue());
int levCount1 = 1;
int levCount2 = 0;
BinTreeNode<T> levList1Node = new BinTreeNode<T>();
BinTreeNode<T> levList2Node = new BinTreeNode<T>();
boolean flagForInsertList2 = true;//为真的话往levList2里面插，否则往levList1里面插
//boolean flagAllNULLList1 = true;
//boolean flagAllNULLList2 = false;
while(levCount1!=0||levCount2!=0){
if(flagForInsertList2){
flagForInsertList2 = false;
while((levCount1!=0||levList1.size()!=0)){//从levList1里面找
levList1Node = levList1.get(0);
if(levList1Node==null){
levList2.add(null);
result.add(null);
levList2.add(null);
result.add(null);
}else{//非空
levCount1--;
if(levList1Node.getLeftNode()!=null){
levList2.add(levList1Node.getLeftNode());
result.add(levList1Node.getLeftNode().getValue());
levCount2++;
}else{
levList2.add(null);
result.add(null);
}
if(levList1Node.getRightNode()!=null){
levList2.add(levList1Node.getRightNode());
result.add(levList1Node.getRightNode().getValue());
levCount2++;
}else{
levList2.add(null);
result.add(null);
}
}
levList1.remove(0);
}
}else{
flagForInsertList2 = true;
while(levCount2!=0||levList2.size()!=0){//从levList1里面找
levList2Node = levList2.get(0);
if(levList2Node==null){
levList1.add(null);
result.add(null);
levList1.add(null);
result.add(null);
}else{//非空
levCount2--;
if(levList2Node.getLeftNode()!=null){
levList1.add(levList2Node.getLeftNode());
result.add(levList2Node.getLeftNode().getValue());
levCount1++;
}else{
levList1.add(null);
result.add(null);
}
if(levList2Node.getRightNode()!=null){
levList1.add(levList2Node.getRightNode());
result.add(levList2Node.getRightNode().getValue());
levCount1++;
}else{
levList1.add(null);
result.add(null);
}
}
levList2.remove(0);
}
}
}

}
return result;
}
public void setRootNode(BinTreeNode<T> rootNode){
this.rootNode = rootNode;
}
public BinTreeNode<T> getRootNode(){
return this.rootNode;
}
public void preOrder(BinTreeNode<T>node){
if(node == null){
return;
}
printInfo(node);
if(node.getLeftNode()!=null){
preOrder(node.getLeftNode());
}
if(node.getRightNode()!=null){
preOrder(node.getRightNode());
}
}
public void iteraPreOrder(BinTreeNode<T>node){
Stack<BinTreeNode<T>> stack = new Stack<BinTreeNode<T>>();
if(node != null){
stack.push(node);
while(!stack.empty()){
node = stack.pop();
printInfo(node);
if(node.getLeftNode()!=null){
stack.push(node.getRightNode());
}
if(node.getRightNode()!=null){
stack.push(node.getLeftNode());
}
}
}
}
public void midOrder(BinTreeNode<T>node){
if(node == null){
return;
}
if(node.getLeftNode()!=null){
midOrder(node.getLeftNode());
}
printInfo(node);
if(node.getRightNode()!=null){
midOrder(node.getRightNode());
}
}
public void iteraMidOrder(BinTreeNode<T>p){
Stack<BinTreeNode<T>>stack = new Stack<BinTreeNode<T>>();
BinTreeNode<T> node = p;
while(node != null || stack.size()>0){
while(node != null){
stack.push(node);
node = node.getLeftNode();
}
if(stack.size()>0){
node = stack.pop();
printInfo(node);
node = node.getRightNode();
}
}
}
public void lastOrder(BinTreeNode<T>node){
if(node == null){
return;
}
if(node.getLeftNode()!=null){
lastOrder(node.getLeftNode());
}
if(node.getRightNode()!=null){
lastOrder(node.getRightNode());
}
printInfo(node);
}

Answer 3

public void iteraLastOrder(BinTreeNode<T>p){
BinTreeNode<T> q = p;   
        Stack<BinTreeNode<T>> stack = new Stack<BinTreeNode<T>>();   
        while (p != null) {   
            // 左子树入栈   
            for (; p.getLeftNode() != null; p = p.getLeftNode())   
                stack.push(p);   
            // 当前节点无右子或右子已经输出   
            while (p != null && (p.getRightNode() == null || p.getRightNode() == q)) {   
                printInfo(p);   
                q = p;// 记录上一个已输出节点   
                if (stack.empty())   
                    return;   
                p = stack.pop();   
            }   
            // 处理右子   
            stack.push(p);   
            p = p.getRightNode();   
        }  
}
public void levOrder(BinTreeNode<T>node){
ArrayList<BinTreeNode<T>> tempList = new ArrayList<BinTreeNode<T>>();
tempList.add(node);
while(tempList.size()!=0){
BinTreeNode<T> nodeIndex0 = tempList.get(0);
if(nodeIndex0.getLeftNode()!=null){
tempList.add(nodeIndex0.getLeftNode());
}
if(nodeIndex0.getRightNode()!=null){
tempList.add(nodeIndex0.getRightNode());
}
printInfo(nodeIndex0);
tempList.remove(0);
}
tempList = null;
}
public void printInfo(BinTreeNode<T> node){
System.out.print(node.getValue().toString()+"  ");
}
/**
 * 二叉树深拷贝
 * @param node
 * @param treeNode
 */
public void copy(BinTreeNode<T> node,BinTreeNode<T> treeNode){
if(node == null){
return ;
}else{
treeNode.setValue(node.getValue());
if(node.getLeftNode()!=null){
BinTreeNode<T> tempNode= new BinTreeNode<T>();
treeNode.setLeftNode(tempNode);
copy(node.getLeftNode(),tempNode);
}
if(node.getRightNode()!=null){
BinTreeNode<T> tempNode = new BinTreeNode<T>();
treeNode.setRightNode(tempNode);
copy(node.getRightNode(),tempNode);
}
}

}
public int getLen(T[]preOrder,T[]midOrder){
//System.out.println(preOrder.length+" "+midOrder.length);
//if(preOrder.length==1&&midOrder.length==1&&preOrder[0].equals(midOrder[0]))
//return 1;
int result = 0;
for(int i=0;i<midOrder.length;i++){
if(preOrder[0].equals(midOrder[i])){
//System.out.println(i);
result = i;
}
}
if(result==0)return 1;
//return -1;
return result;
}
public void testInfo(T[]preOrder,T[]midOrder){
System.out.println("testinfo start:");
for(int i=0;i<preOrder.length;i++){
System.out.println("pre"+i+" "+preOrder[i]+ " "+midOrder[i]);
}
}
/**
 * 根据前序和中序遍历重建二叉树，
 * 不支持元素相同的情况
 * @param preOrder
 * @param midOrder
 * @param node
 */
public void rebuild(T[]preOrder,T[]midOrder,BinTreeNode<T>node){
if(preOrder ==null||midOrder==null)
return;
if(preOrder.length==0||midOrder.length==0)
return;
if(preOrder.length==1||midOrder.length==1){
node.setValue(preOrder[0]);
return;
}
node.setValue(preOrder[0]);
int k = getLen(preOrder,midOrder);
if(true){
T[]leftMidOrder = (T[])(new Object[k]);
System.arraycopy(midOrder, 0, leftMidOrder, 0, k);
T[]leftPreOrder = (T[])(new Object[k]);
System.arraycopy(preOrder, 1, leftPreOrder, 0, k);
BinTreeNode<T>leftNode = new BinTreeNode<T>();
node.setLeftNode(leftNode);
testInfo(leftPreOrder,leftMidOrder);
rebuild(leftPreOrder,leftMidOrder,leftNode);
}
int rightLen = midOrder.length - k-1;
if(true){
T[]rightMidOrder = (T[])(new Object[rightLen]);
System.arraycopy(midOrder, k+1, rightMidOrder, 0, rightLen);
T[]rightPreOrder = (T[])(new Object[rightLen]);
System.arraycopy(preOrder, k+1, rightPreOrder, 0, rightLen);
testInfo(rightPreOrder,rightMidOrder);
BinTreeNode<T>rightNode = new BinTreeNode<T>();
node.setRightNode(rightNode);
rebuild(rightPreOrder,rightMidOrder,rightNode);
}
}
    public static void main(String[]args){
     String[]s={"a","b","c","d","e","f","g","h","i","j","k"};
     BinTree<String> bt = new BinTree<String>(s);
     //ArrayList<String>k = bt.getObjectArray();
     //for(int i =0;i<k.size();i++){
     // System.out.println(k.get(i));
     //}
     BinTree<String> copy = new BinTree<String>();
     copy.setRootNode(new BinTreeNode<String>());
     bt.copy(bt.getRootNode(), copy.getRootNode());
     //copy.preOrder(copy.getRootNode());
     //System.out.println();
     //copy.midOrder(copy.getRootNode());
     String[]pre = {"a",  "b",  "d",  "h",  "i",  "e",  "j",  "k",  "c",  "f",  "g"};
     String[]mid = {"h",  "d",  "i",  "b",  "j",  "e",  "k",  "a",  "f",  "c",  "g"};
     BinTree<String>rebuild = new BinTree<String>();
     rebuild.setRootNode(new BinTreeNode<String>());
     bt.rebuild(pre, mid, rebuild.getRootNode());
     System.out.println();
     rebuild.preOrder(rebuild.getRootNode());
     System.out.println();
     rebuild.midOrder(rebuild.getRootNode());
     System.out.println();
     rebuild.iteraPreOrder(rebuild.getRootNode());
     System.out.println();
     rebuild.iteraMidOrder(rebuild.getRootNode());
     System.out.println();
     bt.iteraPreOrder(bt.getRootNode());
     System.out.println();
     bt.lastOrder(bt.getRootNode());
     System.out.println();
     bt.iteraLastOrder(bt.getRootNode());
     System.out.println();
     copy.lastOrder(copy.getRootNode());
     System.out.println();
     copy.iteraLastOrder(copy.getRootNode());
     //System.out.println(bt.getRootNode().getValue());
    }
}

Answer 4

package com.yaowei.datastructure;public class BST<T> extends BinTree<T>{
private BinTreeNode<T> rootNode;
public void setRootNode(BinTreeNode<T>rootNode){
this.insertNode(rootNode);
}
public BinTreeNode<T> getRootNode(){
return this.rootNode;
}
public BST(){
super();
}
public BST(BinTreeNode<T>rootNode){
super();
}
public void insertNode(BinTreeNode<T> node){
if(node == null || node.getValue() == null){
return;
}
node.setLeftNode(null);
node.setRightNode(null);
if(this.rootNode == null){
this.rootNode = node;
return;
}
boolean flag = true;
BinTreeNode<T>tempNode = new BinTreeNode<T>();
tempNode = this.rootNode;
while(flag){
//相等直接退出，别插入了
if(tempNode.compareTo(node) == 0){
return;
}else if(tempNode.compareTo(node)>0){
if(tempNode.getLeftNode()!=null){
tempNode = tempNode.getLeftNode();
}else{
tempNode.setLeftNode(node);
flag = false;
}
}else{
if(tempNode.getRightNode()!=null){
tempNode = tempNode.getRightNode();
}else{
tempNode.setRightNode(node);
flag = false;
}
}

}
}
public void insertValue(T key){
if(key == null){
return;
}
BinTreeNode<T>node = new BinTreeNode<T>(key);
this.insertNode(node);
}
/**
 * 1。若p有左子树，用p的左孩子取代它；
 * 找到其左子树的最右边的叶子结点r，
 * 把p的右子树作为r的右子树。
     * 2。若p没有左子树，直接用p的右孩子取代它。
 * @param key
 */
public void deleteValue(T key){
if(key == null){
return;
}
BinTreeNode<T>node = new BinTreeNode<T>(key);
if(this.getRootNode() == null || this.getRootNode().getValue() == null){
return;
}
BinTreeNode<T>parentNode = this.getRootNode();
BinTreeNode<T>tempNode = this.getRootNode();
while(true){
if(tempNode.compareTo(node) == 0){
//找到要删除的结点了
//case 1 tempNode有左子树
if(tempNode.getLeftNode()!=null){
BinTreeNode<T>leftNode = tempNode.getLeftNode();
BinTreeNode<T>rightNode = tempNode.getRightNode();
BinTreeNode<T>subLeftNode = leftNode.getLeftNode();
BinTreeNode<T>subRightNode = leftNode.getRightNode();
tempNode.setValue(leftNode.getValue());
leftNode.setLeftNode(null);
leftNode.setRightNode(null);
leftNode = null;
tempNode.setLeftNode(subLeftNode);
tempNode.setRightNode(subRightNode);
while(tempNode.getRightNode()!=null){
tempNode = tempNode.getRightNode();
}
tempNode.setRightNode(rightNode);
}
//case 2 tempNode无左子树
else{
if(tempNode.getRightNode()==null){
if(parentNode.compareTo(this.getRootNode())==0){
this.rootNode = null;
return;
}
if(parentNode.getLeftNode()!=null&&parentNode.getLeftNode().compareTo(tempNode)==0){
parentNode.setLeftNode(null);
}else{
parentNode.setRightNode(null);
}
tempNode = null;
}else{
BinTreeNode<T>leftNode = tempNode.getRightNode().getLeftNode();
BinTreeNode<T>rightNode = tempNode.getRightNode().getRightNode();
BinTreeNode<T>tempRightNode = tempNode.getRightNode();
tempNode.setLeftNode(leftNode);
tempNode.setRightNode(rightNode);
tempNode.setValue(tempRightNode.getValue());
tempRightNode.setLeftNode(null);
tempRightNode.setRightNode(null);
tempRightNode = null;
}
}
//删除end
return;
}else if(tempNode.compareTo(node)>0){
if(tempNode.getLeftNode()==null){
return;
}else{
parentNode = tempNode;
tempNode = tempNode.getLeftNode();
}
}else{
if(tempNode.getRightNode()==null){
return;
}else{
parentNode = tempNode;
tempNode = tempNode.getRightNode();
}
}
}
}
public boolean exists(T key){
BinTreeNode<T>node = new BinTreeNode<T>(key);
if(this.getRootNode() == null || this.getRootNode().getValue() == null){
return false;
}
BinTreeNode<T>tempNode = this.getRootNode();
while(true){
if(tempNode.compareTo(node) == 0){
return true;
}else if(tempNode.compareTo(node)>0){
if(tempNode.getLeftNode()==null){
return false;
}else{
tempNode = tempNode.getLeftNode();
}
}else{
if(tempNode.getRightNode()==null){
return false;
}else{
tempNode = tempNode.getRightNode();
}
}
}
}
    public static void main(String[]args){
     BST<String> b = new BST<String>();
     b.insertValue("donglei");
     b.insertValue("yaowei");
     b.insertValue("p");
     b.insertValue("kk");
     b.insertValue("c");
     b.insertValue("ff");
     b.insertValue("sven");
     b.insertValue("snk");
     b.insertValue("lina");
     b.insertValue("qop");
     b.midOrder(b.getRootNode());
     System.out.println();
     System.out.println(b.exists("donglei"));
     System.out.println(b.exists("yaowei"));
     //System.out.println(b.getRootNode().getValue());
     b.deleteValue("ff");
     b.midOrder(b.getRootNode());
     System.out.println();
     b.levOrder(b.getRootNode());
    }
}avl还没搞出来
数据有序的话就成链表了

Answer 5

class BinaryTree{
class Node{ // 声明一个节点类
private Comparable data ; // 保存具体的内容
private Node left ; // 保存左子树
private Node right ; // 保存右子树
public Node(Comparable data){
this.data = data ;
}
public void addNode(Node newNode){
// 确定是放在左子树还是右子树
if(newNode.data.compareTo(this.data)<0){ // 内容小，放在左子树
if(this.left==null){
this.left = newNode ; // 直接将新的节点设置成左子树
}else{
this.left.addNode(newNode) ; // 继续向下判断
}
}
if(newNode.data.compareTo(this.data)>=0){ // 放在右子树
if(this.right==null){
this.right = newNode ; // 没有右子树则将此节点设置成右子树
}else{
this.right.addNode(newNode) ; // 继续向下判断
}
}
}
public void printNode(){ // 输出的时候采用中序遍历
if(this.left!=null){
this.left.printNode() ; // 输出左子树
}
System.out.print(this.data + "\t") ;
if(this.right!=null){
this.right.printNode() ;
}
}
};
private Node root ; // 根元素
public void add(Comparable data){ // 加入元素
Node newNode = new Node(data) ; // 定义新的节点
if(root==null){ // 没有根节点
root = newNode ; // 第一个元素作为根节点
}else{
root.addNode(newNode) ; // 确定是放在左子树还是放在右子树
}
}
public void print(){
this.root.printNode() ; // 通过根节点输出
}
};
public class Compare{
public static void main(String args[]){
BinaryTree bt = new BinaryTree() ;
bt.add(8) ;
bt.add(3) ;
bt.add(3) ;
bt.add(10) ;
bt.add(9) ;
bt.add(1) ;
bt.add(5) ;
bt.add(5) ;
System.out.println("排序之后的结果：") ;
bt.print() ;
}
};

Answer 6

#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> struct node { 
int value; 
struct node* left; 
struct node* right; 
}; 
typedef struct node NODE; 
typedef struct node* PNODE; PNODE creat( PNODE tree,PNODE r,int value) 
{ 
if(!r) 
{ 
r = (PNODE)malloc(sizeof(NODE)); 
if(!r) 
{ 
printf("内存分配失败！"); 
exit(0); 
} 
r->left = NULL; 
r->right = NULL; 
r->value = value; 
if(!tree) 
return r; 
if(value<tree->value) 
tree->left = r; 
else 
tree->right = r; 
return r; 
} 
if(value < r->value) 
creat(r,r->left,value); 
else 
creat(r,r->right,value); 
return tree; 
} 
void new_node (PNODE* n, int value) { *n = (PNODE)malloc (sizeof(NODE)); 
if (*n != NULL) { 
(*n)->value = value; 
(*n)->left = NULL; 
(*n)->right = NULL; 
} 
} 
void free_node (PNODE* n) { 
if ((*n) != NULL) { 
free (*n); 
*n = NULL; 
} 
} 
/* 查找结点 */ 
PNODE find_node (PNODE n, int value) { 
if (n == NULL) { 
return NULL; 
} else if (n->value == value) { 
return n; 
} else if (value <= n->value) { 
return find_node (n->left, value); 
} else { 
return find_node (n->right, value); 
} 
} 
/* 插入结点 */ 
void insert_node (PNODE* n, int value) { 
if (*n == NULL) { 
new_node (n, value); 
} else if (value == (*n)->value) { 
return; 
} else if (value < (*n)->value) { 
insert_node (&((*n)->left), value); 
} else { 
insert_node (&((*n)->right), value); 
} 
} /* 删除结点 */ 
void deletenode (PNODE *n) { 
PNODE tmp = NULL; 
if (n == NULL) return; 
if ((*n)->right == NULL) { 
tmp = *n; 
*n = (*n)->left; 
free_node (n); 
} else if ((*n)->left == NULL) { 
tmp = *n; 
*n = (*n)->right; 
free_node (n); 
} else { 
for (tmp = (*n)->right; tmp->left != NULL; tmp = tmp->left); 
tmp->left = (*n)->left; 
tmp = (*n); 
*n = (*n)->right; 
free_node (&tmp); 
} 
} 
void delete_node (PNODE *n, int value) { 
PNODE node; 
if (n == NULL) return; 
node = find_node (*n, value); 
if ((*n)->value == value) { 
deletenode (n); 
} else if (value < (*n)->value) { 
delete_node (&((*n)->left), value); 
} else { 
delete_node(&((*n)->right), value); 
} 
} 
void pre_order_traversal(PNODE n) /* 前序遍历 */
{ 
if (n != NULL) { 
printf ("%i ", n->value); 
pre_order_traversal (n->left); 
pre_order_traversal( n->right); 
} 
} 
void in_order_traversal (PNODE n) /* 中序遍历 */
{ 
if (n != NULL) { 
in_order_traversal (n->left); 
printf ("%i ", n->value); 
in_order_traversal ( n->right); 
} 
} 
void post_order_traversal (PNODE n) /* 后序遍历 */
{ 
if (n != NULL) { 
post_order_traversal (n->left); 
post_order_traversal (n->right); 
printf ("%i ", n->value); 
} 
} 
int get_num_nodes (PNODE n) /* 计算树的节点数 */
{int left = 0; 
int right = 0; 
if (n == NULL) { 
return 0; 
} 
if (n->left != NULL) { 
left = get_num_nodes (n->left); 
} 
if (n->right != NULL) { 
right = get_num_nodes (n->right); 
} 
return (left + 1 + right); 
} 
int main() { 
char buf[50]; 
int i,n,option,s[80]; 
PNODE tree = NULL;/*树的第一个结点*/ 
PNODE node = NULL; 
while (1) { 
printf ("--------------------------\n"); 
printf ("Options are:\n\n"); 
printf (" 0 Creat tree\n"); 
printf (" 1 Insert node\n"); 
printf (" 2 Delete node\n"); 
printf (" 3 Find node\n"); 
printf (" 4 Pre order traversal\n"); /* 前序遍历 */ 
printf (" 5 In order traversal\n"); /* 中序遍历 */ 
printf (" 6 Post order traversal\n");/* 后序遍历 */ 
printf (" 7 Node Count\n"); 
printf (" 8 Exit\n\n"); 
printf ("--------------------------\n"); 
printf ("Select an option: "); 
fgets (buf, sizeof(buf), stdin); 
sscanf (buf, "%i", &option); 
printf ("--------------------------\n"); 
if (option < 0 || option > 12) { 
fprintf (stderr, "Invalid option"); 
continue; 
} 
switch (option) { 
case 0: 
printf ("Enter number of elements of array: "); 
scanf("%d",&n); 
printf ("Enter %d elements of array:\n",n); 
for(i=0;i<n;i++) 
{ scanf("%d",&s[i]); 
tree = creat(tree,tree,s[i]); 
} 
fflush(stdin); 
break; 
case 1: 
printf ("Enter number to insert: "); 
fgets (buf, sizeof(buf), stdin); 
sscanf (buf, "%i", &option); 
printf ("\n\n"); 
insert_node (&tree, option); 
break; 
case 2: 
printf ("Enter number to delete: "); 
fgets (buf, sizeof(buf), stdin); 
sscanf (buf, "%i", &option); 
printf ("\n\n"); 
delete_node (&tree, option); 
break; 
case 3: 
printf ("Enter number to find: "); 
fgets (buf, sizeof(buf), stdin); 
sscanf (buf, "%i", &option); 
printf ("\n\n"); 
node = find_node (tree, option); 
if (node != NULL) { 
printf ("Found node\n\n"); 
} else { 
printf ("There is no node which you input!\n\n"); 
} 
break; 
case 4: 
printf ("Pre order traversal: "); 
pre_order_traversal (tree); 
printf ("\n\n"); 
break; 
case 5: 
printf ("In order traversal: "); 
in_order_traversal (tree); 
printf ("\n\n"); 
break; 
case 6: 
printf ("Post order traversal: "); 
post_order_traversal (tree); 
printf ("\n\n"); 
break; 
case 7: 
printf ("Node Count is %i\n\n", get_num_nodes (tree)); 
break; 
case 8: 
exit (0); 
} 
} 
return 0; 
} 本人从c区转来搞点分，java代码没有，但c代码也足以说明此数据结构的问题，与用啥开发语言没有关系程序按你的要求改写，去掉了不少功能，大大简化，但总体功能依旧强大。 
先要选择0，创建一棵树，然后程序提示你要输入的数组数字的个数，比如要输入10个数字，输入10，然后再分别输入各个数字。要注意看程序提示。

Answer 7

先将数组排序，然后中间元素为树的根，中间以左为左子树，中间以右为右子树。C++代码大概如下:class TreeNode {
public:
TreeNode(int num): data(num), left(NULL), right(NULL) {}
......
......
private:
int data;
TreeNode *left;
TreeNode *right;
};TreeNode *createTreeNode(int num) {
return new TreeNode(num);
}TreeNode *createTreeFromArray(int *array, int begin, int end) {
// @param array: 已经排序数组
// @param begin: 数组第一个位置
// @param end:   数组最后一位加一
if((end - begin) == 1) {
// 数组只有一个元素，直接返回一个节点
return createTreeNode(array[0]);
}

int middle = (begin + end)/2; // 数组中间数位置
TreeNode *root = createTreeNode(array[middle]); // 以中间数为二叉排序树的根
root->left = createTreeFromArray(array, begin, middle); // 得到左子树
root-right = createTreeFromArray(array, middle+1, end); // 得到右子树
return root;
}

Answer 8

class TreeNode { 
public: 
    TreeNode(int num): data(num), left(NULL), right(NULL) {} 
    ...... 
    ...... 
private: 
    int data; 
    TreeNode *left; 
    TreeNode *right; 
}; TreeNode *createTreeNode(int num) { 
    return new TreeNode(num); 
} TreeNode *createTreeFromArray(int *array, int begin, int end) { 
    // @param array: 已经排序数组 
    // @param begin: 数组第一个位置 
    // @param end: 数组最后一位加一 
    if((end - begin) == 1) { 
        // 数组只有一个元素，直接返回一个节点 
         return createTreeNode(array[0]); 
    }     int middle = (begin + end)/2; // 数组中间数位置 
     TreeNode *root = createTreeNode(array[middle]); // 以中间数为二叉排序树的根 
     root->left = createTreeFromArray(array, begin, middle); // 得到左子树 
     root-right = createTreeFromArray(array, middle+1, end); // 得到右子树 
     return root; 
}