Êý¾Ý½á¹¹±à³Ì£º ͳ¼Æ¶þ²æÊ÷ÖÐÒ¶×Ó½áµãµÄ¸öÊý¡£

ÀûÓÃjavaµÄ֪ʶ½øÐбà³Ì£ºÍ³¼Æ¶þ²æÊ÷ÖÐÒ¶×Ó½áµãµÄ¸öÊý¡£

ÇëÄÄλ¸ßÊÖÖ¸½ÌһϠ ÔÙ´ÎÏÈлÀ²£¡

Ò¶×ӽڵ㣺ûÓк¢×Ó½ÚµãµÄ½Úµã
Ò²¾ÍÊÇ˵£¬µ±ÎÒÃÇÃ÷°×ÁËÒ¶×Ó½ÚµãµÄ¶¨Òåºó£¬Ö»ÐèÒª±éÀúÒ»±é¶þ²æÊ÷£¬°Ñ·ûºÏÕâÖÖÌõ¼þ£¨×óº¢×Ó½ÚµãºÍÓÒº¢×ӽڵ㶼ΪNULLµÄ½Úµã£©µÄ½Úµãͳ¼Æ³öÀ´¾Í¿ÉÒÔÁË¡£
ÓÚÊÇ£¬Êµ¼ÊÉÏÕâ¸öÎÊÌâÒ²¾Íת»¯³ÉÁËÈçºÎ±éÀú¶þ²æÊ÷£¿ºÜÏÔÈ»£¬±éÀú¶þ²æÊ÷ÊÇ¿ÉÒÔÓжàÖÖ·½Ê½µÄ£¬È磺ǰÐò±éÀú£¨µÝ¹é/·ÇµÝ¹é£©¡¢ÖÐÐò±éÀú£¨µÝ¹é/·ÇµÝ¹é£©¡¢ºóÐò±éÀú£¨µÝ¹é/·ÇµÝ¹é£©¡¢²ã´Î±éÀúµÈµÈ¡£
ÏÂÃæÎÒ½«¸ø³öʹÓõݹéÇ°Ðò±éÀúÒÔ¼°²ã´Î±éÀúÁ½ÖÖ˼·ʵÏÖµÄÇó½âÒ¶×Ó½ÚµãµÄʾÀý´úÂë°É£¬½ö¹©²Î¿¼¡£ÆäËû¼¸ÖÖʵÏÖ·½Ê½Ë¼Â·ÀàËÆ£¬¿É×ÔÐг¢ÊÔ¡£Ê¾Àý´úÂëÈçÏ£º
package cn.zifangsky.tree.questions;

import org.junit.Test;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.tree.BinaryTreeNode;

/**
 * Çó¶þ²æÊ÷ÖÐÒ¶×Ó½ÚµãµÄ¸öÊý
 * @author Administrator
 *
 */
