我的coding練習(xí)
二叉樹
L淋肾、D、R分別表示遍歷左子樹爸邢、訪問根結(jié)點(diǎn)和遍歷右子樹
-
深度優(yōu)先遍歷:
- 先(前)序遍歷：DLR ： 只是為了遍歷
- 中序遍歷：LDR ： 順序輸出
- 后序遍歷：LRD ： 適合破壞性操作(delete等)
-
廣度優(yōu)先遍歷:
- 層序遍歷
僅有前序和后序遍歷樊卓，不能確定一個(gè)二叉樹，必須有中序遍歷的結(jié)果
遍歷
樹節(jié)點(diǎn)
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{
//可以變換順序?yàn)槠渌闅v
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_);
}
}
}
實(shí)現(xiàn)stack和queue：
簡(jiǎn)單版本: List實(shí)現(xiàn)
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就增加一個(gè)Node<T>* tail_;
優(yōu)化版本: vector實(shí)現(xiàn)
- 注意擴(kuò)容與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;
}
}
};
對(duì)于stack和queue的實(shí)現(xiàn)在STL中都是使用deque完成的甲棍，內(nèi)存分段分配結(jié)構(gòu)有點(diǎn)復(fù)雜简识，后續(xù)再分析。
queue是一種“先進(jìn)先出”的數(shù)據(jù)結(jié)構(gòu)感猛，可以對(duì)兩端進(jìn)行操作七扰，但是只能在隊(duì)列頭部進(jìn)行移除元素，只能在隊(duì)列尾部新增元素陪白，可以訪問隊(duì)列尾部和頭部的元素颈走，但是不能遍歷容器，所以queue不需要設(shè)計(jì)自己的容器咱士。在SGI STL的源碼<stl_queue.h>的class queue設(shè)計(jì)中立由，它是基于某種容器作為底部結(jié)構(gòu)的，默認(rèn)容器是deque容器序厉，用戶也可以自己指定容器的類型锐膜。
queue可以以deque和list作為底層的容器
單元測(cè)試：
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;
}
