潍坊网站优化公司,wordpress修改备案号,免费的短视频素材库,中国万网网站建设服务1#xff0c;二叉树基本概念
树分为很多种#xff0c;其中每一个节点最多有两个节点的树形式称之为二叉树二叉树的子节点分为左节点和父节点#xff1b;对于一个父节点来说#xff0c;可以单独存在左子节点或者右子节点#xff0c;也可以同时存在左右子节点 如果二叉树的…1二叉树基本概念
树分为很多种其中每一个节点最多有两个节点的树形式称之为二叉树二叉树的子节点分为左节点和父节点对于一个父节点来说可以单独存在左子节点或者右子节点也可以同时存在左右子节点 如果二叉树的所有叶子节点都在最后一层并且节点总数 2 ^ n - 1n为最大层数则该二叉树可以称之为满二叉树 如果二叉树的所有叶子节点都在最后一层或者倒数第二层且最后一层的叶子节点在左边连续倒数第二层的叶子节点在右边连续则称之为完全二叉树
2二叉树遍历
2.1前序遍历
先输出当前节点初始为叶子节点如果左子节点不为空再递归前序遍历输出左子节点如果右子节点不为空最后递归前序遍历输出右子节点
2.2中序遍历
如果左子节点不为空先递归中序遍历输出左子节点再输出当前节点如果右子节点不为空最后递归中序遍历输出右子节点
2.3后续遍历
如果左子节点不为空先递归后序遍历输出左子节点如果右子节点不为空再递归后序遍历输出右子节点最后输出当前节点
2.4遍历代码汇总
package com.self.datastructure.tree;import lombok.Data;
import lombok.ToString;import java.util.ArrayList;
import java.util.List;/*** 二叉树** author pj_zhang* create 2020-03-21 22:02**/
public class BinaryTree {public static void main(String[] args) {MyBinaryTree binaryTree new MyBinaryTree();binaryTree.addNode(5);binaryTree.addNode(1);binaryTree.addNode(4);binaryTree.addNode(6);binaryTree.addNode(3);binaryTree.addNode(2);binaryTree.addNode(7);binaryTree.addNode(8);binaryTree.addNode(8);binaryTree.postShowDetails(binaryTree.getNode());}static class MyBinaryTree {private Node node;// 添加二叉树节点public void addNode(Integer data) {if (null node) {node new Node(data);} else {addNode(data, node);}}private void addNode(Integer data, Node node) {if (null node) {throw new RuntimeException(Node 节点为空);}if (data node.getData()) {Node rightNode node.getRightNode();if (null rightNode) {Node newNode new Node(data);node.setRightNode(newNode);newNode.setParentNode(node);} else {addNode(data, node.getRightNode());}} else if (data node.getData()) {Node leftNode node.getLeftNode();if (null leftNode) {Node newNode new Node(data);node.setLeftNode(newNode);newNode.setParentNode(node);} else {addNode(data, node.getLeftNode());}} else {System.out.println(数据节点已经存在);}}// 获取整体树节点public Node getNode() {return node;}// 前序遍历,// 先输出当前节点值// 再输出左侧节点值// 最后输出右侧节点值public void preShowDetails() {doPreShowDetails(node);}private void doPreShowDetails(Node node) {if (null node) {return;}System.out.println(Node: node.getData());if (null ! node.getLeftNode()) {doPreShowDetails(node.getLeftNode());}if (null ! node.getRightNode()) {doPreShowDetails(node.getRightNode());}}// 中序输入// 先输出左侧节点值// 再输出当前节点值// 最后输出中间节点值// 中序输出结果为有序数组public void middleShowDetails() {doMiddleShowDetails(node);}public void doMiddleShowDetails(Node node) {if (null node) {return;}if (null ! node.getLeftNode()) {doMiddleShowDetails(node.getLeftNode());}System.out.println(Node: node.getData());if (null ! node.getRightNode()) {doMiddleShowDetails(node.getRightNode());}}// 后续输出// 先输出左侧数据// 再输出右侧数据// 最后输出当前数据public void postShowDetails() {doPostShowDetails(node);}public void doPostShowDetails(Node node) {if (null node) {return;}if (null ! node.getLeftNode()) {doPostShowDetails(node.getLeftNode());}if (null ! node.getRightNode()) {doPostShowDetails(node.getRightNode());}System.out.println(Node: node.getData());}}DataToStringstatic class Node {private Integer data;private Node leftNode;private Node rightNode;private Node parentNode;public Node() {}public Node(Integer data) {this(data, null, null);}public Node(Integer data, Node leftNode, Node rightNode) {this.data data;this.leftNode leftNode;this.rightNode rightNode;}}
}3二叉树查找
3.1前序查找
先比较当前节点当前节点匹配到直接返回再匹配左侧节点并递归前序查找进行匹配匹配到直接返回最后匹配右侧节点并递归前序查找进行匹配匹配到直接返回以上几步没有匹配到则返回null表示没有匹配到
3.2中序查找
先匹配左侧节点并递归中序查找进行匹配匹配到直接返回再比较当前节点当前节点匹配到直接返回最后匹配右侧节点并递归中序查找进行匹配匹配到直接返回以上几步没有匹配到则返回null表示没有匹配到
3.3后续查找
先匹配左侧节点并递归后序查找进行匹配匹配到直接返回再匹配右侧节点并递归后序查找进行匹配匹配到直接返回再比较当前节点当前节点匹配到直接返回以上几步没有匹配到则返回null表示没有匹配到
3.4查找代码汇总
package com.self.datastructure.tree;import lombok.Data;
import lombok.ToString;import java.util.ArrayList;
import java.util.List;/*** 二叉树** author pj_zhang* create 2020-03-21 22:02**/
public class BinaryTree {public static void main(String[] args) {MyBinaryTree binaryTree new MyBinaryTree();binaryTree.addNode(5);binaryTree.addNode(1);binaryTree.addNode(4);binaryTree.addNode(6);binaryTree.addNode(3);binaryTree.addNode(2);binaryTree.addNode(7);binaryTree.addNode(8);System.out.println(binaryTree.preFindNode(50));}static class MyBinaryTree {private Node node;// 添加二叉树节点public void addNode(Integer data) {if (null node) {node new Node(data);} else {addNode(data, node);}}private void addNode(Integer data, Node node) {if (null node) {throw new RuntimeException(Node 节点为空);}if (data node.getData()) {Node rightNode node.getRightNode();if (null rightNode) {Node newNode new Node(data);node.setRightNode(newNode);newNode.setParentNode(node);} else {addNode(data, node.getRightNode());}} else if (data node.getData()) {Node leftNode node.getLeftNode();if (null leftNode) {Node newNode new Node(data);node.setLeftNode(newNode);newNode.setParentNode(node);} else {addNode(data, node.getLeftNode());}} else {System.out.println(数据节点已经存在);}}// 前序查找public Integer preFindNode(Integer targetData) {return doPreFindNode(targetData, node);}public Integer doPreFindNode(Integer targetData, Node node) {if (null node) {return null;}if (targetData node.getData()) {return node.getData();} else if (targetData node.getData()) {return doPreFindNode(targetData, node.getLeftNode());} else if (targetData node.getData()) {return doPreFindNode(targetData, node.getRightNode());}return null;}// 中序查找public Integer middleFindNode(Integer targetData) {return doMiddleFindNode(targetData, node);}public Integer doMiddleFindNode(Integer targetData, Node node) {if (null node) {return null;}if (targetData node.getData()) {return doMiddleFindNode(targetData, node.getLeftNode());} else if (targetData node.getData()) {return node.getData();} else if (targetData node.getData()) {return doMiddleFindNode(targetData, node.getRightNode());}return null;}// 后序查找public Integer postFindNode(Integer targetData) {return doPostFindNode(targetData, node);}public Integer doPostFindNode(Integer targetData, Node node) {if (null node) {return null;}if (targetData node.getData()) {return doPostFindNode(targetData, node.getLeftNode());} else if (targetData node.getData()) {return doPostFindNode(targetData, node.getRightNode());} else if (targetData node.getData()) {return node.getData();}return null;}DataToStringstatic class Node {private Integer data;private Node leftNode;private Node rightNode;private Node parentNode;public Node() {}public Node(Integer data) {this(data, null, null);}public Node(Integer data, Node leftNode, Node rightNode) {this.data data;this.leftNode leftNode;this.rightNode rightNode;}}
}4二叉树删除
4.1删除步骤
如果删除的节点是叶子节点则直接删除如果删除的是非叶子节点则需要对删除节点的子节点进行处理用右侧最左节点代替该节点并删除右侧最左节点
4.2删除代码实现
package com.self.datastructure.tree;import lombok.Data;
import lombok.ToString;import java.util.ArrayList;
import java.util.List;/*** 二叉树** author pj_zhang* create 2020-03-21 22:02**/
public class BinaryTree {public static void main(String[] args) {MyBinaryTree binaryTree new MyBinaryTree();binaryTree.addNode(5);binaryTree.addNode(2);binaryTree.addNode(1);binaryTree.addNode(4);binaryTree.addNode(3);binaryTree.addNode(8);binaryTree.addNode(6);binaryTree.addNode(9);binaryTree.addNode(10);binaryTree.middleShowDetails();System.out.println(binaryTree.delNode(1));;binaryTree.middleShowDetails();}static class MyBinaryTree {private Node node;// 添加二叉树节点public void addNode(Integer data) {if (null node) {node new Node(data);} else {addNode(data, node);}}private void addNode(Integer data, Node node) {if (null node) {throw new RuntimeException(Node 节点为空);}if (data node.getData()) {Node rightNode node.getRightNode();if (null rightNode) {node.setRightNode(new Node(data));} else {addNode(data, node.getRightNode());}} else if (data node.getData()) {Node leftNode node.getLeftNode();if (null leftNode) {node.setLeftNode(new Node(data));} else {addNode(data, node.getLeftNode());}} else {System.out.println(数据节点已经存在);}}/*** 二叉树节点删除* * 如果删除节点为叶子节点, 则直接删除* * 如果删除节点为非叶子节点, 且只有左节点或者有节点其中一个节点, 将子节点设置为该节点* * 如果删除节点为非叶子节点, 则子节点完整, 则让右子节点代替该节点, 左子节点按顺序挂在右子节点的左侧位置** param targetData* return*/public boolean delNode(Integer targetData) {if (null node) {return false;}return doDelNode(targetData, node);}private boolean doDelNode(Integer targetData, Node node) {if (null node) {return false;}if (targetData node.getData()) {// 删除值大于当前节点值, 向右查找return doDelNode(targetData, node.getRightNode());} else if (targetData node.getData()) {// 删除值小于当前节点值, 向左查找return doDelNode(targetData, node.getLeftNode());} else {// 找到后, 进行处理// 获取右侧节点的最左节点Node nextNode findNextNode(node);// 说明存在右侧节点if (null nextNode) {// 直接用左侧节点替换该节点// 如果当前节点是根节点, 直接将根节点替换为其左侧节点if (this.node node) {this.node node.getLeftNode();this.node.setParentNode(null);} else {// 删除节点是中间节点, 如果是父节点的左侧节点, 则将父节点的左侧节点替换为其左侧节点if (node node.getParentNode().getLeftNode()) {node.getParentNode().setLeftNode(node.getLeftNode());} else if (node node.getParentNode().getRightNode()) {// 删除节点是中间节点, 如果是父节点的右侧节点, 则将父节点的右侧节点替换为其左侧节点node.getParentNode().setRightNode(node.getLeftNode());}if (null ! node.getLeftNode()) {node.getLeftNode().setParentNode(node.getParentNode());}}} else {// 存在后继节点// 将当前值替换为后继节点的值node.setData(nextNode.getData());// 将后继节点挂空, 后继节点可能存在右侧节点, 用右侧节点进行替换if (nextNode nextNode.getParentNode().getLeftNode()) {nextNode.getParentNode().setLeftNode(nextNode.getRightNode());} else if (nextNode nextNode.getParentNode().getRightNode()) {// 删除节点是中间节点, 如果是父节点的右侧节点, 则将父节点的右侧节点替换为其左侧节点nextNode.getParentNode().setRightNode(nextNode.getRightNode());}if (null ! nextNode.getRightNode()) {nextNode.getRightNode().setParentNode(nextNode.getParentNode());}}return true;}}/*** 获取右侧节点的最左节点* param node* return*/private Node findNextNode(Node node) {Node nextNode node.getRightNode();if (null nextNode) {return nextNode;}while (null ! nextNode.getLeftNode()) {nextNode nextNode.getLeftNode();}return nextNode;}// 中序输出// 先输出左侧节点值// 再输出当前节点值// 最后输出中间节点值// 中序输出结果为有序数组public void middleShowDetails() {doMiddleShowDetails(node);}public void doMiddleShowDetails(Node node) {if (null node) {return;}if (null ! node.getLeftNode()) {doMiddleShowDetails(node.getLeftNode());}System.out.println(Node: node.getData());if (null ! node.getRightNode()) {doMiddleShowDetails(node.getRightNode());}}}DataToStringstatic class Node {private Integer data;private Node leftNode;private Node rightNode;public Node() {}public Node(Integer data) {this(data, null, null);}public Node(Integer data, Node leftNode, Node rightNode) {this.data data;this.leftNode leftNode;this.rightNode rightNode;}}
}
