论坛 › Java语言交流 › 数据结构

zsxxn 发表于 2023-11-12 17:41:27

数据结构

Java编程泛型类BinaryTree（二叉树），BinaryTree的基本功能设计要求：构建二叉树、前序遍历、中序遍历、后序遍历、层序遍历、获取总结点个数、获取叶子结点个数、获取第n层结点个数、获取二叉树的深度、插入指定元素结点、删除指定元素结点、查找指定元素结点。

isdkz 发表于 2023-11-12 17:41:49

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<T> {
    private TreeNode<T> root;

    // 构建二叉树
    public void buildTree(T[] values) {
      if (values == null || values.length == 0) {
            return;
      }
      root = buildTree(values, 0);
    }

    private TreeNode<T> buildTree(T[] values, int index) {
      if (index < values.length) {
            TreeNode<T> node = new TreeNode<>(values);
            node.left = buildTree(values, 2 * index + 1);
            node.right = buildTree(values, 2 * index + 2);
            return node;
      }
      return null;
    }

    // 前序遍历
    public void preOrderTraversal() {
      preOrderTraversal(root);
    }

    private void preOrderTraversal(TreeNode<T> node) {
      if (node != null) {
            System.out.print(node.value + " ");
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
      }
    }

    // 中序遍历
    public void inOrderTraversal() {
      inOrderTraversal(root);
    }

    private void inOrderTraversal(TreeNode<T> node) {
      if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.value + " ");
            inOrderTraversal(node.right);
      }
    }

    // 后序遍历
    public void postOrderTraversal() {
      postOrderTraversal(root);
    }

    private void postOrderTraversal(TreeNode<T> node) {
      if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.print(node.value + " ");
      }
    }

    // 层序遍历
    public void levelOrderTraversal() {
      if (root == null) {
            return;
      }
      Queue<TreeNode<T>> queue = new LinkedList<>();
      queue.offer(root);
      while (!queue.isEmpty()) {
            TreeNode<T> node = queue.poll();
            System.out.print(node.value + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
      }
    }

    // 获取总结点个数
    public int getNodeCount() {
      return getNodeCount(root);
    }

    private int getNodeCount(TreeNode<T> node) {
      if (node == null) {
            return 0;
      }
      return 1 + getNodeCount(node.left) + getNodeCount(node.right);
    }

    // 获取叶子结点个数
    public int getLeafNodeCount() {
      return getLeafNodeCount(root);
    }

    private int getLeafNodeCount(TreeNode<T> node) {
      if (node == null) {
            return 0;
      }
      if (node.left == null && node.right == null) {
            return 1;
      }
      return getLeafNodeCount(node.left) + getLeafNodeCount(node.right);
    }

    // 获取第n层结点个数
    public int getNodeCountAtLevel(int level) {
      return getNodeCountAtLevel(root, level);
    }

    private int getNodeCountAtLevel(TreeNode<T> node, int level) {
      if (node == null || level < 1) {
            return 0;
      }
      if (level == 1) {
            return 1;
      }
      return getNodeCountAtLevel(node.left, level - 1) + getNodeCountAtLevel(node.right, level - 1);
    }

    // 获取二叉树的深度
    public int getDepth() {
      return getDepth(root);
    }

    private int getDepth(TreeNode<T> node) {
      if (node == null) {
            return 0;
      }
      int leftDepth = getDepth(node.left);
      int rightDepth = getDepth(node.right);
      return 1 + Math.max(leftDepth, rightDepth);
    }

    // 插入指定元素结点
    public void insertNode(T value) {
      if (root == null) {
            root = new TreeNode<>(value);
      } else {
            insertNode(root, value);
      }
    }

    private void insertNode(TreeNode<T> node, T value) {
      if (node.left == null) {
            node.left = new TreeNode<>(value);
      } else if (node.right == null) {
            node.right = new TreeNode<>(value);
      } else {
            insertNode(node.left, value);
      }
    }

    // 删除指定元素结点
    public void deleteNode(T value) {
      if (root == null) {
            return;
      }
      if (root.value.equals(value)) {
            root = null;
      } else {
            deleteNode(root, value);
      }
    }

    private void deleteNode(TreeNode<T> node, T value) {
      if (node == null) {
            return;
      }
      if (node.left != null && node.left.value.equals(value)) {
            node.left = null;
      } else if (node.right != null && node.right.value.equals(value)) {
            node.right = null;
      } else {
            deleteNode(node.left, value);
            deleteNode(node.right, value);
      }
    }

    // 查找指定元素结点
    public boolean searchNode(T value) {
      return searchNode(root, value);
    }

    private boolean searchNode(TreeNode<T> node, T value) {
      if (node == null) {
            return false;
      }
      if (node.value.equals(value)) {
            return true;
      }
      return searchNode(node.left, value) || searchNode(node.right, value);
    }

    private static class TreeNode<T> {
      T value;
      TreeNode<T> left;
      TreeNode<T> right;

      TreeNode(T value) {
            this.value = value;
            this.left = null;
            this.right = null;
      }
    }
}

