做网站租用数据库云游戏主机

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;}}
}