二叉树问题---握手问题

Question

题目一：根据二叉树前序，中序序列，编程输出该树的后序序列。
如给出：
前序：ABCDEF
中序：BCDEFA
上面给出的两个序列不一定是正确的，因此写出的程序还要求判断给出的序列是否是一棵正确的二叉树，如果不正确，返回“failed！”。题目二：握手问题。
李氏夫妇请其他四对夫妇吃饭，已知他们自己不能自己握手，不能后自己配偶握手，和其他人握手最多只能一次，最后，李某问其他人握手了几次，他们每个人的答案都不一样，问：李氏夫人握手了几次？

Answer 1

thanks  ~~ jie tie gei ni 20

Answer 2

import java.io.BufferedReader;
import java.io.InputStreamReader;public class TreeNode {
 public static String res = "";
 static int findchar(String s,char a){
  for(int i=0;i<s.length();i++){
   if(a==s.charAt(i))
    return i;
  }
  return -1;
 }
 static boolean StringEquals(String a1,String a2){
  boolean state= true;
  if(a1.length()!=a2.length()){
   state = false;
  }
  if(a1.length()==a2.length()){
   for(int i=0;i<a1.length();i++){
    if(findchar(a2,a1.charAt(i))==-1)
     state = false;
   }
  }
  return state;
 }
 static void cal_tree(String sa,String sb){
  boolean state = StringEquals(sa,sb);
  if(state==false)
   return ;
  if(sb.length()==0)
   return ;
  if(sb.length()==1){
   //System.out.print(sb);
   res+=sb;
   return ;
  }
  char x = sa.charAt(0);
  int mid = findchar(sb,x);
  String c = sb.substring(0,mid);
  String d = sb.substring(mid+1);
  cal_tree(sa.substring(1,c.length()+1),c);
  cal_tree(sa.substring(1+c.length()),d);
  res+=String.valueOf(x);
  //System.out.print(x);
  return ;
 }
 public static void main(String[] agrs){
  try {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   while(true){
    System.out.println("前序：");
    String s1 = br.readLine().trim();
    System.out.println("中序：");
    String s2 = br.readLine().trim();
    System.out.println("后序：");
    cal_tree(s1,s2);
    if(res.length()!=s1.length())
     System.out.println("NO ANSWER!");
    else{
     System.out.println(res);
     res="";
    }
    System.out.println("继续或者结束：Y/N");
    if(br.readLine().trim().equalsIgnoreCase("Y")){
     continue;
    }
    else{
     break;
    }
   }
   //cal_tree("DBACEGF","ABCDEFG");
   //cal_tree("ABCD","BDAC");  
  } catch (Exception e) {
   // TODO Auto-generated catch block
   System.out.println("NO ANSWER!");
  }
 }
}

Answer 3

public class SortTree
{
public static void main(String[] args)
{
char[] preSort = {'A', 'B', 'C', 'D', 'E', 'F'};

char[] midSort = {'B', 'C', 'D', 'E', 'F', 'A'};

TreeVo tree = constructTree(preSort, midSort);

printLatTree(tree);
}

public static TreeVo constructTree(char[] preSort, char[] midSort)
{
TreeVo tree = new TreeVo();

int index = find(preSort, midSort);

char[] lMidSort = new char[index];

char[] rMidSort = new char[midSort.length - index - 1];

System.arraycopy(midSort, 0, lMidSort, 0, lMidSort.length);

System.arraycopy(midSort, index + 1, rMidSort, 0, rMidSort.length);

tree.setRoot(midSort[index]);

if(index == 0)
{
tree.setLchild(null);
}
else
{
tree.setLchild(constructTree(preSort, lMidSort));
}

if(index == midSort.length - 1)
{
tree.setRchild(null);
}
else
{
tree.setRchild(constructTree(preSort, rMidSort));
}

return tree;
}

public static int find(char[] preSort, char[] midSort)
{
for(int i = 0; i < preSort.length; i++)
{
for(int j = 0; j < midSort.length; j++)
{
if(preSort[i] == midSort[j])
{
return j;
}
}
}
return -1;
}

public static void printLatTree(TreeVo tree)
{
if(tree == null)
{
return;
}

printLatTree(tree.getLchild());
printLatTree(tree.getRchild());
System.out.print(tree.getRoot());
}
}public class TreeVo
{
private char root;

private TreeVo lchild;

private TreeVo rchild; public TreeVo getLchild() {
return lchild;
} public void setLchild(TreeVo lchild) {
this.lchild = lchild;
} public TreeVo getRchild() {
return rchild;
} public void setRchild(TreeVo rchild) {
this.rchild = rchild;
} public char getRoot() {
return root;
} public void setRoot(char root) {
this.root = root;
}
}

Answer 4

主要思路是用递归的方法,根据先序和中序把二叉树构造出来,然后再递归的把树用后序输出.核心的方法是
public static TreeVo constructTree(char[] preSort, char[] midSort)
输入: preSort代表先序序列,midSort代表中序序列
输出: 根据输入参数构造好的二叉树(TreeVo包含3个成员变量: root树根节点的值,lChild左子树,rChild右子树)处理思想: 在midSort中定位在preSort中最先出现的节点,这就是当前树的根节点,然后把midSort拆分两部分,根节点前面的部分就是左子树,后面部分就是右子树.
按照这样的思想一直递归,得到原来的二叉树.