二叉树遍历（非递归）

文章目录

• 二叉树遍历非递归版本
• • • 前序遍历
    • 中序遍历
    • 后序遍历
    • 层序遍历
    • 层序遍历+map记录高度

二叉树遍历非递归版本 前序遍历

如果右侧不为空，则右侧进栈，随后是左侧进栈。

因为栈是先进后出，所以实现先序遍历。

void aaa2(node *head){
	if(head==NULL)return;
	stack<node> s;
	s.push(*head);
	while(!s.empty()){
		node a = s.top();s.pop();
		cout<<a.val<<" ";
		if(a.right!=NULL){
			s.push(*a.right);
		}
		if(a.left!=NULL){
			s.push(*a.left);
		}
	}
}

中序遍历

---

1. 先把左侧全部压栈
2. 栈中d出并打印
3. 右子树重复①

void bbb2(node *head){
	if(head==NULL)return;
	stack<node> s;
	node *cur = head;
	
	while(cur!=NULL||!s.empty()){
		if(cur!=NULL){
			s.push(*cur);
			cur = cur->left;
		}else{
			cur = &s.top();
			s.pop();
			cout<<cur->val<<" ";
			cur = cur->right;
		}
	}
}

后序遍历

---

1. 先左边进栈 再右边进栈
2. 此时输出的顺序为 中右左
3. 不输出，再进栈，之后输出，顺序为左中右

void ccc2(node *head){
	if(head==NULL)return;
	stack<node> s1;
	stack<node> s2;
	s1.push(*head);
	node top;
	while(!s1.empty()){
		top = s1.top();
		s1.pop();
		s2.push(top);
		if(top.left!=NULL){
			s1.push(*top.left);
		}
		if(top.right!=NULL){
			s1.push(*top.right);
		}
	}
	while(!s2.empty()){
		top = s2.top();s2.pop();
		cout<<top.val<<" ";
	}
}

层序遍历

---

1. 头节点入栈
2. pop()并输出栈顶
3. 先左后右

void ddd1(node *head){
	if(head==NULL)return;
	queue<node> q1;
	q1.push(*head);

	while(!q1.empty()){
		node top = q1.front();q1.pop();
		
		cout<<top.val<<" ";
		
		if(top.left!=NULL){
			q1.push(*top.left);
		}
		if(top.right!=NULL){
			q1.push(*top.right);
		}
	}
}

层序遍历+map记录高度

map 用来记录结点对应的高度

void ddd2(node *head){
	if(head==NULL)return;
	queue<node*> q1;
	map<node*, int> maps;
	q1.push(head);
	maps[head] = 1;
	
	while(!q1.empty()){
		node* top = q1.front();q1.pop();
		int level = maps[top];
		cout<<"数值："<<top->val<<",层数："<<level<<endl;
		
		if(top->left!=NULL){
			q1.push(top->left);
			maps[top->left] = level+1; 
		}
		if(top->right!=NULL){
			q1.push(top->right);
			maps[top->right] = level+1;
		}
	}
}