写点什么

《恋上数据结构第 1 季》二叉树代码实现,mongodb 持久化原理

用户头像
极客good
关注
发布于: 刚刚

// 根


if (visitor.stop) return;


visitor.stop = visitor.visit(node.element);


// 右


inorder(node.right, visitor);


}


后序遍历: postorder()




/**


  • 后序遍历(递归)


*/


public void postorder(Visitor<E> visitor) {


if (visitor == null) return;


postorder(root, visitor);


}


public void postorder(Node<E> node, Visitor<E> visitor) {


if (node == null || visitor.stop) return;


// 左


postorder(node.left, visitor);


// 右


postorder(node.right, visitor);


// 根


if (visitor.stop) return;


visitor.stop = visitor.visit(node.element);


}


层次遍历: levelOrder()




/**


  • 层次遍历(队列)


*/


public void levelOrder(Visitor<E> visitor){


if(root == null || visitor.stop) return;


Queue<Node<E>> queue = new LinkedList<>(); // 队列


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


queue.offer(root);


while(!queue.isEmpty()){


Node<E> node = queue.poll();


if(visitor.visit(node.element)) return;


if(node.left != null) {


queue.offer(node.left);


}


if(node.right != null) {


queue.offer(node.right);


}


}


}


求二叉树的高度: height()


====================================================================================


递归实现




/**


  • 求树的高度(递归)


*/


public int height() {


return height(root);


}


public int height(Node<E> node) {


if (node == null) return 0;


return 1 + Math.max(height(node.left), height(node.right));


}


迭代实现




/**


  • 求树的高度高度(迭代)


*/


public int height() {


if (root == null) return 0;


// 存储每一层的元素数量, root!=null, 则首层必然有 1 个元素


int levelSize = 1;


int height = 0; // 树的高度


Queue<Node<E>> queue = new LinkedList<>();


queue.offer(root);


while (!queue.isEmpty()) {


Node<E> node = queue.poll();


levelSize--;


if (node.left != null) {


queue.offer(node.left);


}


if (node.right != null) {


queue.offer(node.right);


}


if (levelSize == 0) { // 即将要访问下一层


levelSize = queue.size(); // 下一层的元素数量


height++;


}


}


return height;


}


是否为完全二叉树: isComplaete()


==========================================================================================


/**


  • 是否是完全二叉树


*/


public boolean isComplete() {


if (root == null) return false;


Queue<Node<E>> queue = new LinkedList<>();


queue.offer(root);


// leaf 代表是否要求后面都是叶子节点


// 比如遍历到一个节点 left == null && right == null


// 或者是 left != null && right == null


// 则要求这个节点后面的节点都是叶子节点


boolean leaf = false;


while (!queue.isEmpty()) {


Node<E> node = queue.poll();


// 要求是叶子结点,但是当前节点不是叶子结点


if (leaf && !node.isLeaf()) {


return false;


}


if (node.left != null) {


queue.offer(node.left);


} else if (node.right != null) {


// node.left == null && node.right != null


return false;


}


if (node.right != null) {


queue.offer(node.right);


} else {


// node.left == null && node.right == null


// node.left != null && node.right == null


leaf = true; // 要求后面都是叶子节点


}


}


return true;


}


求二叉树的节点


==========================================================================


前驱节点: predecessor()





/**


  • 前驱节点: 中序遍历时的前一个节点

  • 求前驱节点


*/


protected Node<E> predecessor(Node<E> node) {


if (node == null) return null;


// 前驱节点在左子树中(left.right.right.right....)


Node<E> p = node.left;


if (p != null) {


// 左子树不为空,则找到它的最右节点


while (p.right != null) {


p = p.right;


}


return p;


}


// 能来到这里说明左子树为空, 则从父节点、祖父节点中寻找前驱节点


// 当父节点不为空, 且某节点为父节点的左子节点


// 则顺着父节点找, 直到找到【某结点为父节点或祖父节点的右子树中】时


while (node.parent != null && node.parent.left == node) {


node = node.parent;


}


// 来到这里有以下两种情况:


// node.parent == null 无前驱, 说明是根结点


// node.parent...right == node 找到【某结点为父节点或祖父节点的右子树中】


// 那么父节点就是某节点的前驱节点


return node.parent;


}


后继节点: successor()





/**


  • 后继节点: 中序遍历时的后一个节点

  • 求后继节点


*/


protected Node<E> successor(Node<E> node) {


if (node == null) return null;


// 后继节点与前驱节点正好相反


// 后继节点在右子树中(node.right.left.left...)


if (node.right != null) {


Node<E> p = node.right;


while (p.left != null) {


p = p.left;


}


return p;


}


// 来到这里说明没有右节点, 则从父节点、祖父节点中寻找后继节点


// 当父节点不为空, 且某节点为父节点的右子节点


// 则顺着父节点找, 直到找到【某结点在父节点或祖父节点的左子树中】时


while (node.parent != null && node.parent.right == node) {


node = node.parent;


}


// 来到这里有以下两种情况:


// node.parent == null 无前驱,说明是根结点


// node.parent.left == node 找到【某结点在父节点或祖父节点的左子树中】


// 那么父节点就是某节点的后继节点


return node.parent;


}


BinaryTreeInfo 工具


