树的非递归遍历

原创
2016/11/03 15:19
阅读数 100

//定义树结构
struct Tree{
    int data;
    Tree *left;
    Tree *right;
    
    Tree(){
        this->data = 0;
        this->left = nullptr;
        this->right = nullptr;
    }
};

//递归先序遍历
void visit_recursive1(Tree *tree){
    if(tree){
        printf("data--->%d\n",tree->data);
        if(tree->left){
            visit_recursive1(tree->left);
        }
        
        if(tree->right){
            visit_recursive1(tree->right);
        }
    }
}

//递归中序遍历
void visit_recursive2(Tree *tree){
    if(tree){
        
        if(tree->left){
            visit_recursive2(tree->left);
        }
        
        printf("data--->%d\n",tree->data);
        
        if(tree->right){
            visit_recursive2(tree->right);
        }
    }
}

//非递归先序遍历
void visit1(Tree *tree){
    
    stack<Tree*> m_stack;
    
    Tree *cur = tree;
    
    while (cur) {
        printf("data--->%d\n",cur->data);
        m_stack.push(cur);
        
        cur = cur->left;
        
        while(!cur && !m_stack.empty()){
            
            cur = m_stack.top()->right;
            m_stack.pop();
        }
    }
}

//测试
int main(int argc, const char * argv[]) {
    Tree head;
    head.data = 1;
    
    
    Tree tree2;
    tree2.data = 2;
    
    Tree tree3;
    tree3.data = 3;
    
    Tree tree4;
    tree4.data = 4;
    
    Tree tree5;
    tree5.data = 5;
    
    Tree tree6;
    tree6.data = 6;
    
    head.left = &tree2;
    head.right = &tree3;
    
    tree2.left = &tree4;
    tree2.right = &tree5;
    
    tree3.left = &tree6;
    
    visit_recursive1(&head);
    visit_recursive2(&head);
    visit1(&head);
    
    return 0;
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部