二叉树叶子结点计数-蒲公英云

一、问题描述

实现输入二叉树，输出叶子结点个数。

二、数据结构设计

由于输入的二叉树是字符串形式，首先需要由输入的标明空子树的先根遍历序列创建一棵二叉树，创建二叉树过程中需要创建二叉链表存储结构来实现创建二叉树的操作，创建二叉链表需要结点类，我定义的结点有：空结点、两个孩子的结点为空的结点、不为空结点，该结点类定义如下：

public classBiTreeNode

{

publicObject data; //结点的数据域

publicBiTreeNode lchild,rchild; //左右孩子域

}

我定义的二叉链表的方法为BiTree,该结构定义如下：

public classBiTree //创建二叉树与实现二叉树遍历

{

public BiTreeNode root; //树的根节点

}

三、算法设计

对标明空子树的先根遍历序列字符串输入，然后需要创建一棵二叉树，创建完成后需要创建并调用求叶子结点个数的方法，求出叶子结点数，方法定义如下：

1、创建空结点方法：

（1）创建空结点的目的是：二叉链表中含有空结点，需要通过空结点统计叶子结点个数。

（2）方法定义：

public BiTreeNode(){

this(null);

}

2、创建两个孩子为空结点方法：

（1）创建空结点的目的是：二叉链表中含有两个孩子结点为空的结点，需要通过此结点创建二叉树。

（2）方法定义如下：

public BiTreeNode(Objectdata){

this(data,null,null);

}

3、创建不为空结点方法：

（1）创建空结点的目的是：二叉链表中含有不为空结点，需要通过此结点创建二叉树。

（2）方法定义：

public BiTreeNode(Objectdata,BiTreeNode lchild,BiTreeNode rchild){

this.data = data;

this.lchild = lchild;

this.rchild = rchild;

}

4、使用get、set方法获取根结点：

（1）获取根结点的目的是：通过获取根结点将其作为参数传入求叶子节点个数的方法中

（2）方法定义如下：

public BiTreeNodegetRoot(){

return root;

}

public voidsetRoot(BiTreeNode root){

this.root = root;

}

5、建立二叉树方法：

（1）建立二叉树目的：建立二叉树可以通过先根遍历的内容，将字符串创建成为一个二叉树，以此达到求取叶子结点的目的。

（2）方法定义：

private static int index =0;

public BiTree(StringpreStr){

char c = preStr.charAt(index++);

if(c!=’#‘){

root = newBiTreeNode(c);

root.lchild = new BiTree(preStr).root;

root.rchild = new BiTree(preStr).root;

}

else

root = null;

}

6、求叶子结点个数的方法：

（1）方法定义如下：

public intcountleafNode(BiTreeNode T){

int count = 0;

if(T != null){

if(T.lchild==null&&T.rchild==null){

count++;

}else{

count+=countleafNode(T.lchild);

count+=countleafNode(T.rchild);

}

return count;

}

四、测试及结果

输入的是具有三个叶子结点的二叉树，输出结果如下：

![Image 1][]

五、调试情况总结

1、我在此次实训中感觉自己学习很多东西都不灵活，采用方法时对各种方法并没有区分，尤其是遇到没有用的方法时，自己不会采取措施解决，总是写一些多于的、不使用的方法，导致中途出现很多问题。

2、方法的调用方面：调用方法时使用的方法名相同。自己写了一个含有同一名字的方法名，参数个数也相同，但是实际调用时，编译器会直接识别第一个。

附1：源程序清单

1、使用的类：

BiTreeNode.java

BiTree.java

Main.java

2、程序如下：

package ch01;
        public class BiTreeNode{
            public Object data;  //结点的数据域
            public BiTreeNode lchild,rchild;  //左右孩子域
            //创造一个空节点
            public BiTreeNode(){
                this(null);
            }
            //创建一个左右域为空的二叉树
            public BiTreeNode(Object data){
                this(data,null,null);
            }
            //创建一个数据域与左右孩子都不为空的结点
            public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild){
                this.data = data;
                this.lchild = lchild;
                this.rchild = rchild;
            }
        }
package ch01;
        public class BiTree{   //创建二叉树与实现二叉树遍历
            public BiTreeNode root;   //树的根节点
            //get方法
            public BiTreeNode getRoot(){
                return root;
            }
            //set方法
            public void setRoot(BiTreeNode root){
                this.root = root;
            }
            private static int index = 0;    
            //由标明空子树的先根遍历序列建立一个二叉树
            public BiTree(String preStr){
                char c = preStr.charAt(index++);
                if(c!='#'){
                    root = new BiTreeNode(c);
                    root.lchild = new BiTree(preStr).root;
                    root.rchild = new BiTree(preStr).root;
                }else
                    root = null;
            }
            //统计二叉树中叶子结点个数
            public int countleafNode(BiTreeNode T){
                int count = 0;
                if(T != null){
                    if(T.lchild==null&&T.rchild==null){
                        count++;
                    }else
                    {
                        count+=countleafNode(T.lchild);
                        count+=countleafNode(T.rchild);
                    }
                }
                return count;
            }    
        }
package ch01;
        import ch01.BiTree;
        import java.util.Scanner;
        public class Main {//实现输入二叉树，输出叶子结点个数
            public static void main(String []args){
                System.out.println("请输入一个标明空子树的先根遍历序列：");
                Scanner sc = new Scanner(System.in);
                String preStr =sc.nextLine();
                BiTree bitree= new BiTree(preStr);
                System.out.println(bitree.countleafNode(bitree.root));
            }
        }