Mike_python小 发表于 2023-11-12 17:42:42

java
import java.util.LinkedList;
import java.util.Queue;

public class TreeNode<T> {
    T val;
    TreeNode<T> left;
    TreeNode<T> right;

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

public class BinaryTree<T> {
    private TreeNode<T> root;

    public void insert(T value) {
      if (root == null) {
            root = new TreeNode<>(value);
      } else {
            insert(root, value);
      }
    }

    private void insert(TreeNode<T> node, T value) {
      Queue<TreeNode<T>> queue = new LinkedList<>();
      queue.add(node);
      
      while (!queue.isEmpty()) {
            TreeNode<T> current = queue.poll();
            if (current.left == null) {
                current.left = new TreeNode<>(value);
                break;
            } else {
                queue.add(current.left);
            }
            
            if (current.right == null) {
                current.right = new TreeNode<>(value);
                break;
            } else {
                queue.add(current.right);
            }
      }
    }

    public void delete(T value) {
      // 实现删除指定元素结点的逻辑
    }

    public TreeNode<T> find(T value) {
      return find(root, value);
    }

    private TreeNode<T> find(TreeNode<T> node, T value) {
      if (node == null || node.val.equals(value)) {
            return node;
      }
      
      TreeNode<T> left = find(node.left, value);
      if (left != null) {
            return left;
      }
      
      TreeNode<T> right = find(node.right, value);
      return right;
    }

    // 其他方法实现略...

    // 获取总结点个数
    public int getNodeCount() {
      return getNodeCount(root);
    }

    private int getNodeCount(TreeNode<T> node) {
      if (node == null) {
            return 0;
      }
      return 1 + getNodeCount(node.left) + getNodeCount(node.right);
    }

    // 获取叶子结点个数
    public int getLeafNodeCount() {
      return getLeafNodeCount(root);
    }

    private int getLeafNodeCount(TreeNode<T> node) {
      if (node == null) {
            return 0;
      }
      if (node.left == null && node.right == null) {
            return 1;
      }
      return getLeafNodeCount(node.left) + getLeafNodeCount(node.right);
    }

    // 获取第n层结点个数
    public int getNodeCountAtLevel(int level) {
      return getNodeCountAtLevel(root, level);
    }

    private int getNodeCountAtLevel(TreeNode<T> node, int level) {
      if (node == null || level < 1) {
            return 0;
      }
      if (level == 1) {
            return 1;
      }
      return getNodeCountAtLevel(node.left, level - 1) + getNodeCountAtLevel(node.right, level - 1);
    }

    // 获取二叉树的深度
    public int getDepth() {
      return getDepth(root);
    }

    private int getDepth(TreeNode<T> node) {
      if (node == null) {
            return 0;
      }
      int leftDepth = getDepth(node.left);
      int rightDepth = getDepth(node.right);
      return Math.max(leftDepth, rightDepth) + 1;
    }

    // 前序遍历
    public void preOrderTraversal() {
      preOrderTraversal(root);
      System.out.println(); // 换行
    }

