数据结构与算法学习——二叉排序树
简介
二叉排序树亦称二叉查找树，是树形数据结构的一种，在一般情况下，二叉排序树的查找效率要高于普通链表，它要么是一棵空树，要么具有以下性质：
-
若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
-
若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
-
它的左、右子树分别为二叉排序树。
-
下面是一棵标准的二叉排序树。
二叉排序树的生成与节点插入
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<Node> 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<Node> 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<Node> stack = new Stack<>();
//辅助栈
Stack<Node> 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());
}
}
二叉排序树节点的删除
二叉排序树中的节点可以分为以下三种：
叶子节点
有一棵子树的节点
有两棵子树的节点
我们需要判断待删除节点为什么类型，然后根据节点类型进行删除操作。
💫点击直接资料领取💫
具体文章转数据结构与算法学习——二叉排序树
这里有各种学习资料还有有有趣好玩的编程项目，更有难寻的各种资源。
- 点赞
- 收藏
- 关注作者
评论（0）