ZBLOG

java创建一个二叉树,结点存放的是整型数据(可以有负数),遵循的规则是:第一个数值作为二叉树的树根,小于父节点的值放在左子节点,大于父节点的值放在右子节点。 在创建好二叉树的基础之上,进行结点统计和删除。 统计的内容包括:结点的个数;树的深度;度为0的点的个数;度为1的点的个数;度为2的点的个数。 删除的策略:如果删除结点是叶子结点,直接删除该点;如果删除结点只有一棵子树,子树的根结点直接替代该结点;如果删除结点同时有左子树和右子树,将右子树中的最小值点移动到删除点的位置上来替代删除结点...

下面是一个Java示例代码,实现了创建二叉树、节点统计和删除功能:

import java.util.*;

// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class BinaryTree {

    // 创建二叉树
    public static TreeNode createBinaryTree(List<Integer> values) {
        if (values == null || values.isEmpty()) {
            return null;
        }

        TreeNode root = new TreeNode(values.get(0));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        for (int i = 1; i < values.size(); i += 2) {
            TreeNode node = queue.poll();
            if (values.get(i) != null) {
                node.left = new TreeNode(values.get(i));
                queue.offer(node.left);
            }
            if (i + 1 < values.size() && values.get(i + 1) != null) {
                node.right = new TreeNode(values.get(i + 1));
                queue.offer(node.right);
            }
        }

        return root;
    }

    // 统计节点个数
    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return countNodes(root.left) + countNodes(root.right) + 1;
    }

    // 计算树的深度
    public static int calculateDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = calculateDepth(root.left);
        int rightDepth = calculateDepth(root.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    // 统计度为0、1、2的节点个数
    public static void countDegrees(TreeNode root, int[] counts) {
        if (root == null) {
            return;
        }

        if (root.left == null && root.right == null) {
            counts[0]++;
        } else if (root.left != null && root.right != null) {
            counts[2]++;
        } else {
            counts[1]++;
        }

        countDegrees(root.left, counts);
        countDegrees(root.right, counts);
    }

    // 删除指定值的节点
    public static TreeNode deleteNode(TreeNode root, int target) {
        if (root == null) {
            return null;
        }

        if (root.val < target) { // 目标值在右子树上
            root.right = deleteNode(root.right, target);
            return root;
        } else if (root.val > target) { // 目标值在左子树上
            root.left = deleteNode(root.left, target);
            return root;
        } else { // 找到目标节点
            if (root.left == null && root.right == null) { // 叶子节点直接删除
                return null;
            } else if (root.left != null && root.right != null) { // 左右子树都存在,找到右子树中最小值替代删除点位置
                TreeNode minNode = findMinNode(root.right);
                root.val = minNode.val;
                root.right = deleteNode(root.right, minNode.val);
                return root;
            } else { // 只有一棵子树,直接替代删除点位置
                return (root.left != null) ? root.left : root.right;
            }
        }
    }

    // 找到二叉搜索树中最小的节点
    public static TreeNode findMinNode(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    // 中序遍历二叉树
    public static void inOrderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left, result);
        result.add(root.val);
        inOrderTraversal(root.right, result);
    }

    // 层序遍历二叉树
    public static void layerOrderTraversal(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    public static void main(String[] args) {

      Scanner scanner=new Scanner(System.in);
      
      int n=scanner.nextInt();
      String valuesLine=scanner.next();
      int target=scanner.nextInt();

      List<Integer> values=new ArrayList<>();
      String[] valueStrs=valuesLine.split(",");
      
      for(int i=0;i<valueStrs.length;i++){
          values.add(Integer.parseInt(valueStrs[i]));
      }
      
        
       TreeNode root=createBinaryTree(values); 
       
       int nodeNumbers=countNodes(root);  
        
       int treeDepth=calculateDepth(root); 
        
       int[] counts={0,0,0}; 
       countDegrees(root,counts);

       TreeNode deleteResult=deleteNode(root,target); 
       
       List<Integer> inOrderBefore=new ArrayList<>();
       inOrderTraversal(root,inOrderBefore);
       
       List<Integer> layerOrderBefore=new ArrayList<>();
       layerOrderTraversal(root,layerOrderBefore);

       List<Integer> inOrderAfter=new ArrayList<>();
       if(deleteResult!=null)
          inOrderTraversal(deleteResult,inOrderAfter);
       
        List<Integer> layerOrderAfter=new ArrayList<>();
         if(deleteResult!=null)
             layerOrderTraversal(deleteResult,layerOrderAfter);

         
      System.out.println("NodeNumbers:"+nodeNumbers);
      System.out.println("TreeDepth:"+treeDepth);
      System.out.println("numbers_0:"+counts[0]);
      System.out.println("numbers_1:"+counts[1]);
      System.out.println("numbers_2:"+counts[2]);
      
      System.out.print("InOrder:");
      
      for(int i=0;i<inOrderBefore.size();i++){
          if(i==inOrderBefore.size()-1){
              System.out.print(inOrderBefore.get(i));
          }else{
              System.out.print(inOrderBefore.get(i)+",");
          }
      }
      
    	System.out.print("\nLayerOder:");
    	for(int i=0;i<layerOrderBefore.size();i++){
          if(i==layerOderBefor.size()-1){
              System.out.print(layerOderBefor.get(i));
          }else{
              System.out.print(layerOderBefor.get(i)+",");
          }
    	}
    	
    	  	System.out.print("\nInorder after:");

     		if(inOderAfet!=null) {
    			for (int i = 0; i < InoderAfet .size() ; i++) {
    				if(==inOderAfet.size()-1){
    					System. out.pritIn(inODerAfet get(i)) ;
    				}else{
    					System. out.pritIn(inODerAfet.get(i)+",");
    				}
    			}
    		}
    	
    System.out.print("\nLaye Order after:");
    	if(layerOrderAfter!=null){
    	    for(int i=0;i<layerOrderAfter.size();i++){
               if(i==layerOrderAfter.size()-1){
                System.out.print(layerOrderAfter.get(i));
              }else{
                System.out.print(layerOrderAfter.get(i)+",");
             }
        }
     }   
   }
}

希望这个示例能够帮助你理解如何创建二叉树,进行节点统计和删除操作。请注意,上述代码只是一个基本示例,可能需要根据实际情况进行适当调整和修改。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=15237

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?