    private void preOrderTraversal(TreeNode<T> node) {
      if (node != null) {
            System.out.print(node.val + " ");
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
      }
    }

    // 中序遍历
    public void inOrderTraversal() {
      inOrderTraversal(root);
      System.out.println(); // 换行
    }

    private void inOrderTraversal(TreeNode<T> node) {
      if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.val + " ");
            inOrderTraversal(node.right);
      }
    }

    // 后序遍历
    public void postOrderTraversal() {
      postOrderTraversal(root);
      System.out.println(); // 换行
    }

    private void postOrderTraversal(TreeNode<T> node) {
      if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.print(node.val + " ");
      }
    }

    // 层序遍历
    public void levelOrderTraversal() {
      Queue<TreeNode<T>> queue = new LinkedList<>();
      if (root != null) {
            queue.add(root);
      }

      while (!queue.isEmpty()) {
            TreeNode<T> node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
      }
      System.out.println(); // 换行
    }
}


这个BinaryTree类实现了二叉树的基本功能，包括构建二叉树、前序遍历、中序遍历、后序遍历、层序遍历、获取总结点个数、获取叶子结点个数、获取第n层结点个数、获取二叉树的深度、插入指定元素结点、删除指定元素结点、查找指定元素结点等。希望这个例子能够帮助你完成Java编程中泛型类BinaryTree的基本功能设计。

liuhongrun2022 发表于 2023-11-12 20:09:49

在Java中，实现一个二叉树类（BinaryTree）需要定义一个内部类（TreeNode）来表示树的节点。每个TreeNode对象有一个元素以及两个指向子节点的引用（左子节点和右子节点）。以下是一个基本的实现，包含了包含了构建二叉树、前序遍历、中序遍历、后序遍历、层序遍历、获取总结点个数、获取叶子结点个数、获取第n层结点个数、获取二叉树的深度、插入指定元素结点、删除指定元素结点和查找指定元素结点的功能。

import java.util.*;

public class BinaryTree<T> {
    private TreeNode<T> root;

    private static class TreeNode<T> {
      T data;
      TreeNode<T> left;
      TreeNode<T> right;

      TreeNode(T data) {
            this.data = data;
      }
    }

    public BinaryTree() {
      root = null;
    }

    // 根据需要自行实现构建二叉树的方法，例如通过数组构建

    // 前序遍历
    public void preOrderTraversal(TreeNode<T> node) {
      if (node == null) return;
      System.out.println(node.data);
      preOrderTraversal(node.left);
      preOrderTraversal(node.right);
    }

    // 中序遍历
    public void inOrderTraversal(TreeNode<T> node) {
      if (node == null) return;
      inOrderTraversal(node.left);
      System.out.println(node.data);
      inOrderTraversal(node.right);
    }

    // 后序遍历
    public void postOrderTraversal(TreeNode<T> node) {
      if (node == null) return;
      postOrderTraversal(node.left);
      postOrderTraversal(node.right);
      System.out.println(node.data);
    }

    // 层序遍历
    public void levelOrderTraversal(TreeNode<T> node) {
      Queue<TreeNode<T>> queue = new LinkedList<>();
      queue.add(node);

      while(!queue.isEmpty()) {
            TreeNode<T> curr = queue.poll();
            System.out.println(curr.data);

            if(curr.left != null) queue.add(curr.left);
            if(curr.right != null) queue.add(curr.right);
      }
    }

    // 获取总节点个数
    // 获取叶子节点个数
    // 获取第n层节点个数
    // 获取二叉树的深度
    // 插入指定元素节点
    // 删除指定元素节点
    // 查找指定元素节点
    // 以上功能根据需要自行实现
}


本示例只包含了基本的遍历功能，其它的功能如获取总节点个数、获取叶子节点个数、获取第n层节点个数、获取二叉树的深度、插入指定元素节点、删除指定元素节点和查找指定元素节点需要你根据具体需求进行实现。

查看完整版本: 数据结构