# 树的非递归遍历

2016/11/03 15:19

//定义树结构
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 tree2;
tree2.data = 2;

Tree tree3;
tree3.data = 3;

Tree tree4;
tree4.data = 4;

Tree tree5;
tree5.data = 5;

Tree tree6;
tree6.data = 6;

tree2.left = &tree4;
tree2.right = &tree5;

tree3.left = &tree6;

return 0;
}

0
0 收藏

### 作者的其它热门文章 0 评论
0 收藏
0   