解决问题100分全拿走要快哦！

Question

经典数据结构试题：
用java对二杈数ABCDEFGH进行,先序排序,  后序排序.
并带注释

Answer 1

此回复为自动发出,仅用于显示而已，并无任何其他特殊作用
楼主【systemoutprint】截止到2008-06-25 17:56:10的历史汇总数据(不包括此帖)：
发帖数:0                  发帖分:0                  
结贴数:0                  结贴分:0                  
未结数:0                  未结分:0                  
结贴率:-------------------结分率:-------------------
如何结贴请参考这里：http://topic.csdn.net/u/20080501/09/ef7ba1b3-6466-49f6-9d92-36fe6d471dd1.html

Answer 2

.....发分绝对结帖
void  PostOrder ( Bnode  * t )
{
if ( t ) 
{
        PostOrder ( t->lchild );
        PostOrder ( t->rchild );
        Visite(t->data);
    }
}
遍历得到的是后序序列GDBEHFCA。void  PreOrder ( Bnode  * t )  
{
if  ( t )  
{
        visite (t->data);   /* 访问结点内容 */
        PreOrder ( t->lchild );  /* 遍历左子树 */
        PreOrder ( t->rchild );  /* 遍历右子树 */
}
}
二叉树进行遍历得到的是先序序列ABDGCEFH。

Answer 3

public class BinTree {/**
* @param args
*/
public static void main(String[] args) {System.out.println("Please the string of a tree(space indicating null tree:");
String s=DataStructures.inputString();
Tree root=createTreeFromString(s,0);
if(root!=null)
{
System.out.print("The pre order traverse:");
System.out.println(PreOrderTraverse(root));
System.out.print("The pre order traverse(not nested simple):");
System.out.println(PreOrderTraverseNotNestedSimple(root));
System.out.print("The in order traverse:");
System.out.println(InOrderTraverse(root));
System.out.print("The in order traverse(not nested):");
System.out.println(InOrderTraverseNotNested(root));
System.out.print("The in order traverse(not nested simple):");
System.out.println(InOrderTraverseNotNestedSimple(root));
System.out.print("The post order traverse:");
System.out.println(PostOrderTraverse(root));
System.out.print("The post order traverse(not nested):");
System.out.println(PostOrderTraverseNotNested(root));}
}/**
* Create a binary tree
* @param s - the string of the tree.
*
space reprensents the tree is null.
* @return
*/
public static Tree createTreeFromString(String s,int i){
if(s==null || s.length()==0) return null;
Tree t=null;
if(i
t=new Tree();
t.data=s.charAt(i);
t.left=createTreeFromString(s,2*i+1);
t.right=createTreeFromString(s,2*i+2);
}
return t;
}public static String PreOrderTraverse(Tree root)
{
StringBuilder builder=new StringBuilder();
if(root!=null) {
builder.append(root.data);
builder.append(PreOrderTraverse(root.left));
builder.append(PreOrderTraverse(root.right));
}
return new String(builder);
}public static String PreOrderTraverseNotNestedSimple(Tree root){
Stack> stack=new Stack>();
Tree p=root;
StringBuilder builder=new StringBuilder();
while(p!=null || !stack.empty()){
if(p!=null){
builder.append(p.data);
stack.push(p);
p=p.left;
}
else{
p=stack.pop().right;
}
}
return new String(builder);
}public static String InOrderTraverse(Tree root)
{
StringBuilder builder=new StringBuilder();
if(root!=null){
builder.append(InOrderTraverse(root.left));
builder.append(root.data);
builder.append(InOrderTraverse(root.right));
}
return new String(builder);
}public static String InOrderTraverseNotNested(Tree root)
{
Tree p=root;
StringBuilder builder=new StringBuilder();
Stack> stack=new Stack>();
boolean visted=false;
while(p!=null){
if(p.left!=null && !visted){
stack.push(p);
p=p.left;
}
else{
builder.append(p.data);
if(p.right!=null) {p=p.right;visted=false;}
else{
if(stack.empty()) break;
else {p=stack.pop();visted=true;}
}
}
}
return new String(builder);
}public static String InOrderTraverseNotNestedSimple(Treeroot){
StringBuilder builder=new StringBuilder();
Stack> stack=new Stack>();
Tree p=root;
while(p!=null || !stack.empty())
{
if(p!=null){
stack.push(p);p=p.left;
}
else{
p=stack.pop();
builder.append(p.data);
p=p.right;
}
}
return new String(builder);
}public static String PostOrderTraverse(Tree root)
{
StringBuilder builder=new StringBuilder();
Tree p=root;
if(p!=null){
builder.append(PostOrderTraverse(p.left));
builder.append(PostOrderTraverse(p.right));
builder.append(p.data);
}
return new String(builder);
}public static String PostOrderTraverseNotNested(Tree root)
{
StringBuilder builder=new StringBuilder();
Stack> stack=new Stack>();
Tree p=root;
do{
if(p!=null){
stack.push(p);
p=p.left;
}
else
{
boolean visited=true;
Tree q=null;
while(visited && !stack.empty()){
p=stack.get(stack.size() - 1);
if(p.right==q){
builder.append(p.data);
stack.pop();
q=p;
}
else
{
p=p.right;
visited=false;
}
}
}
}
while(!stack.empty());
return new String(builder);
}
private static class Tree{
T data;
Tree left=null,right=null;
}
}辅助类文件：/**
* DataStructures.java
*/
package com.zyh.test;
import java.util.*;
/**
* @author zhyhang
*
*/
public class DataStructures {/**
* @param args
*/
public static void main(String[] args) {
//test add list
System.out.println("Please input some integers for a new list:");
ZList p=inputIntList();
printList(p);
}public static Integer[] inputInt()
{
Scanner scan=new Scanner(System.in);
ArrayList a=new ArrayList();
while(scan.hasNextInt())
a.add(scan.nextInt());
return a.toArray(new Integer[0]);
}public static int[] inputint()
{
Integer[] a=inputInt();
int[] b=new int[a.length];
for(int i=0;i!=a.length;++i) b[i]=a[i];
return b;
}public static String inputString()
{
Scanner scan=new Scanner(System.in);
if(scan.hasNextLine())
return scan.nextLine();
else return "";
}public static void printValues(T[] values)
{
for(T v:values)
System.out.print(v+"\t");
System.out.println();
}public static ZList inputIntList()
{
ZList head=null,p=head;
Scanner sca=new Scanner(System.in);
while(sca.hasNextInt()){
Integer i=sca.nextInt();
if(head==null){
head=new ZList();
head.data=i;
p=head;
}
else{
p.next=new ZList();
p.next.data=i;
p=p.next;
}
}
return head;}
public static void printList(ZList head)
{
ZList p=head;
while(p!=null){
System.out.print(p.data+"->");
p=p.next;
}
if(head!=null) System.out.println("end.");
else System.out.println("null list.");
}
/**
* @author zhyhang
*
*/
public final static class ZList {
public T data=null;
public ZList next=null;
public ZList()
{
}
}}