public class Question2 {

/**
 * ͨ¹ýµÝ¹éÇ°Ðò±éÀú»ñÈ¡Ò¶×Ó½Úµã¸öÊý
 * @param root
 * @return
 */
public int getNumberOfLeavesByPreOrder(BinaryTreeNode root){
  if(root == null){
   return 0;
  }else{
   if(root.getLeft() == null && root.getRight() == null){ //Ò¶×Ó½Úµã
    return 1;
   }else{
    return getNumberOfLeavesByPreOrder(root.getLeft()) + getNumberOfLeavesByPreOrder(root.getRight());
   }
  }

}


/**
 * ʹÓòã´Î±éÀú»ñÈ¡¶þ²æÊ÷Ò¶×Ó½Úµã¸öÊý
 * 
 * @ʱ¼ä¸´ÔӶȠO(n)
 * @param root
 */
public int getNumberOfLeavesByQueue(BinaryTreeNode root){
  int count = 0; //Ò¶×Ó½Úµã×ÜÊý
  LinkQueue queue = new LinkQueue();
  if(root != null){
   queue.enQueue(root);
  }

  while (!queue.isEmpty()) {
   BinaryTreeNode temp = (BinaryTreeNode) queue.deQueue();
   //Ò¶×ӽڵ㣺×óº¢×Ó½ÚµãºÍÓÒº¢×ӽڵ㶼ΪNULLµÄ½Úµã
   if(temp.getLeft() == null && temp.getRight() == null){
    count++;
   }else{
    if(temp.getLeft() != null){
     queue.enQueue(temp.getLeft());
    }
    if(temp.getRight() != null){
     queue.enQueue(temp.getRight());
    }
   }
  }
  return count;
}


/**
 * ²âÊÔÓÃÀý
 */
@Test
public void testMethods(){
  /**
  Â * ʹÓöÓÁй¹ÔìÒ»¸ö¹©²âÊÔʹÓõĶþ²æÊ÷
  Â *     1
  Â *   2    3
  Â * 4  5  6  7
  Â *   8 9  
  Â */
  LinkQueue queue = new LinkQueue();
  BinaryTreeNode root = new BinaryTreeNode(1); //¸ù½Úµã

  queue.enQueue(root);
  BinaryTreeNode temp = null;
  for(int i=2;i rearNode; //¶Óβ½Úµã

public LinkQueue() {
  frontNode = null;
  rearNode = null;
}

/**
 * ·µ»Ø¶ÓÁÐÊÇ·ñΪ¿Õ
 * @ʱ¼ä¸´ÔӶȠO(1)
 * @return
 */
public boolean isEmpty(){
  return (frontNode == null);
}

/**
 * ·µ»Ø´æ´¢ÔÚ¶ÓÁеÄÔªËظöÊý
 * @ʱ¼ä¸´ÔӶȠO(n)
 * @return
 */
public int size(){
  int length = 0;
  SinglyNode currentNode = frontNode;
  while (currentNode != null) {
   length++;
   currentNode = currentNode.getNext();
  }

  return length;
}

/**
 * Èë¶Ó£ºÔÚÁ´±í±íβ²åÈëÊý¾Ý
 * @ʱ¼ä¸´ÔӶȠO(1)
 * @param data
 */
public void enQueue(K data){
  SinglyNode newNode = new SinglyNode(data);

  if(rearNode != null){
   rearNode.setNext(newNode);
  }

  rearNode = newNode;

  if(frontNode == null){
   frontNode = rearNode;
  }
}

/**
 * ³ö¶Ó£ºÉ¾³ý±íÍ·½Úµã
 * @ʱ¼ä¸´ÔӶȠO(1)
 * @return
 */
public Object deQueue(){
  if(isEmpty()){
   throw new RuntimeException("Queue Empty!");
  }else{
   Object result = frontNode.getData();

   if(frontNode == rearNode){
    frontNode = null;
    rearNode = null;
   }else{
    frontNode = frontNode.getNext();
   }

   return result;
  }
}

}µ¥Á´±í½ÚµãSinglyNodeµÄ¶¨Ò壺
package cn.zifangsky.linkedlist;

/**
 * µ¥Á´±íµÄ¶¨Òå
 * @author zifangsky
 * @param 
 */
public class SinglyNode {
private K data; // Êý¾Ý
private SinglyNode next; // ¸Ã½ÚµãµÄϸö½Úµã

public SinglyNode(K data) {
  this.data = data;
}

public SinglyNode(K data, SinglyNode next) {
  this.data = data;
  this.next = next;
}

public K getData() {
  return data;
}

public void setData(K data) {
  this.data = data;
}

public SinglyNode getNext() {
  return next;
}

public void setNext(SinglyNode next) {
  this.next = next;
}

@Override
public String toString() {
  return "SinglyNode [data=" + data + "]";
}

}

public void getLeaves(){
  System.out.print("Ò¶×Ó½ÚµãΪ£º");
  getLeaves(root);

  }

private void getLeaves(BinaryNode p){
  if(p!=null)
  {
   if(p.left==null&&p.right==null){
    System.out.print(p.data.toString()+"");
    t++;

   }
   getLeaves(p.left);
   getLeaves(p.right);
  }
}
// ¹¹ÔìÒ»¿Ã¶þ²æÊ÷
public void getBinaryTree(String[] nodes) {
  this.root = (BinaryNode) getBinaryTreeByPreOrder(nodes);
}
private int i = 0;
private BinaryNode getBinaryTreeByPreOrder(String[] nodes) {
  BinaryNode node = null;
  if (i < nodes.length) {
   String tmp = nodes;
   i++;
   if (tmp != null) {
    node = new BinaryNode(tmp);
    // System.out.println("Í·½áµã"+node);
    node.left = (BinaryNode) getBinaryTreeByPreOrder(nodes);
    //System.out.println("×óº¢×Ó" + node.left);
    node.right = (BinaryNode) getBinaryTreeByPreOrder(nodes);
    //System.out.println("ÓÒº¢×Ó" + node.right);
   }
  }
  return node;
}
public static void main(String[] args) {
  String[] nodes = { "A", "B", "D", null, "G",null,null,null, "C","E", null,null, "F", "H",null,
    null, null };
  BinaryTree bt = new BinaryTree();
  bt.getBinaryTree(nodes);
bt.getLeaves();

Óöþ²æÊ÷±éÀúËã·¨¾Í¿ÉÒÔ×öµ½£¬Ò¶×Ó½ÚµãµÄÒâ˼¾ÍÊÇûÓÐ×Ó½Úµã¾Í±íʾÊÇÒ¶×ӽڵ㡣

¶þ²æÊ÷±éÀú·½±ãÒ»µã¿ÉÒÔÓõݹéËã·¨×öµ½¡£