当前位置：首页 > news >正文

免费php域名网站郑州见效果付费优化公司

news 2025/8/7 0:46:04

免费php域名网站,郑州见效果付费优化公司,外国做挂的网站是多少钱,国外平面设计1，二叉树基本概念树分为很多种，其中每一个节点最多有两个节点的树形式称之为二叉树二叉树的子节点分为左节点和父节点；对于一个父节点来说，可以单独存在左子节点或者右子节点，也可以同时存在左右子节点如果二叉树的…

1，二叉树基本概念

树分为很多种，其中每一个节点最多有两个节点的树形式称之为二叉树
二叉树的子节点分为左节点和父节点；对于一个父节点来说，可以单独存在左子节点或者右子节点，也可以同时存在左右子节点
如果二叉树的所有叶子节点都在最后一层，并且节点总数 = 2 ^ n - 1，n为最大层数，则该二叉树可以称之为满二叉树
如果二叉树的所有叶子节点都在最后一层或者倒数第二层，且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，则称之为完全二叉树

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());}}@Data@ToStringstatic 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;}@Data@ToStringstatic 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());}}}@Data@ToStringstatic 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;}}
}