Answer 4

import java.util.concurrent.ConcurrentLinkedQueue;
/**
* 排序二叉树.
*/
public class BSTree {
//定义根节点
    BSTNode root;
//定义树的深度
    int level;
//定义构造方法，创建一颗新二叉树
    public BSTree(){
        root=null;
    }
//判断二叉树是否为空
    public boolean isEmpty(){
        return root==null;
    }
//插入新节点
    public void insert(int o){
        if(isEmpty())
            this.root=new BSTNode(o);
        else{
            BSTNode tmp=this.root;
            boolean flag=false;
            while((tmp.left!=null||tmp.right!=null)&&!flag){
                if(tmp.left!=null&&tmp.right==null){
                    if(tmp.data>o)
                        tmp=tmp.left;
                    else
                        flag=true;
                }
                if(tmp.left==null&&tmp.right!=null){
                    if(tmp.data>o)
                        flag=true;
                    else
                        tmp=tmp.right;
                }
                if(tmp.left!=null&&tmp.right!=null){
                    if(tmp.data>o)
                        tmp=tmp.left;
                    else
                        tmp=tmp.right;
                }
            }
            if(tmp.data>o)
                tmp.left=new BSTNode(o);
            else
                tmp.right=new BSTNode(o);
        }
    }
//删除节点
    public BSTNode delete(int o){
        if(isEmpty()){
            System.err.println("这是一颗空二叉树");
            return null;
        }else{
            BSTNode tmp=root;
            BSTNode buf=null;
            boolean flag=true;
            while(tmp!=null){
                if(tmp.data>o){
                    buf=tmp;
                    tmp=tmp.left;
                    flag=true;
                }
                else if(tmp.data<o){
                    buf=tmp;
                    tmp=tmp.right;
                    flag=false;
                }
                else{
                    if(buf==null){
                        if(root.left==null&&root.right==null){
                            int n=root.data;
                            root=null;
                            return new BSTNode(n);
                        }else if(root.left!=null&&root.right!=null){
                            BSTNode N=root.left;
                            while(N.right!=null)
                                N=N.right;
                            N.right=root.right;
                            BSTNode rootin=root;
                            root=root.left;
                            rootin.left=null;
                            rootin.right=null;
                            return rootin;
                        }else{
                            if(root.left!=null){
                                BSTNode rootin=root;
                                root=root.left;
                                rootin.left=null;
                                return rootin;
                            }else{
                                BSTNode rootin=root;
                                root=root.right;
                                rootin.right=null;
                                return rootin;
                            }
                        }
                    }
//如果tmp的左右节点都为空，只需要改变tmp父节点的左右指向=null即可
//flag=true说明tmp是父节点的左节点，flag=false说明tmp是父节点的右节点                    
                    if(tmp.left==null&&tmp.right==null){
                        if(flag){
                            buf.left=null;
                            return tmp;
                        }else{
                            buf.right=null;
                            return tmp;
                        }
                    }else if(tmp.left==null&&tmp.right!=null){
//如果tmp只有一个子节点，就把该子节点作为tmp父节点的相应子节点即可
//flag=true说明tmp是父节点的左节点，flag=false说明tmp是父节点的右节点
                        if(flag){
                            buf.left=tmp.right;
                            tmp.right=null;
                            return tmp;
                        }else{
                            buf.right=tmp.right;
                            tmp.right=null;
                            return tmp;
                        }
                    }else if(tmp.left!=null&&tmp.right==null){
//flag=true说明tmp是父节点的左节点，flag=false说明tmp是父节点的右节点                       
                        if(flag){
                            buf.left=tmp.left;
                            tmp.left=null;
                            return tmp;
                        }else{
                            buf.right=tmp.left;
                            tmp.left=null;
                            return tmp;
                        }
                    }else{
/**
* 如果tmp的左右节点都不为空，则把tmp的左节点作为tmp父节点的左节点，
* 把tmp的右节点作为tmp前驱节点。前驱节点是中序遍历时tmp的前遍历。
* 先找tmp的左节点S，再不断遍历S的右节点，直到S的右节点为空，则S就是tmp的前驱节点。
*/
                        BSTNode S=tmp.left;
                        while(S.right!=null)
                            S=S.right;
                        S.right=tmp.right;
//flag=true说明tmp是父节点的左节点，flag=false说明tmp是父节点的右节点
                        if(flag)
                            buf.left=tmp.left;
                        else
                            buf.right=tmp.left;
                        tmp.left=null;
                        tmp.right=null;
                        return tmp;
                    }
                }
            }
            System.err.println("找不到该节点");
            return null;
        }
    }
//建造一棵二叉树
    public void build(int[] on){
        for(int i=0;i<on.length;i++)
            insert(on[i]);
    }
//获取二叉树的深度
    public int depth(BSTNode n){
        if(n==null)
            return 0;
        else
            return depth(n.left)>depth(n.right)?depth(n.left)+1:depth(n.right)+1;
    }
//中序遍历二叉树
    public void printmid(BSTNode n){
        if(n!=null){
            printmid(n.left);
            System.out.print(n.data+" ");
            printmid(n.right);
        }
    }
//前序遍历二叉树
    public void printfro(BSTNode n){
        if(n!=null){
            System.out.print(n.data+" ");
            printfro(n.left);
            printfro(n.right);
        }
    }
//后序遍历二叉树
    public void printbeh(BSTNode n){
        if(n!=null){
            printbeh(n.left);
            printbeh(n.right);
            System.out.print(n.data+" ");
        }
    }
//层次遍历二叉树
//先被访问节点的子节点要早于后被访问节点的子节点被访问，所以用FIFO队列实现    
    public void printlev(BSTNode n){
        if(n!=null){
            ConcurrentLinkedQueue<BSTNode> q=new ConcurrentLinkedQueue<BSTNode>();
            System.out.print(n.data+" ");
            if(n.left!=null)
                q.offer(n.left);
            if(n.right!=null)
                q.offer(n.right);
            while(!q.isEmpty()){
                BSTNode tmp= q.poll();//从对列中取出数据
                System.out.print(tmp.data+" ");
                if(tmp.left!=null)//左节点不为空就入队列
                    q.offer(tmp.left);
                if(tmp.right!=null)//右节点不为空就入队列
                    q.offer(tmp.right);
            }
        }
    }//判断此二叉树是否平衡
    public boolean isBalance(BSTNode n){
        if(n!=null){
            if(depth(n.left)-depth(n.right)>1||depth(n.right)-depth(n.left)>1)
                return false;
            else
                return isBalance(n.left)&&isBalance(n.right);
        }
        return true;
    }
}
class BSTNode{
    BSTNode left;
    BSTNode right;
    int data;
    BSTNode(BSTNode l,int o,BSTNode r){
        this.left=l;
        this.data=o;
        this.right=r;
    }
    BSTNode(BSTNode l,int o){
        this(l,o,null);
    }
    BSTNode(int o,BSTNode r){
        this(null,o,r);
    }
    BSTNode(int o){
        this(null,o,null);    
    }
}呵呵，‘还差94个字符’，这次帖的有点多

Answer 5

 如果tmp的左右节点都不为空，则把tmp的左节点作为tmp父节点的左节点，
 把tmp的右节点作为tmp前驱节点。前驱节点是中序遍历时tmp的前遍历。
 先找tmp的左节点S，再不断遍历S的右节点，直到S的右节点为空，则S就是tmp的前驱节点。