Question

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

利用java的知识进行编程：统计二叉树中叶子结点的个数。

请哪位高手指教一下 再次先谢啦！

Answer 1

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

也就是说，当我们明白了叶子节点的定义后，只需要遍历一遍二叉树，把符合这种条件（左孩子节点和右孩子节点都为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<BinaryTreeNode> 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<BinaryTreeNode> queue = new LinkQueue<BinaryTreeNode>();
		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 <K>
 */
public class LinkQueue<K extends Object>{
	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<K> newNode = new SinglyNode<K>(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 <K>
 */
public class SinglyNode<K extends Object> {
	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 + "]";
	}

}

Answer 2

public void getLeaves(){
System.out.print("叶子节点为：");
getLeaves(root);

}

private void getLeaves(BinaryNode<T> 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<T>) getBinaryTreeByPreOrder(nodes);
}
private int i = 0;
private BinaryNode<String> getBinaryTreeByPreOrder(String[] nodes) {
BinaryNode<String> node = null;
if (i < nodes.length) {
String tmp = nodes[i];
i++;
if (tmp != null) {
node = new BinaryNode<String>(tmp);
// System.out.println("头结点"+node);
node.left = (BinaryNode<String>) getBinaryTreeByPreOrder(nodes);
//System.out.println("左孩子" + node.left);
node.right = (BinaryNode<String>) 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<String>();
bt.getBinaryTree(nodes);
bt.getLeaves();

Answer 3

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

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