java--二叉树常见操作

二叉树节点定义

public class BinaryNode<T> {

/**
 * 左节点
 */
private BinaryNode<T> leftNode;
/**
 * 右节点
 */
private BinaryNode<T> rightNode;
/**
 * 节点数据
 */
private T data;
public BinaryNode(T data) {
this.data = data;
    }
public BinaryNode<T> getLeftNode() {
return leftNode;
    }

public void setLeftNode(BinaryNode<T> leftNode) {
this.leftNode = leftNode;
    }

public BinaryNode<T> getRightNode() {
return rightNode;
    }

public void setRightNode(BinaryNode<T> rightNode) {
this.rightNode = rightNode;
    }

public T getData() {
return data;
    }
public void setData(T data) {
this.data = data;
    }
}

常见操作

public class Test {

/**
 * @title 获取二叉树节点数量（递归）
 */
public static <T> int getNodes(BinaryNode<T> rootNode){
if (rootNode == null) {
return 0;
        }else {
return 1 + getNodes(rootNode.getLeftNode()) + getNodes(rootNode.getRightNode());
        }
    }
/**
 * @title 获取二叉树深度（递归）
 */
public static <T> int getDepth(BinaryNode<T> rootNode){
if (rootNode == null) {
return 0;
        }else {
int left = getDepth(rootNode.getLeftNode());
int right = getDepth(rootNode.getRightNode());
return left > right ? left + 1 : right + 1;
        }
    }
/**
 * @title 前序遍历二叉树（递归）（遍历顺序：根节点、左节点、右节点）
 */
public static <T> void frontTraverse(BinaryNode<T> rootNode){
if (rootNode == null) {
return;
        }else {
            System.out.print(rootNode.getData());
            frontTraverse(rootNode.getLeftNode());
            frontTraverse(rootNode.getRightNode());
        }

    }
/**
 * @title 中序遍历二叉树（递归）（遍历顺序：左节点、根节点、右节点）
 */
public static <T> void midTraverse(BinaryNode<T> rootNode){
if (rootNode == null) {
return;
        }else {
            midTraverse(rootNode.getLeftNode());
            System.out.print(rootNode.getData());
            midTraverse(rootNode.getRightNode());
        }
    }
/**
 * @title 后续遍历二叉树（递归）（遍历顺序：左节点、右节点、根节点）
 */
public static <T> void afterTraverse(BinaryNode<T> rootNode){
if (rootNode == null) {
return;
        }else {
            afterTraverse(rootNode.getLeftNode());
            afterTraverse(rootNode.getRightNode());
            System.out.print(rootNode.getData());
        }
    }
/**
 * @title 层次遍历二叉树（从上往下，从左往右）
 */
public static <T> void levelTraverse(BinaryNode<T> rootNode){
if (rootNode == null) {
return;
        }
        Queue<BinaryNode<T>> queue = new LinkedBlockingDeque<>();
        queue.offer(rootNode);
while(!queue.isEmpty()){
            BinaryNode<T> curNode = queue.poll();
            System.out.print(curNode.getData());
if (curNode.getLeftNode() != null) {
                queue.offer(curNode.getLeftNode());
            }
if (curNode.getRightNode() != null) {
                queue.offer(curNode.getRightNode());
            }
        }
    }
public static void main(String[] args) {
        BinaryNode<Integer> root = new BinaryNode<Integer>(1);
        BinaryNode<Integer> left = new BinaryNode<Integer>(2);
        BinaryNode<Integer> right = new BinaryNode<Integer>(3);
        root.setLeftNode(left);
        root.setRightNode(right);
        BinaryNode<Integer> left1 = new BinaryNode<Integer>(4);
        BinaryNode<Integer> right1 = new BinaryNode<Integer>(5);
        BinaryNode<Integer> left2 = new BinaryNode<Integer>(6);
        BinaryNode<Integer> right2 = new BinaryNode<Integer>(7);
        left.setLeftNode(left1);
        left.setRightNode(right1);
        right.setLeftNode(left2);
        right.setRightNode(right2);
        BinaryNode<Integer> left3 = new BinaryNode<Integer>(8);
        left1.setLeftNode(left3);
        System.out.println("节点数："+getNodes(root));
        System.out.println("深度："+getDepth(root));
        System.out.println("前序遍历结果：");
        frontTraverse(root);
        System.out.println();
        System.out.println("中序遍历结果：");
        midTraverse(root);
        System.out.println();
        System.out.println("后序遍历结果：");
        afterTraverse(root);
        System.out.println();
        System.out.println("层次遍历结果：");
        levelTraverse(root);

    }

}