C******x
发帖数: 91 | 1 卡了一阵子了
知道这里藏龙卧虎, 跪求一个bst中序遍历 c++ class iterator代码参考
也可以私信我, 还请不吝赐教
写了很多次, 但是对于c++迭代器还是不熟悉, c++想写好着实不容易 汗
我写成下面这样, 看起来有点像java的(不对也请指出), c++的该怎么写啊, 跪求指导
和意见
class BSTreeInorderIterator
{
private:
stack st;
public:
BSTreeInorderIterator(BSTNode* root)
{
push_left(root);
}
bool hasNext()
{
return !st.empty();
}
BSTNode* next()
{
BSTNode* node = st.top();
st.pop();
push_left(node->right);
return node;
}
private:
void push_left(BSTNode* p)
{
while (p) {
st.push(p);
p = p->left;
}
}
} |
p*****3
发帖数: 488 | 2 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet->pRgt);
return pRet;
}
private:
void PushLefts(NODE* pNode)
{
while (NULL != pNode)
{
m_stk.push(pNode);
pNode = pNode->pLft;
}
}
private:
stack m_stk;
}; |
w**x
发帖数: 362 | 3 The next() should be operator() ++
No GetIter() function.
No iter in class. |
C******x
发帖数: 91 | 4
学了中！ 多谢赐教:)
【在 p*****3 的大作中提到】
: struct NODE
: {
: int nVal;
: NODE* pLft;
: NODE* pRgt;
: NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
: };
: class BTIterator
: {
: public:
|
C******x
发帖数: 91 | 5 受教了~
可能的话，拜托给个具体的signature~
多谢～
【在 w**x 的大作中提到】
: The next() should be operator() ++
: No GetIter() function.
: No iter in class.
|
w**x
发帖数: 362 | 6 your code is not C++, but C.
No constructor.
No operator()++.
No destructor.
No current iter.
why void PushLefts(NODE* pNode) ?
Left is left not lefts.
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet->pRgt);
return pRet;
}
private:
void PushLefts(NODE* pNode)
{
while (NULL != pNode)
{
m_stk.push(pNode);
pNode = pNode->pLft;
}
}
private:
stack m_stk;
}; |
C******x
发帖数: 91 | 7 恩 确实不是c++ 所以来求教了～ 多谢大牛赐教！
【在 w**x 的大作中提到】
: your code is not C++, but C.
: No constructor.
: No operator()++.
: No destructor.
: No current iter.
: why void PushLefts(NODE* pNode) ?
: Left is left not lefts.
: struct NODE
: {
: int nVal;
|
w**x
发帖数: 362 | 8 不牛，你自己可以按我说得去一个一个写。需要有个iter in private. |
w******j
发帖数: 185 | 9 来个java的吧，带parent pointer和不带的，preorder和inorder的
import java.util.NoSuchElementException;
import java.util.Stack;
public class BST {
private Node root;
private static class Node {
int key;
Node left, right, parent;
Node(int key) {
this.key = key;
}
}
public BST(){
}
public BSTIterator inorderIterator() {
return new InorderIterator();
}
public BSTIterator preorderIterator() {
return new PreorderIterator();
}
public BSTIterator postorderIterator() {
return new PostorderIterator();
}
public BSTIterator preorderIterator1() {
return new Preorder();
}
public BSTIterator inorderIterator1() {
return new Inorder();
}
private class Inorder implements BSTIterator {
Stack stack = new Stack();
Inorder() {
Node leftmost = root;
while (leftmost != null){
stack.push(leftmost);
leftmost = leftmost.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
if (!hasNext())
throw new NoSuchElementException();
Node x = stack.pop();
int key = x.key;
if (x.right != null){
stack.push(x.right);
Node left = x.right.left;
while(left != null)
{
stack.push(left);
left = left.left;
}
}
return key;
}
}
private class Preorder implements BSTIterator {
Stack stack = new Stack();
Preorder() {
if (root != null)
stack.push(root);
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
if (!hasNext())
throw new NoSuchElementException();
Node x = stack.pop();
int key = x.key;
if (x.right != null)
stack.push(x.right);
if (x.left != null)
stack.push(x.left);
return key;
}
}
private class InorderIterator implements BSTIterator {
private Node nextNode;
private InorderIterator() {
// The traversal starts with the smallest node
Node leftmost = root;
while(leftmost != null && leftmost.left != null)
leftmost = leftmost.left;
nextNode = leftmost;
}
public boolean hasNext() {
return (nextNode != null);
}
public int next() {
if (nextNode == null)
throw new NoSuchElementException();
// Store a copy of the key to be returned.
int key = nextNode.key;
if(nextNode.right != null)
{
nextNode = nextNode.right;
while(nextNode.left != null)
nextNode = nextNode.left;
}
else
{
Node child = nextNode;
Node parent = nextNode.parent;
while(parent != null && parent.right == child)
{
child = parent;
parent = parent.parent;
}
if (parent == null)
nextNode = null; // the traversal is complete
else
nextNode = parent;
}
return key;
}
}
/*** inner class for a preorder iterator ***/
private class PreorderIterator implements BSTIterator {
private Node nextNode;
private PreorderIterator() {
// The traversal starts with the root node.
nextNode = root;
}
public boolean hasNext() {
return (nextNode != null);
}
public int next() {
if (nextNode == null)
throw new NoSuchElementException();
// Store a copy of the key to be returned.
int key = nextNode.key;
// Advance nextNode.
if (nextNode.left != null)
nextNode = nextNode.left;
else if (nextNode.right != null)
nextNode = nextNode.right;
else {
// We've just visited a leaf node.
// Go back up the tree until we find a node
// with a right child that we haven't seen yet.
Node parent = nextNode.parent;
Node child = nextNode;
while (parent != null
&& (parent.right == child || parent.right == null)) {
child = parent;
parent = parent.parent;
}
if (parent == null)
nextNode = null; // the traversal is complete
else
nextNode = parent.right;
}
return key;
}
}
public static void main(String[] args) {
BST bst = new BST();
bst.root = new Node(15);
bst.root.left = new Node(12);
bst.root.left.parent = bst.root;
bst.root.left.left = new Node(6);
bst.root.left.left.parent = bst.root.left;
bst.root.left.right = new Node(14);
bst.root.left.right.parent = bst.root.left;
bst.root.left.left.right = new Node(10);
bst.root.left.left.right.parent = bst.root.left.left;
bst.root.left.left.right.left = new Node(9);
bst.root.left.left.right.left.parent = bst.root.left.left.right;
bst.root.right = new Node(18);
bst.root.right.parent = bst.root;
bst.root.right.right = new Node(25);
bst.root.right.right.parent = bst.root.right;
bst.root.right.right.left = new Node(21);
bst.root.right.right.left.parent = bst.root.right.right;
BSTIterator preorder = bst.preorderIterator();
BSTIterator preorder1 = bst.preorderIterator1();
while(preorder.hasNext())
System.out.print(preorder.next() + " ");
System.out.println();
while(preorder1.hasNext())
System.out.print(preorder1.next() + " ");
System.out.println();
BSTIterator inorder = bst.inorderIterator();
while(inorder.hasNext())
System.out.print(inorder.next() + " ");
System.out.println();
BSTIterator inorder1 = bst.inorderIterator1();
while(inorder1.hasNext())
System.out.print(inorder1.next() + " ");
System.out.println();
}
}
public interface BSTIterator {
boolean hasNext();
int next();
} |
r*********n
发帖数: 4553 | 10 要写一个真正的C++ iterator不容易，对于bst，bidirectional iterator应该就够了。
//T is the type of tree node value
template class BSTIterator: public std::iterator
iterator_tag, T> {
//....
public:
//...
BSTIterator& operator++();
BSTIterator opterator++(int);
BSTIterator& operator--();
BSTIterator operator--(int);
T& operator*();
bool operator==(const BSTIterator&);
bool operator!=(const BSTIterator&);
};
至少把上面几个关键的operator overload之后才差不多吧。 |
C******x
发帖数: 91 | 11 恩, 接口清晰很多了,正在临摹中。。。 多谢指教！
具体到算法，
对于没有parent指针的tree，
对于++运算符 , 两个方案，
1 迭代器中维护一个栈，好处是遍历一次的复杂度是O(n)， 坏处是空间， 如果是后
缀加加， 每次都要复制一遍栈~ 如果不小心用后缀++遍历, 实际复杂度是O(n^2)，用
前缀++没有
这个问题, 复杂度还是O(n)
2 每次++，都调用next函数，要么找右子节点的最小值，要么从root找起，找到下一
个节点~ 最坏复杂度还是O(n^2)
另外，如果还是--， 还得额外维护一个栈~
对于有parent指针的tree
方便的找next就好了，遍历一遍的平均复杂度应该是O(n)~ 最坏的情况下貌似也是O(
n)[不是非常确定]
问题:
知道板上有人面试面到这个题，貌似还是高频
请问到底到写到什么程度，要求所有的接口，然后写出上面的那种case啊？
网上找到一些代码，正在修改~
感觉如果真要写清楚，还要定义Node，BSTree, 然后才能定义Iterator， 不仅仅是单
纯的非递归中序遍历二叉树~
了。
【在 r*********n 的大作中提到】
: 要写一个真正的C++ iterator不容易，对于bst，bidirectional iterator应该就够了。
: //T is the type of tree node value
: template class BSTIterator: public std::iterator: iterator_tag, T> {
: //....
: public:
: //...
: BSTIterator& operator++();
: BSTIterator opterator++(int);
: BSTIterator& operator--();
|
