我的coding练习
二叉树
L、D、R分别表示遍历左子树、访问根结点和遍历右子树
-
深度优先遍历:
- 先(前)序遍历：DLR ： 只是为了遍历
- 中序遍历：LDR ： 顺序输出
- 后序遍历：LRD ： 适合破坏性操作(delete等)
-
广度优先遍历:
- 层序遍历
仅有前序和后序遍历，不能确定一个二叉树，必须有中序遍历的结果
遍历
树节点
struct BTN{
int data_;
BTN* left_;
BTN* right_;
};
前序遍历：DLR
- 递归
void preOrderTraverse(BTN* p){
if(p == nullptr){
return;
}
print p->data_;
preOrderTraverse(p->left_);
preOrderTraverse(p->right_);
}
- 非递归
void preOrderTraverse(BTN* p){
if(p == nullptr){
return;
}
std::stack<BTN*> stack;
stack.push(p);
while(!stack.empty()){
p = stack.top();
stack.pop();
print(p->data_);
if(p->right_){
stack.push(p->right_);
}
if(p->left_){
stack.push(p->left_);
}
}
}
中序遍历：LDR
- 递归
void preOrderTraverse(BTN* p){
if(p == nullptr){
return;
}
preOrderTraverse(p->left_);
print p->data_;
preOrderTraverse(p->right_);
}
- 非递归
void inOrderTraverse(BTN* p){
std::stack<BTN*> stack;
while(p || !stack.empty()){
if(p){
stack.push(p);
p = p->left_;
}else{
p = stack.top();
stack.pop();
print(p->data_);
p = p->right_;
}
}
}
后序遍历：DLR
- 递归
void preOrderTraverse(BTN* p){
if(p == nullptr){
return;
}
preOrderTraverse(p->right_);
preOrderTraverse(p->left_);
print p->data_;
}
- 非递归
struct TmpBTN{
BTN* p_;
bool visited_;
TmpBTN(BTN* p):p_(p),visited_(false){}
};
void postorderTraversalNew(BTN *p)
{
std::stack< TmpBTN > s;
TmpBTN tmpBTN(p);
s.push(tmpBTN);
while(!s.empty())
{
tmpBTN = s.top();
s.pop();
if(tmpBTN.p_ == NULL)
continue;
if(tmpBTN.visited_)
{
print(tmpBTN.p_->data_);
}else{
//可以变换顺序为其他遍历
tmpBTN.visited_=true;
s.push(tmpBTN);
s.push(TmpBTN(tmpBTN.p_->right_));
s.push(TmpBTN(tmpBTN.p_->left_));
}
}
}
层序遍历：
void LevelOrderTraversal(BTN *p){
std::queue<BTN*> q;
q.push(p);
while(!q.empty()){
p = q.front();
q.pop();
if(p){
print(p->data_);
q.push(p->left_);
q.push(p->right_);
}
}
}
实现stack和queue：
简单版本: List实现
template<class T>
struct Node{
T data_;
Node* next_;
Node():next_(nullptr){}
Node(const T& data):data_(data),next_(nullptr){}
};
template<T>
class Stack{
public:
Stack():head_(nullptr){}
~Stack(){
while(head_){
Node<T>* toFreeNode = head_;
head_ = head_->next_;
delete toFreeNode;
}
}
bool empty(){
return head_ == nullptr;
}
void push(const T& data){
try{
Node<T>* newHead = new Node<T>(data);
newHead->next_=head_;
head_=newHead;
}catch(std::bad_alloc& exception){
throw exception;
}
}
void pop(){
if(empty()){
//TODO execption
}else{
Node<T>* toFreeNode = head_;
head_ = head_->next_;
delete toFreeNode;
}
}
T top(){
if(!empty()){
return head_->data_;
}else{
//TODO execption
}
}
private:
Node<T>* head_;
};
//如果是queue就增加一个Node<T>* tail_;
优化版本: vector实现
- 注意扩容与copy
template<class T>
class Queue{
public:
Queue(uint32_t max_size):
datas_(0),
max_size_(max_size),
size_(0),
head_(0),
tail_(0){
datas_ = new T[max_size_];
}
~Queue(){
delete[] datas_;
}
bool empty(){
return size_ == 0;
}
//TODO!
void push(const T& data){
if(size_ == max_size_){
std::cout << "push:" << data << " failed !" << std::endl;
return;
}
datas_[tail_] = data;
Move(tail_);
++size_;
}
void pop(){
if(empty()){
std::cout << "pop: failed !" << std::endl;
}else{
Move(head_);
--size_;
}
}
T top(){
if(!empty()){
return datas_[head_];
}else{
std::cout << "top: failed !" << std::endl;
return T();
}
}
private:
T* datas_;
uint32_t max_size_;
uint32_t size_;
int32_t head_;
int32_t tail_;
void Move(int32_t& cur){
if(cur+1 < max_size_){
++cur;
}else{
cur = 0;
}
}
};
对于stack和queue的实现在STL中都是使用deque完成的，内存分段分配结构有点复杂，后续再分析。
queue是一种“先进先出”的数据结构，可以对两端进行操作，但是只能在队列头部进行移除元素，只能在队列尾部新增元素，可以访问队列尾部和头部的元素，但是不能遍历容器，所以queue不需要设计自己的容器。在SGI STL的源码<stl_queue.h>的class queue设计中，它是基于某种容器作为底部结构的，默认容器是deque容器，用户也可以自己指定容器的类型。
queue可以以deque和list作为底层的容器
单元测试：
struct BTN{
int data_;
BTN* left_;
BTN* right_;
BTN(int data):
data_(data),
left_(nullptr),
right_(nullptr){}
};
// 4
// 2 6
// 1 3 7
BTN* createBTN(){
BTN* root = new BTN(4);
root->left_ = new BTN(2);
root->left_->left_ = new BTN(1);
root->left_->right_= new BTN(3);
root->right_ = new BTN(6);
root->right_->right_ = new BTN(7);
return root;
}
void print(int data){
std::cout << data << std::endl;
}
