这里写出三种儿叉查询树遍历的非递归写法,非常有意思。
preorder:先打印root,再left,最后right。
public static void BSTPreorderTraverse(Node node) {
if (node == null) {
return;
}
Stack<Node> s = new Stack<Node>();
s.push(node);
while (!s.empty()) {
node = s.pop();
System.out.println(node.toString());
if (node.rightChild != null) {s.push(node.rightChild);}
if (node.leftChild != null) {s.push(node.leftChild);}
}
}
Inorder: 先打印left,再root,最后right.
public static void BSTInorderTraverse(Node node) {
Stack<Node> s = new Stack<Node>();
while (!s.empty() || node != null) {
if (node != null) {
s.push(node);
node = node.leftChild;
} else {
node = s.pop();
System.out.println(node.toString());
node = node.rightChild;
}
}
}
Postorder: 先打印left,再right,最后root.
public static void BSTPostorderTraverse(Node node) {
if (node == null) {
return;
}
Stack<Node> s = new Stack<Node>();
Node cur = node;
while (true) {
if (cur != null) {
if (cur.rightChild != null) {
s.push(cur.rightChild);
}
s.push(cur);
cur = cur.leftChild;
continue;
}
if (s.empty()) {
return;
}
cur = s.pop();
if (cur.rightChild != null && !s.empty() && cur.rightChild == s.peek()) {
s.pop();
s.push(cur);
cur = cur.rightChild;
} else {
System.out.println(cur.toString());
cur = null;
}
}
}
class Node {
Node leftChild = null;
Node rightChild = null;
String name;
Node(String name) {
this.name = name;
}
@Override
public String toString() {
return name;
}
}
参考:http://en.wikipedia.org/wiki/Inorder
分享到:
相关推荐
1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)
采用llink-rlink方式存储二叉排序树,编写能够通过键盘输入建立二叉排序树,并在建立完立即在屏幕显示中序遍历结果的程序
三种遍历的非递归算法.doc
建立一位数组,然后以一位数组为例进行二叉排序树的中序遍历
二叉树先序中序后序三种遍历的非递归算法.doc
二叉排序树_层次遍历
数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版).
二叉树的创建与三种遍历的递归与非递归实现 包括二叉树的动态创建,前序遍历,中序遍历,后续遍历的递归与非递归方法的实现。
二叉搜索树的后序遍历序列.md
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
本人写的二叉寻找树的建立,遍历 用逗号分隔。。。。
二叉搜索树的后序遍历序列,二叉搜索树的后序遍历序列,python,jupyter
《剑指offer》面试题24的相关题目。输入一个整数数组,判断该数组是不是某二叉搜索树的前序遍历。假设输入的数组的任意两个数字互不相同。
二叉树先序、中序、后序三种遍历的非递归算法
二叉树前序、中序、后序三种遍历的非递归算法(C语言)
数据结构DFS深度优先遍历非递归算法实现,是自己编写的,可靠。
剑指 Offer 33. 二叉搜索树的后序遍历序列有空看下这个题解,感觉和我的思路不一样面试题33. 二叉搜索树的后序遍历序列(递归分治 / 单调栈,清晰图解)
1.先序遍历非递归算法#define maxsize 100typedef struct{ Bitree Elem[maxsize]; int top;}SqStack;void PreOrderUnrec(Bitree t){ SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=...
C语言实现二叉树的前序遍历(非递归),下载下来看看哦!