你的位置:首页 > Java教程

[Java教程]求二叉树中第K层结点的个数


一,问题描述

构建一棵二叉树(不一定是二叉查找树),求出该二叉树中第K层中的结点个数(根结点为第0层)

 

二,二叉树的构建

定义一个BinaryTree类来表示二叉树,二叉树BinaryTree 又是由各个结点组成的,因此需要定义一个结点类BinaryNode,BinaryNode作为BinaryTree的内部类。

此外,在BinaryTree中需要一定一个BinaryNode属性来表示树的根结点。

 1 public class BinaryTree<T extends Comparable<? super T>> { 2    3   private static class BinaryNode<T>{ 4     T element; 5     BinaryNode<T> left; 6     BinaryNode<T> right; 7      8     public BinaryNode(T element) { 9       this.element = element;10       left = right = null;11     }12   13     public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right){14       this.element = element;15       this.left = left;16       this.right = right;17     }18   }19   20   private BinaryNode<T> root;21 22 //other code.....

第一行是二叉树类的定义,第三行是结点类的定义,第20行是二叉树根的定义。

 

三,求解第K层结点个数的算法实现

感觉对二叉树中的许多操作都可以用递归来实现。因此,二叉树是理解递归一个好实例。比如,二叉树的操作之统计二叉树中节点的个数 和 二叉树的先序遍历和后序遍历的应用--输出文件和统计目录大小

求第K层结点的个数也可以用递归来实现:

①若二叉树为空或者K小于0,返回0

②若K等于0,第0层就是树根,根只有一个,返回1

③若K大于0,返回左子树中第K-1层结点个数 加上 右子树中第K-1层结点的个数

因为,第K层结点,相对于根的左子树 和 右子树 而言,就是第K-1层结点

 

四,代码实现

 1 public class BinaryTree<T extends Comparable<? super T>> { 2    3   private static class BinaryNode<T>{ 4     T element; 5     BinaryNode<T> left; 6     BinaryNode<T> right; 7      8     public BinaryNode(T element) { 9       this.element = element;10       left = right = null;11     }12   }13   14   private BinaryNode<T> root;15   16   /**17    * 向二叉树中插入一个元素18    * @param element19   */20   public void insert(T element){21     root = insert(root, element);22   }23   private BinaryNode<T> insert(BinaryNode<T> root, T element){24     if(root == null)25       return new BinaryNode<T>(element);26     int r = (int)(2*Math.random());27     //随机地将元素插入到左子树 或者 右子树中28     if(r==0)29       root.left = insert(root.left, element);30     else31       root.right = insert(root.right, element);32     return root;33   }34   35   /**36    * 37    * @param k38    * @return 二叉树中第K层结点的个数(根位于第0层)39   */40   public int k_nodes(int k){41     return k_nodes(root, k);42   }43   private int k_nodes(BinaryNode<T> root, int k){44     if(root == null || k < 0)45       return 0;46     if(k == 0)47       return 1;//根结点48     else49       return k_nodes(root.left, k-1) + k_nodes(root.right, k-1);50   }51   52   public static void main(String[] args) {53     BinaryTree<Integer> tree = new BinaryTree<>();54     55     int[] ele = C2_2_8.algorithm1(4);//构造一个随机数组,数组元素的范围为[1,4]56     for (int i = 0; i < ele.length; i++) {57       tree.insert(ele[i]);58     }59     60     int k_nodes = tree.k_nodes(2);//第二层61     int k_nodes2 = tree.k_nodes(-1);//第-1层62     int k_nodes3 = tree.k_nodes(0);63     int k_nodes4 = tree.k_nodes(1);64     int k_nodes5 = tree.k_nodes(4);//若超过了树的高度,结果为065     System.out.println(k_nodes);66     System.out.println(k_nodes2);67     System.out.println(k_nodes3);68     System.out.println(k_nodes4);69     System.out.println(k_nodes5);70   }71 }

 

关于 C2_2_8类,参考:随机序列生成算法---生成前N个整数的一组随机序列

 

五,参考资料

http://blog.csdn.net/luckyxiaoqiang/article/details/7518888