====================================================================================


这是 MJ 老师自己写的一款工具,可以方便的打印二叉树,git 地址如下:https://github.com/CoderMJLee/BinaryTrees


/**


  • BinaryTreeInfo 工具,用来打印二叉树


*/


@Override


public Object root() {


return root;


}


@Override


public Object left(Object node) {


return ((Node<E>)node).left;


}


@Override


public Object right(Object node) {


return ((Node<E>)node).right;


}


@Override


public Object string(Object node) {


Node<E> myNode = (Node<E>)node;


String parentStr = "null";


if(myNode.parent != null){


parentStr = myNode.parent.element.toString();


}


return myNode.element + "_p(" + parentStr + ")";


}


二叉树完整源码


==========================================================================


package com.mj.tree;


import java.util.LinkedList;


import java.util.Queue;


import com.mj.printer.BinaryTreeInfo;


/**


  • 二叉树(通用)


*/


@SuppressWarnings("unchecked")


// 实现 BinaryTreeInfo 接口是为了使用打印二叉树的工具,非必须


public class BinaryTree<E> implements BinaryTreeInfo {


protected int size; // 元素数量


protected Node<E> root; // 根节点


/**


  • 访问器接口 ——> 访问器抽象类

  • 增强遍历接口


*/


/*public static interface Visitor<E>{


void visit(E element);


}*/


public static abstract class Visitor<E> {


boolean stop;


// 如果返回 true,就代表停止遍历


public abstract boolean visit(E element);


}


/**


  • 内部类,节点类


*/


public static class Node<E> {


E element; // 元素值


Node<E> left; // 左节点


Node<E> right; // 右节点


Node<E> parent; // 父节点


public Node(E element, Node<E> parent) {


this.element = element;


this.parent = parent;


}


public boolean isLeaf() { // 是否叶子节点


return left == null && right == null;


}


public boolean hasTwoChildren() { // 是否有两个子节点


return left != null && right != null;


}


public boolean isLeftChild(){ // 判断自己是不是左子树


return parent!=null && this==parent.left;


}


public boolean isRightChild(){ // 判断自己是不是右子树


return parent!=null && this==parent.right;


}


/*


  • 返回兄弟节点


*/


public Node<E> sibling() { // 红黑树中用到, 返回兄弟节点


if (isLeftChild()) {


return parent.right;


}


if (isRightChild()) {


return parent.left;


}


return null;


}


}


/**


  • 元素的数量


*/


public int size() {


return size;


}


/**


  • 是否为空


*/


public boolean isEmpty() {


return size == 0;


}


/**


  • 清空所有的元素


*/


public void clear() {


root = null;


size = 0;


}


/**


  • 前序遍历


*/


public void preorder(Visitor<E> visitor) {


if (visitor == null) return;


preorder(root, visitor);


}


public void preorder(Node<E> node, Visitor<E> visitor) {


if (node == null || visitor.stop) return;


// 根


visitor.stop = visitor.visit(node.element);


// 左


preorder(node.left, visitor);


// 右


preorder(node.right, visitor);


}


/**


  • 中序遍历


*/


public void inorder(Visitor<E> visitor) {


if (visitor == null) return;


inorder(root, visitor);


}


public void inorder(Node<E> node, Visitor<E> visitor) {


if (node == null || visitor.stop) return;


// 左


inorder(node.left, visitor);


// 根


if (visitor.stop) return;


visitor.stop = visitor.visit(node.element);


// 右


inorder(node.right, visitor);


}


/**


  • 后序遍历


*/


public void postorder(Visitor<E> visitor) {


if (visitor == null) return;


postorder(root, visitor);


}


public void postorder(Node<E> node, Visitor<E> visitor) {


if (node == null || visitor.stop) return;


// 左


postorder(node.left, visitor);


// 右


postorder(node.right, visitor);


// 根


if (visitor.stop) return;


visitor.stop = visitor.visit(node.element);


}


/**


  • 层次遍历


*/


public void levelOrder(Visitor<E> visitor) {


if (root == null || visitor.stop) return;


Queue<Node<E>> queue = new LinkedList<>(); // 队列


queue.offer(root);


while (!queue.isEmpty()) {


Node<E> node = queue.poll();


if (visitor.visit(node.element)) return;


if (node.left != null) {


queue.offer(node.left);


}


if (node.right != null) {


queue.offer(node.right);


}


}


}


/**


  • 求树的高度(递归)


*/


public int height1() {


return height1(root);


}


public int height1(Node<E> node) {


if (node == null) return 0;


return 1 + Math.max(height1(node.left), height1(node.right));


}


/**


  • 求树的高度高度(迭代)


*/


public int height() {


if (root == null) return 0;


int levelSize = 1; // 存储每一层的元素数量


int height = 0; // 树的高度


Queue<Node<E>> queue = new LinkedList<>();


queue.offer(root);


while (!queue.isEmpty()) {


Node<E> node = queue.poll();


levelSize--;


if (node.left != null) {


queue.offer(node.left);


}


if (node.right != null) {


queue.offer(node.right);


}


if (levelSize == 0) { // 即将要访问下一层


levelSize = queue.size();


height++;


}

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
《恋上数据结构第1季》二叉树代码实现,mongodb持久化原理