搜索二叉树概念
二叉树是树的特殊一种，具有如下特点：
1、每个结点最多有两颗子树，结点的度最大为2。
2、左子树和右子树是有顺序的，次序不能颠倒。
3、即使某结点只有一个子树，也要区分左右子树。
搜索二叉树
递归遍历
前序遍历
基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。
public static void preRecDisplay(TreeNode node){
//前序遍历
if (node!=null){
System.out.println(node.data);
preRecDisplay(node.leftNode);
preRecDisplay(node.rightNode);
}
}
中序遍历
基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。
public static void midRecDisplay(TreeNode node){
//中序遍历
if (node!=null) {
midRecDisplay(node.leftNode);
System.out.println(node.data);
midRecDisplay(node.rightNode);
}
}
后序遍历
基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。
public static void postRecDisplay(TreeNode node){
//后序遍历
if (node!=null) {
postRecDisplay(node.leftNode);
postRecDisplay(node.rightNode);
System.out.println(node.data);
}
}
public static void main(String[] args){
int datas[] = {1,2,3,4,5,6,7,8,9};
Tree tree = new Tree(datas);
postRecDisplay(tree.root);
}
非递归遍历
前序遍历
对于任一结点p：
a. 访问结点p，并将结点p入栈；
b. 判断结点p的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点p，循环置a；若不为空，则将p的左孩子置为当前结点p；
c. 直到p为空，并且栈为空，则遍历结束。
public static void preDisplay(TreeNode node){
//前序遍历
Stack<TreeNode> stack = new Stack<>();
while (true){
while (node!=null){
//输出就是遍历的过程，前序遍历先输出当前节点
System.out.println(node.data);
//最后输出右节点，那就用stack来保存它
stack.push(node);
//当前节点置为左节点，下次循环就可以输出左节点
node=node.leftNode;
}
if (stack.isEmpty()){
return;
}
//当前节点置为右节点
node = stack.pop().rightNode;
}
}
中序遍历
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一个根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才停止访问，然后按相同的规则访问其右子树。其处理过程如下：
对于任一结点：
a. 若其左孩子不为空，则将p入栈，并将p的左孩子设置为当前的p，然后对当前结点再进行相同的操作；
b. 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的p置为栈顶结点的右孩子；
c. 直到p为空并且栈为空，则遍历结束。
public static void midDisplay(TreeNode node){
//中序遍历
Stack<TreeNode> stack = new Stack<>();
while (true){
//循环截止说明当前节点没有左节点了
while (node!=null){
//需要先输出左节点，只能讲当前节点入栈，暂时不输出
stack.push(node);
//先输出左节点
node=node.leftNode;
}
if (stack.isEmpty()){
return;
}
node = stack.pop();
//当前节点没有左子树了，该轮到它自己输出了
System.out.println(node.data);
//输出右子树的过程
node = node.rightNode;
}
}
后序遍历
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问，并且左孩子在右孩子之前访问才能访问根结点，这就为流程控制带来了难题。
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。若p不存在左孩子和右孩子，则可以直接访问它。当前p节点为左子树输出一次，然后重复入栈过程，当前节点p为右子树,那么他的父节点就必定不能重复的将右子树入栈。则之间循环输出即可。
当前节点p有右节点 ，需要将右节点放到stack中，重复上述过程。
public static void postListN(TreeNode node){
//后序遍历
Stack<TreeNode> stack = new Stack<>();
while (true){
while (node!=null){
//最后输出当前节点，所有先入栈保存
stack.push(node);
node=node.leftNode;
}
if (stack.isEmpty()){
return;
}
//当前节点
node = stack.lastElement();
//在这里当前节点有几种情况
//1.当前节点没有右节点，需要输出，同时输出也有几种情况
// （1 当前节点为左子树 输出一次，然后重复入栈过程
// （2 当前节点为右子树 当前节点已经为右子树，输出完毕，那么他的父节点就必定不能重复的将右子树入栈
//2.当前节点有右节点 需要将右节点放到stack中
//判断当前节点有没有右节点
if (node.rightNode==null){
//没右节点
stack.pop();
System.out.println(node.data);
node = node.rightNode;
//判断当前node是不是右分支
while (stack.lastElement().rightNode==node){
//是右分支
TreeNode root = stack.pop();
System.out.println(root.data);
if (stack.isEmpty()){
break;
}
}
}
//判断栈是否为空
if (!stack.isEmpty()){
//将当前节点置为右节点
node=stack.lastElement().rightNode;
}else{
node=null;
}
}
}
网友评论