数据结构编程： 统计二叉树中叶子结点的个数。

叶子节点：没有孩子节点的节点

也就是说，当我们明白了叶子节点的定义后，只需要遍戚兄历一遍二叉树，把符合这种条件（左孩子节点和右孩子节点都为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<10;i=i+2){
			BinaryTreeNode tmpNode1 = new BinaryTreeNode(i);
			BinaryTreeNode tmpNode2 = new BinaryTreeNode(i+1);
			
			temp = (BinaryTreeNode) queue.deQueue();
			
			temp.setLeft(tmpNode1);
			temp.setRight(tmpNode2);
			
			if(i != 4)
				queue.enQueue(tmpNode1);
			queue.enQueue(tmpNode2);
		}

		System.out.println("叶子节点个数是：" + getNumberOfLeavesByPreOrder(root));
		System.out.println("叶子节点个数是：" + getNumberOfLeavesByQueue(root));
		
	}

}

测试代码输出如下：

叶子节点个数是：5
叶子节点个数是：5

附：

二叉树节点BinaryTreeNode的定义：

package cn.zifangsky.tree;

public class BinaryTreeNode {
	private int data; // 数据
	private BinaryTreeNode left; //左孩子节点
	private BinaryTreeNode right; //右孩子节点
	
	public BinaryTreeNode(int data) {
		this.data = data;
	}

	public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public int getData() {
		return data;
	}

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

	public BinaryTreeNode getLeft() {
		return left;
	}

	public void setLeft(BinaryTreeNode left) {
		this.left = left;
	}

	public BinaryTreeNode getRight() {
		return right;
	}

	public void setRight(BinaryTreeNode right) {
		this.right = right;
	}
	
}

队列LinkQueue的定义：

package cn.zifangsky.queue;

import cn.zifangsky.linkedlist.SinglyNode;

/**
 * 基于单链表实现的队列
 * @author zifangsky
 * @param 
 */
public class LinkQueue{
	private SinglyNode frontNode; //队首节点
	private SinglyNode 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];
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();

用二叉树遍历算法就可以做到，叶轿芦子节点的意思就是没有子节点就表简铅示是叶子节点。

二叉树遍历方便一点可以拦帆好用递归算法做到。