一、先/中/后序遍历(递归)
递归方式会导致每个节点会经过三次,先序是在第一次经过节点时访问,中序是第二次经过节点时访问,后序是第三次经过节点时访问。
其中较为特殊的是叶子节点,左孩子和右孩子都为空,访问空树时什么都不做就返回。
public static void p(Node h) {
if(h == null) return;
else {
System.out.print(h.val);
//遍历左子树
p(h.left);
//遍历右子树
p(h.right);
}
}
二、先/中/后序遍历(非递归)
(1)利用栈来进行实现,三种算法在理解的基础上进行记忆,作为一种模板,以后遇到具体问题,可以稍加改变,但是大致流程需要记住。
(2)看待二叉树的两种角度(递归与非递归)区别:
1、先序遍历
先将根节点压入栈中,方便之后进行追踪
一些规则:
1)弹出就打印
2)如有右孩子,压入右
3)如有左孩子,压入左
4)都没有则什么都不干
public static void p(Node head) {
if(head != null) {
//准备一个栈
Stack<Node> stack = new Stack<>();
//压入根节点
stack.add(head);
while(!stack.isEmpty()) {//栈不为空
Node node = stack.pop();//弹出节点
//访问节点(弹出就打印)
System.out.print(node.val);
if(node.right != null) {
stack.add(node.right);
}
if(node.left != null) {
stack.add(node.left);
}
//左右孩子为空就什么也不做
}
}
}
2、中序遍历(重要)
一些规则:
1)只要有左边界就把树的左边界从上往下依次压入栈中
2)当头节点走到空时,才走第2条逻辑,弹出节点,打印,来到右树上继续执行1)-》第i次与第i+1次循环。
特别的:对于叶子节点来说,本身就相当于左边界上的第一个节点。
注意:
借助这个算法,区别循环与递归。
public static void in(Node head) {
Node node = head;//令节点的初始值为head
Stack<Node> stack = new Stack<>();//创建一个栈
while(node != null || !stack.isEmpty()) {
//非递归,每次都需要进行节点非空的判断,而不是像递归,在最开始才进行判断
if(node != null) {//如果还有左节点
//压入左节点
stack.add(node);
node = node.left;//要一直往左走
}else {
node = stack.pop();
System.out.print(node.val);
node = node.right;
}
}
}
3、后序
(1)两个栈
头左右(先压右,再压左)
头右左(先压左,再压右)
左右头(将上一个序列反转,即本来是弹出就打印,现在改为压入另外一个栈)
public static void back(Node head) {
Stack<Node> stack1 = new Stack<>();//创建一个栈
Stack<Node> stack2 = new Stack<>();
if(head != null) {
stack1.add(head);//先压入头节点
while(!stack1.isEmpty()) {
Node node = stack1.pop();
stack2.add(node);
if(node.left != null) {
stack1.add(node.left);
}
if(node.right != null) {
stack1.add(node.right);
}
}
while(!stack2.isEmpty()) {
System.out.print(stack2.pop().val);
}
}
}
(2)一个栈
public static void back(Node h) {
if(h != null) {
Stack<Node> stack = new Stack<>();//创建一个栈
stack.add(h);
Node c = null;
while(!stack.isEmpty()) {
c = stack.peek();//不弹栈,c指向栈顶元素
if(c.left != null && h != c.left && h != c.right) {
stack.push(c.left);//左节点不为空且未被访问
}else if(c.right != null && h != c.right) {
stack.push(c.right);//右节点不为空且未被访问
}else {
System.out.print(stack.pop().val);//这里一定要弹出
h = c;//让h指向c,因为c其实就是刚刚被弹出的节点
}
}
}
}
三、层次遍历
利用队列来实现:
public static void level(Node head) {
if(head == null) return;
//创建队列
Queue<Node> queue =new LinkedList<>();
//先将头结点压入栈中,不然一开始没法弹,也没法开始
queue.add(head);
//队列不为空则循环
while(!queue.isEmpty()) {
//移出结点
Node node = queue.poll();
System.out.print(node.val);
if(node.left != null) {//该结点的左孩子不为空
queue.add(node.left);
}
//这里不能用else if,他们不是二选一的情况,对于一个结点是都要看左右结点
if(node.right != null) {//该结点的右孩子不为空
queue.add(node.right);
}//如果左右孩子都为空,那么直接进入下一层循环,接着弹出队头节点
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/16891.html