template<typename T, typename size_type=size_t>
class BinarySearchTree {
template<typename Seq>
void linear(Seq& seq) const;
}
template<typename T, typename size_type>
template<typename Seq>
void BinarySearchTree<T, size_type>::linear(Seq& seq) const {
if (!this->_size) return;
Node* cursor = this->root;
Node* cache = nullptr;
auto* path = new Stack<Node*>; // Stack<Node*> path;
console.log(path); // console.log(&path);
size_type count = this->_size;
while (count) {
path->push(cursor);
if (cursor->lnode != nullptr) {
cursor = cursor->lnode;
continue;
}
seq.push_back(path->pop()->data);
count--;
if (cursor->rnode != nullptr) {
cursor = cursor->rnode;
continue;
}
while (count) {
cache = path->pop();
seq.push_back(cache->data);
count--;
if (cache->rnode != nullptr) {
cursor = cache->rnode;
break;
}
}
}
delete path;
}
typedef BinarySearchTree<int> IBST;
int main() {
IBST bst;
std::vector<int> nums = {100, 2, 7, 4, -1, 0, 14, 8, 3, 124, 380, 266, 255};
for (auto item : nums) {
bst.append(item);
}
for (auto item : nums) {
if (!bst.exist(item)) {
console.log("Error");
break;
}
}
std::vector<int> sorted;
bst.linear(sorted);
sorted.clear();
bst.linear(sorted);
for (auto item : sorted) {
console.log(item);
}
}
上面是我实现的中序遍历 bst。
问题是那个path
变量,不论是在堆上、还是栈上,打印出来都是同一个地址,,,,,,,,
惊呆了。。。。