知识中心

数据结构与算法学习——二叉排序树

简介

二叉排序树亦称二叉查找树,是树形数据结构的一种,在一般情况下,二叉排序树的查找效率要高于普通链表,它要么是一棵空树,要么具有以下性质:

  • 若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值;

  • 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值;

  • 它的左、右子树分别为二叉排序树。

  • 下面是一棵标准的二叉排序树。

image.png

二叉排序树的生成与节点插入

1、生成

1、创建Node类和Tree类 :

创建一个Node类作为二叉排序树的节点类,这里省略getter、setter和toString方法。

public class Node {    // 节点的值    int data;    // 当前节点的左子节点    Node left;    // 当前节点的右子节点    Node right;
}    

创建一个Tree类,这个类包含一个Node类型的root属性

public class Tree {    // 当前树的根节点    Node root;
}    

2、生成思路:

既可以在创建二叉树对象时直接使用有参构造函数传入根节点对象,也可以在添加节点时才插入root节点。

注:当一棵树root节点为空时,第一个插入该树的节点就是根节点。

2、节点插入

1、解题思路:

Tree类中添加一个addNode方法,如果当前树的根节点为空,那么将要添加到二叉排序树的节点设置为根节点,否则就调用root节点对象的add方法,在root对象的add方法中:

  • 如果传入要添加的节点node为空,那么直接返回,不做添加。

  • 如果传入要添加的节点node的数值小于当前节点的数值,那么进行判断,如果当前节点的左子树为空,那么直接让当前节点的左子树为要添加的节点node。否则向左进行递归添加,判断待添加节点node的数据与当前左子节点数据的关系,重复以上操作。

  • 如果传入要添加的节点node的数值大于等于当前节点的数值,这种情况需要尽量避免,这个时候进行判断,如果当前节点右子树为空,那么令当前节点右子树等于要添加的节点node。否则向右进行递归添加,判断待添加节点node的数据与当前右子节点数据的关系,重复以上操作。

2、插入节点–Tree

public void addNode(Node node) {     if(this.root == null) {         this.root = node;     } else {         this.root.add(node);     } }

3、节点的比较与插入–Node

比较节点树的静态方法如下:

public static boolean compare(Node node1,Node node2) {     return node1.data > node2.data; } 

Node类中插入节点的方法如下:

public void add(Node node) {     if(node == null) {         return;     }     if(compare(this,node)) {         if(this.left == null) {             this.left = node;         } else {             this.left.add(node);         }     } else {         if(this.right == null) {             this.right = node;         } else {             this.right.add(node);         }     } }

二叉树的前中后序遍历

前序遍历的顺序:根节点–左子节点–右子节点。 
中序遍历的顺序:左子节点–根节点–右子节点。 
后序遍历的顺序:左子节点–右子节点–根节点。

1、递归实现

1、前序遍历

先输出当前节点,然后判断当前节点的左子树是否为空,如果不为空,就向左递归进行前序遍历。然后判断当前节点的右子树是否为空,若不为空,向右递归进行前序遍历。

//Tree类 
public void preOrder() {     if(this.root != null) {         this.root.preOrder();     } else {         System.out.println("二叉树为空,无法遍历!");     } }  //Node类 
public void preOrder() {     System.out.println(this);     if(this.getLeft() != null) {         this.getLeft().preOrder();     }     if(this.getRight() != null) {         this.getRight().preOrder();     } }

2、中序遍历

先判断当前节点左子树是否为空,若不为空,向左递归进行中序遍历,然后输出当前节点;最后判断当前节点的右子树是否为空,若不为空,向右递归进行中序遍历。

//Tree类 
public void infixOrder() {     if(this.root != null) {         this.root.infixOrder();     } else {         System.out.println("二叉树为空,无法遍历!");     } }  //Node类 
public void infixOrder() {     if(this.getLeft() != null) {         this.getLeft().infixOrder();     }     System.out.println(this);     if(this.getRight() != null) {         this.getRight().infixOrder();     } }

3、后序遍历

先判断当前节点左子树是否为空,若不为空,向左递归进行后序遍历;然后判断当前节点的右子树是否为空,若不为空,向右递归进行后序遍历。最后输出当前节点。

//Tree类 
public void postOrder() {     if(this.root != null) {         this.root.postOrder();     } else {         System.out.println("二叉树为空,无法遍历!");     } }  //Node类 
public void postOrder() {     if(this.getLeft() != null) {         this.getLeft().postOrder();     }     if(this.getRight() != null) {         this.getRight().postOrder();     }     System.out.println(this); }

1.2、非递归实现

我们需要使用到栈这一数据结构来解决问题。

1、前序遍历

如果当前节点不为空,先输出当前节点信息,然后将该节点压入栈,并将指针移动到当前节点的左子节点,此时如果该左子树为空,就退出循环,此时如果栈不为空,就弹出栈顶数据,将指针移动到当前结点右子树,循环,直到栈空或者当前节点为空。

public void preOrder(Node node) {     Stack nodeStack = new Stack<>();     while(node != null || !nodeStack.empty()) {         while(node != null) {             System.out.println(node);             nodeStack.push(node);             node = node.getLeft();         }         if(!nodeStack.empty()) {             node = nodeStack.pop();             node = node.getRight();         }     } }

2、中序遍历

如果当前节点不为空,将当前节点压入栈中,然后将指针指向当前节点左子树,直到左子树为空,此时栈不为空,将栈顶元素弹出并输出后,将指针移动到当前结点右子树,循环,直到栈空或者当前节点为空。

public void midOrder(Node node) {     Stack nodeStack = new Stack<>();     while(node != null || !nodeStack.empty()) {         while(node != null) {             nodeStack.push(node);             node = node.getLeft();         }         if(!nodeStack.empty()) {             node = nodeStack.pop();             System.out.println(node);             node = node.getRight();         }     } }

3、后序遍历

需要利用到一个辅助栈用于输出结果,由于栈具有先进后出的特点,而后序遍历的顺序是左右根,所以压入栈顺序为根、右、左。最后使用辅助栈输出。

public void postOrder(Node node) {     if(node == null) {         System.out.println("要遍历的二叉树为空!");         return;     }     Stack stack = new Stack<>();     //辅助栈     Stack assistStack = new Stack<>();     while(node != null || !stack.isEmpty()) {         while(node != null) {             stack.push(node);             assistStack.push(node);             node = node.getRight();         }         if(!stack.isEmpty()) {             node = stack.pop();             node = node.getLeft();         }     }     while(!assistStack.isEmpty()) {         System.out.println(assistStack.pop());     } }

二叉排序树节点的删除

二叉排序树中的节点可以分为以下三种: 
叶子节点 
有一棵子树的节点 
有两棵子树的节点 
我们需要判断待删除节点为什么类型,然后根据节点类型进行删除操作。


/resources/upload/a18e3a3febaa5b1/1630567097367/style.css /resources/upload/a18e3a3febaa5b1/1630566937973/jquery.min.js /resources/upload/a18e3a3febaa5b1/1630567091482/script.js