二叉树学习

mac2024-01-29  38

package com.aic.jon.bst; public class BST<E extends Comparable<E>> { //Comparable接口,方便元素进行比较 private Node root; //根节点 private int size; //元素数量 private class Node { public E e; public Node left, right; //左节点,右节点 public Node(E e) { //构造方法,将左右节点赋值Null this.e = e; left = null; right = null; } } public BST() { root = null; size = 0; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void add(E e) { root = add(root, e); } //向以node为根的二分搜索树插入元素e,递归算法 //返回插入新节点后的树根 private Node add(Node node, E e) { if (node == null) { size++; return new Node(e); } if (e.compareTo(node.e) < 0) { node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { node.right = add(node.right, e); } return node; } public boolean contains(E e) { return contains(root, e); } //通过递归算法实现搜索 private boolean contains(Node node, E e) { if (node == null) { return false; } if (e.compareTo(node.e) == 0) { return true; } else if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else { return contains(node.right, e); } } //前序遍历 public void preOrder(){ preOrder(root); } private void preOrder(Node node) { if(node == null){ //递归时就不用担心node为空了 return; } System.out.println(node.e); preOrder(node.left); //先左子树 preOrder(node.right); //后右子树 } @Override public String toString() { StringBuilder res = new StringBuilder(); //StringBuilder用于动态改变字符串时使用,线程不安全 generateBSTString(root, 0, res); return res.toString(); } // 生成以node为根节点,深度为depth的描述二叉树的字符串 private void generateBSTString(Node node, int depth, StringBuilder res) { if (node == null) { res.append(generateDepthString(depth) + "null\n"); return; } res.append(generateDepthString(depth) + node.e + "\n"); generateBSTString(node.left, depth + 1, res); generateBSTString(node.right, depth + 1, res); } private String generateDepthString(int depth) { StringBuilder res = new StringBuilder(); for (int i = 0; i < depth; i++) res.append("--"); return res.toString(); } }
最新回复(0)