你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

7-1 求二叉树的叶子结点个数 (10 分)java版

2021-11-20 12:04:07

以二叉链表作为二叉树的存储结构,求二叉树的叶子结点个数。

输入格式:
输入二叉树的先序序列。
提示:一棵二叉树的先序序列是一个字符串,若字符是‘#’,表示该二叉树是空树,否则该字符是相应结点的数据元素。

输出格式:
输出有两行:
第一行是二叉树的中序遍历序列;
第二行是二叉树的叶子结点个数。

输入样例:

ABC##DE#G##F###

输出样例:

CBEGDFA
3
import java.util.Scanner;

class Tree {
    char data;
    Tree left;
    Tree right;


    public Tree(char data) {
        this(data, null, null);
    }

    public Tree(char data, Tree left, Tree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

}

public class Main {
    static int count = 0;
    static int sum = 0;

    public static void main(String arg[]) {
        Scanner sc = new Scanner(System.in);
        Pre_tra(create(sc.nextLine()));
        System.out.println("\n" + sum);
    }

    public static void Pre_tra(Tree root) {
        if (root != null) {
            if (root.left == null && root.right == null) {
                sum++;
            }
            Pre_tra(root.left);
            System.out.print(root.data);
            Pre_tra(root.right);
        }
    }

    //以先序序列建立二叉树
    public static Tree create(String str) {
        Tree root = null;
        char c = str.charAt(count);
        if (c != '#') {
            root = new Tree(c);
            count++;
            root.left = create(str);
            count++;
            root.right = create(str);
        }
        return root;
    }
}