首页 > 代码库 > 构造二叉树，并求解树的高度
构造二叉树，并求解树的高度
一，问题描述
在控制台上输入一组数据，请按照输入的数据的格式来构造一棵二叉树，并打印出二叉树的高度。
输入的数据格式如下：
第一行为一个整数N(其实是二叉树中边的数目)，表示接下来一共有N行输入，每行输入有两个数，左边的数表示父结点，右边的数表示父结点的孩子结点。示例如下：
6
0 1
0 2
1 3
2 4
2 5
4 6
从上面的输入可以看出：①根结点0 的左孩子为1，右孩子为2 。②结点1 只有一个孩子，即左孩子3
二，问题分析
问题的关键是根据上面的输入数据 构造一棵二叉树。
首先用一个Map<Integer, List<Integer>>保存上面的输入的数据。其中Key为父结点，Value为父结点的孩子结点。对于二叉树而言，父结点的孩子结点最多只有2个，故List长度最大为2.
然后，根据Map来构造二叉树即可。
对于Map中的每一个Entry，Entry的Key为父结点，找到父结点在树中的位置(findNode方法)。
Entry的Value为父结点的左右孩子，遍历Value，构造孩子结点。已知了父结点在树中的位置，又构造了孩子结点，只需要将父结点的左右指针指向左右孩子即可。
三，代码实现
import java.util.ArrayList;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;import java.util.Map.Entry;import java.util.Scanner;import java.util.Set;//按要求构造二叉树,假设头结点为0public class BuildTree { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //<parent, childList> Map<Integer, List<Integer>> datas = new LinkedHashMap<Integer, List<Integer>>(); while(sc.hasNextInt()) { int edges = sc.nextInt(); //将树的信息保存到hashmap<parent, childList>中 for(int i = 0; i < edges; i++) { int parent = sc.nextInt(); int child = sc.nextInt(); if(!datas.containsKey(parent)){ List<Integer> childs = new ArrayList<Integer>(); childs.add(child); datas.put(parent, childs); }else{ List<Integer> childs = datas.get(parent); childs.add(child); } }//end for BinaryNode root = buildTree(datas); int height = height(root); System.out.println(height); } sc.close(); } //求二叉树的高度 private static int height(BinaryNode root){ if(root == null) return 0; int leftHeight = height(root.left); int rightHeight = height(root.right); return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); } //构造二叉树 private static BinaryNode buildTree(Map<Integer, List<Integer>> datas){ BinaryNode root = null; BinaryNode current = null; List<Integer> childs = null; Set<Entry<Integer, List<Integer>>> entrySet = datas.entrySet(); for (Entry<Integer, List<Integer>> entry : entrySet) { int parent = entry.getKey(); current = findNode(parent, root); childs = datas.get(parent); if(current == null){//说明parent是根结点 root = new BinaryNode(parent); createNode(root, childs); }else{ createNode(current, childs); } } return root; } //创建parent结点的左右孩子结点 private static void createNode(BinaryNode parent, List<Integer> childs){ if(childs.size() == 2){//说明有左右孩子 BinaryNode leftChild = new BinaryNode(childs.get(0)); BinaryNode rightChild = new BinaryNode(childs.get(1)); parent.left = leftChild; parent.right = rightChild; } if(childs.size() == 1){//说明只有左孩子 BinaryNode leftChild = new BinaryNode(childs.get(0)); parent.left = leftChild; } } //查找树根为root的二叉树中 值为 nodeVal 的结点 private static BinaryNode findNode(int nodeVal, BinaryNode root){ //先序递归遍历查找 值为 nodeVal的结点 BinaryNode target = null; if(root == null) return null; if(root.val == nodeVal) return root; target = findNode(nodeVal, root.left);//先在左子树中查找 if(target == null) target = findNode(nodeVal, root.right);//左子树中未找到,则在右子树中查找 return target; } private static class BinaryNode{ int val; BinaryNode left; BinaryNode right; public BinaryNode(int val){ this.val = val; left = right = null; } }}
复杂度分析：由于 当构造父结点的左右孩子时，需要先查找父结点在二叉树中的位置，这个查找是用“先序遍历的思路”实现的。
故构造树的时间复杂度为O(1+2+3+……+N)=O(N^2)。有点大。
参考资料：二叉树的构造
构造二叉树，并求解树的高度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。