1、概述
通过前面的学习，我们知道，有序数组可以利用二分查找法快速的查找特定的值，时间复杂度为O(log2N)，但是插入数据时很慢，时间复杂度为O(N)；链表的插入和删除速度都很快，时间复杂度为O(1)，但是查找特定值很慢，时间复杂度为O(N)。
二叉树
如果树的每个节点最多有两个子节点，则称为二叉树。如果节点的子节点可以多余两个，称为多路树。
满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
二叉树的存储结构
顺序存储
二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。
如下所示左边的非二叉树转换为完全二叉树，对应下面的数组
我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,…），若节点 i 有左右孩子，则其左孩子节点为 2i，右孩子节点为 2i+1。
缺点：浪费空间
链式存储
- 指向左孩子节点的指针（Lchild）；
- 节点存储的数据（data）；
- 指向右孩子节点的指针（Rchild）；
二叉树的遍历算法
中序
递归
public void inorder(Node currentRoot){if(currentRoot != null){inorder(currentRoot.leftChild); //先对当前节点的左子树对进行中序遍历System.out.print(currentRoot.age+"\t"); //然后访问当前节点inorder(currentRoot.rightChild); //最后对当前节点的右子树对进行中序遍历}}
非递归
ArrayList<Integer> arr = new ArrayList<Integer>();
public void middleOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root!=null||!stack.isEmpty()) {
while(root!=null) {
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()) {
root = stack.pop();
arr.add(root.val);
root = root.right;
}
}
}
先序
后序
层次
二叉搜索树
二叉搜索树的特点是，一个节点的左子节点的关键字值小于这个节点，右子节点的关键字值大于或等于这个父节点。
平衡树与非平衡树，非平衡就是说树的大部分节点在根的一边，如下图所示：
查找
我们已经知道，二叉搜索树的特点是左子节点小于父节点，右子节点大于或等于父节点。查找某个节点时，先从根节点入手，如果该元素值小于根节点，则转向左子节点，否则转向右子节点，以此类推，直到找到该节点，或者到最后一个叶子节点依然没有找到，则证明树中没有该节点。
比如我们要在树中查找57，执行的搜索路线如下图所示：
代码
public Node find(int key)
{
Node cur = root;
if(cur==null) {
return null;
}
while(cur.age!=key) {
if(cur.age<key) {
cur = cur.rightChild;
}else {
cur = cur.leftChild;
}
if(cur==null) {
return null;
}
}
return cur;
}
插入
插入的节点作为叶子节点
代码
//插入新节点
public void insert(Node node) {
if(root==null) {
root = node;
}else {
Node cur = this.root;
while(true) {
if(node.age<cur.age) {
if(cur.leftChild==null) {
cur.leftChild = node;
return;
}
cur = cur.leftChild;
}else {
if(cur.rightChild==null) {
cur.rightChild = node;
return;
}
cur = cur.rightChild;
}
}
}
}
遍历
代码
//遍历
public static final int PREORDER = 1; //前序遍历
public static final int INORDER = 2; //中序遍历
public static final int POSTORDER = 3; //中序遍历
//遍历
public void traverse(int type){
switch(type){
case 1:
System.out.print("前序遍历：\t");
preorder(root);
System.out.println();
break;
case 2:
System.out.print("中序遍历：\t");
inorder(root);
System.out.println();
break;
case 3:
System.out.print("后序遍历：\t");
postorder(root);
System.out.println();
break;
}
}
//前序遍历
public void preorder(Node currentRoot) {
if(currentRoot!=null) {
System.out.println(currentRoot.age+"\t");
preorder(currentRoot.leftChild);
preorder(currentRoot.rightChild);
}
}
//中序遍历，这三种遍历都用了迭代的思想
public void inorder(Node currentRoot){
if(currentRoot != null){
inorder(currentRoot.leftChild); //先对当前节点的左子树对进行中序遍历
System.out.print(currentRoot.age+"\t"); //然后访问当前节点
inorder(currentRoot.rightChild); //最后对当前节点的右子树对进行中序遍历
}
}
//后序遍历
public void postorder(Node currentRoot){
if(currentRoot != null){
postorder(currentRoot.leftChild);
postorder(currentRoot.rightChild);
System.out.print(currentRoot.age+"\t");
}
}
查找最值
在二叉搜索树中，查找最大值、最小是是很容易实现的，从根循环访问左子节点，直到该节点没有左子节点为止，该节点就是最小值；从根循环访问右子节点，直到该节点没有右子节点为止，该节点就是最大值。
//返回关键值最大的节点,也就对右节点不断地遍历
public Node getMax(){
if(isEmpty()){
return null;
}
Node cur = root;
while(cur.rightChild != null){
cur = cur.rightChild;
}
return cur;
}
//返回关键值最小的节点，对左节点不断的遍历
public Node getMin(){
if(isEmpty()){
return null;
}
Node cur = root;
while(cur.leftChild != null){
cur = cur.leftChild;
}
return cur;
}
删除节点
思路大致分三种
- 该节点没有子节点
- 该节点有一个子节点
- 无论要删除的节点下面有多复杂的子树，只需要将它的子树上移
- 还有一种特殊情况需要考虑，就是要删除的是根节点
- 该节点有两个子节点
import java.util.ArrayList; import java.util.List;
import p.Node;
public class BinaryTree { private Node root;
public BinaryTree() {
root = null;
}
//查找节点
public Node find(int key)
{
Node cur = root;
if(cur==null) {
return null;
}
while(cur.age!=key) {
if(cur.age<key) {
cur = cur.rightChild;
}else {
cur = cur.leftChild;
}
if(cur==null) {
return null;
}
}
return cur;
}
//插入新节点
public void insert(Node node) {
if(root==null) {
root = node;
}else {
Node cur = this.root;
while(true) {
if(node.age<cur.age) {
if(cur.leftChild==null) {
cur.leftChild = node;
return;
}
cur = cur.leftChild;
}else {
if(cur.rightChild==null) {
cur.rightChild = node;
return;
}
cur = cur.rightChild;
}
}
}
}
//删除指定节点
public boolean delete(Node node) {
if(root==null) {
return false;
}
boolean isLeftChild = true;
Node parent = null;
Node cur = root;
while(cur.age!=node.age) {
parent = cur;
if(node.age<cur.age) {
cur = cur.leftChild;
}else {
isLeftChild = false;//记录要删除节点是否是在父节点的左子节点
cur = cur.rightChild;
}
if(cur == null) {
return false;//没有找到要删除的节点
}
}
if(cur.leftChild==null&&cur.rightChild==null) {//目标节点为叶子节点
if(cur==root) {
root = null;
}else if(isLeftChild) {
parent.leftChild = null;
}else {
parent.rightChild = null;
}
}else if(cur.leftChild==null) {//删除点只有一个右子节点
if(cur==root) {
root = cur.rightChild;
}else if(isLeftChild) {//判断删除节点是父节点的左还是右节点
parent.leftChild = cur.rightChild;
}else {
parent.rightChild = cur.rightChild;
}
}else if(cur.rightChild==null) {//删除点只有一个左子节点
if(cur==root) {
root = cur.leftChild;
}else if(isLeftChild){//判断删除节点是父节点的左还是右节点
parent.leftChild = cur.leftChild;
}else {
parent.rightChild = cur.leftChild;
}
}else {//有两个子节点，首先要找到要删除节点的后继节点
Node successor = cur.rightChild;//一种是欲删除节点的右子节点没有左子节点，那么它本身就是后继节点
Node successorParent = null;
while(successor.leftChild!=null) {//另一种情况是欲删除节点的右子节点有左子节点
successorParent = successor;
successor = successor.leftChild;
}
if(successorParent==null) {//欲删除节点的右子节点没有左子节点,则将以后继节点为根的子树上移即可
if(root==cur) {
root = successor;
root.leftChild = cur.leftChild;
}else if(isLeftChild) {
parent.leftChild = successor;
successor.leftChild = cur.leftChild;
}else {
parent.rightChild = successor;
successor.leftChild = cur.leftChild;
}
}else {//另一种情况是欲删除节点的右子节点有左子节点
successorParent.leftChild = successor.rightChild;
successor.rightChild = cur.rightChild;
if(cur==root) {
root = successor;
successor.leftChild = cur.leftChild;
}else if(isLeftChild) {
parent.leftChild = successor;
successor.leftChild = cur.leftChild;
}else {
parent.rightChild = successor;
successor.leftChild = cur.leftChild;
}
}
}
return true;
}
//遍历
public static final int PREORDER = 1; //前序遍历
public static final int INORDER = 2; //中序遍历
public static final int POSTORDER = 3; //中序遍历
//遍历
public void traverse(int type){
switch(type){
case 1:
System.out.print("前序遍历：\t");
preorder(root);
System.out.println();
break;
case 2:
System.out.print("中序遍历：\t");
inorder(root);
System.out.println();
break;
case 3:
System.out.print("后序遍历：\t");
postorder(root);
System.out.println();
break;
}
}
//前序遍历
public void preorder(Node currentRoot) {
if(currentRoot!=null) {
System.out.println(currentRoot.age+"\t");
preorder(currentRoot.leftChild);
preorder(currentRoot.rightChild);
}
}
//中序遍历，这三种遍历都用了迭代的思想
public void inorder(Node currentRoot){
if(currentRoot != null){
inorder(currentRoot.leftChild); //先对当前节点的左子树对进行中序遍历
System.out.print(currentRoot.age+"\t"); //然后访问当前节点
inorder(currentRoot.rightChild); //最后对当前节点的右子树对进行中序遍历
}
}
//后序遍历
public void postorder(Node currentRoot){
if(currentRoot != null){
postorder(currentRoot.leftChild);
postorder(currentRoot.rightChild);
System.out.print(currentRoot.age+"\t");
}
}
//私有方法，用迭代方法来获取左子树和右子树的最大深度，返回两者最大值
public int getDepth(Node currentRoot,int initdepth) {
int depth = initdepth;
int rightdepth = initdepth;
int leftdepth = initdepth;
if(currentRoot.leftChild!=null) {
leftdepth = getDepth(currentRoot.leftChild, depth+1);
}
if(currentRoot.rightChild!=null) {
rightdepth = getDepth(currentRoot.rightChild, depth+1);
}
return Math.max(leftdepth, rightdepth);
}
//获取树的深度 public int getTreeDepth(){ if(root == null){ return 0; } return getDepth(root,1); } //返回关键值最大的节点,也就对右节点不断地遍历 public Node getMax(){ if(isEmpty()){ return null; } Node cur = root; while(cur.rightChild != null){ cur = cur.rightChild; } return cur; }
//返回关键值最小的节点，对左节点不断的遍历
public Node getMin(){
if(isEmpty()){
return null;
}
Node cur = root;
while(cur.leftChild != null){
cur = cur.leftChild;
}
return cur;
}
//判空
public boolean isEmpty(){
return (root == null);
}
//以树的形式打印出该树
public void displayTree(){
int depth = getTreeDepth();
ArrayList
if(node == null){
System.out.print("*\t"); //如果该节点为null，用空位代替
}else{
System.out.print("* "+node.age+"\t"); //打印该节点
}
printBlank(NodeBlankNum); //打印节点之后的空位
System.out.print("*\t"); //补齐空位
}
System.out.println();
layerIndex++;
currentLayerNodes = getAllNodeOfThisLayer(currentLayerNodes); //获取下一层所有的节点
}
}
//获取指定节点集合的所有子节点
private ArrayList getAllNodeOfThisLayer(List parentNodes){
ArrayList list = new ArrayList<Node>();
Node parentNode;
for(int i=0;i<parentNodes.size();i++){
parentNode = (Node)parentNodes.get(i);
if(parentNode != null){
if(parentNode.leftChild != null){ //如果上层的父节点存在左子节点，加入集合
list.add(parentNode.leftChild);
}else{
list.add(null); //如果上层的父节点不存在左子节点，用null代替，一样加入集合
}
if(parentNode.rightChild != null){
list.add(parentNode.rightChild);
}else{
list.add(null);
}
}else{ //如果上层父节点不存在，用两个null占位，代表左右子节点
list.add(null);
list.add(null);
}
}
return list;
}
//打印指定个数的空位
private void printBlank(int num){
for(int i=0;i<num;i++){
System.out.print("*\t");
}
}
//判断是否为叶子节点 public boolean isLeaf(Node node){ return (node.leftChild != null || node.rightChild != null); }
//获取根节点
public Node getRoot(){
return root;
}
} ```
若有收获，就点个赞吧
0 人点赞
