二叉树

引用

【一】
写一个程序给出两个集合A，B的大小m，n（0<=m,n<=100）,以及集合内的元素（均为整数），求集合A-B{x|x属于A且x不属于B}并输出结果（顺序任意）

例如：输入
５３
４３２１５
６２３
输出 ４　　１５

package com.ch.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Test1 {
	
	
	public void  getResult(){

		   List<Integer>  lista= new ArrayList();
		   List<Integer>  listb=new ArrayList();
		   List<Integer>  listc=new ArrayList();
		   List<Integer>  listd=new ArrayList();
		 
		
		Scanner inputA = new Scanner( System.in );
		Scanner inputB = new Scanner( System.in );

	    System.out.println("请输入第一个集合个数：");
	    int a= inputA.nextInt();
	    System.out.println("请输入第一个集合"+a+"个元素：");
	    for (int i = 0; i < a; i++)
	    {
	        lista.add(inputA.nextInt());
	    }
	    
	    System.out.println("请输入第二个集合个数：");
	    int b= inputB.nextInt();
	    System.out.println("请输入第二个集合"+b+"个元素：");
	    for (int i = 0; i < b; i++)
	    {      
	        listb.add(inputB.nextInt());
	    }
	    
	    for(int i=0; i<lista.size();i++){
	    	
	    	for(int j=0; j<listb.size();j++){
	    		
	    		if(lista.get(i)==listb.get(j))
	    		{
	    			listc.add(lista.get(i));
	    		}
	    	}
	    }
	    for (int i = 0; i < lista.size(); i++)
	    {   int info =0;
	    	for(int j=0;j<listc.size();j++){
	    		if(lista.get(i)==listc.get(j)){
	    		    info=1;
	    		}
	    	  }
	    	  if(info==1){
	    		  System.out.println("");
	          }else{
	        	  listd.add(lista.get(i));
	          }
	    } 
      
	    System.out.println("输出结果为：");
	   for (int i = 0; i < listd.size(); i++)
	    {      
	    	System.out.println( listd.get(i));
	    }
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Test1 t =new Test1();
		t.getResult();
	}

}

引用

【二】
给一个二叉树（结点一“A-Z或a-z表示”，切无重复字母）的节点大小，以及先根遍历序列和中根遍历序列，输出他的后根遍历数列
例如：
输入7
  ABCDEFG
  CBEDAFG
输出
    CEDBGFA

从例题分析得：
根据先根遍历序列，我们可知道A为主根
根据中根遍历序列，我们可知道CBED在A根的左边，FG在A根的右边
以此递归，
根据先根遍历序列，我们可知道B为次根，且居左；
F为A的次根，且居右，G为F的次根
我们再以B根为主根分析，
根据中根遍历序列，我们可知道C在B根的左边，ED在B根的右边
再根据先根遍历序列，我们可知道，D为B根的次根，E为D的次根
这样我们就可得到
       A
     /   \
    B     F
   / \      \
  C   D      G
       \
        E

由此可推断出后根序列。

• C语言方法

//方法一

#define EL 10 
#define TEL 2*EL+1 
#define LEN sizeof(struct node) 
#include "stdio.h" 
#include "stdlib.h" 

char pre[TEL]="ABCDEFGHIJ"; 
char pin[TEL]="CBEDAGHFJI"; 

typedef struct node 
{ char data; 
struct node * lch,*rch; 
}BTNode,*BTree; 
BTNode root; 
BTree rt=&root; 

int pos(char c,char s[],int st) 
{char *p; 
p=s+st; 
while(*p!=c && *p!='\0') p++; 
return p-s; 
} 

void create(BTree *t,int i1,int i2,int len) 
{int r,llen,rlen; 
if(len<=0) *t=NULL; 
else 
{*t=(BTree)malloc(LEN); 
(*t)->data=pre[i1]; 
r=pos(pre[i1],pin,i2); 
llen=r-i2; 
rlen=len-(llen+1); 
create(&(*t)->lch,i1+1,i2,llen); 
create(&(*t)->rch,i1+llen+1,r+1,rlen); 
} 
} 

void travel(BTree t) 
{if(t) 
{travel(t->lch); 
travel(t->rch); 
putchar(t->data); 
} 
} 

int main() 
{create(&rt,0,0,EL); 
if(rt) travel(rt); 
} 
//方法二
＃i nclude<stdio.h>
＃i nclude<malloc.h>
＃i nclude<string.h>
typedef struct node
{
  char ch;
  struct node *left,*right;
}node;                   // 定义节点的结构 
node * creat(char *pre,char *in,int len);
void print(node *head);
int main()
{
  int i,j,k,m,n,len;
  char pre[30],in[30];    // 存储先序和中序遍历的序列 
  node *head;
  head=(node*)malloc(sizeof(node));
  while(scanf("%s%s",pre,in)!=EOF)
  { len=strlen(pre);
    head=creat(pre,in,len);
    print(head);
    printf("\n");
  }
  return 0;
}
node * creat(char *pre,char *in,int len)  // 创建后序遍历的函数 
{  int k;
   if(len<=0) return NULL;
   node *head=(node*)malloc(sizeof(node));
   head->ch=*pre;
   char *p;
   for(p=in;p!=NULL;p++) 
      if(*p==*pre) break;                 // 在中序遍历的序列中得到与先序相同的节点 
   k=p-in;
   head->left=creat(pre+1,in,k);          //递归调用得到左子树 
   head->right=creat(pre+k+1,p+1,len-k-1);//得到右子树 
   return head;
}
void print(node *head)  // 打印后序遍历序列 
{
  if(head==NULL) return ;
  print(head->left);
  print(head->right);
  printf("%c",head->ch);
}

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();
 }

}