详解二叉树递归序遍历的多种实现方式

目录

自建栈

二叉树节点

递归随机建树

先序（preOrder traversal）：头左右

递归实现

非递归实现

非递归实现方法一

非递归实现方法二

中序（inOrder traversal）：左头右

递归实现

非递归实现

后序（postOrder traversal）：左右头

递归实现

非递归实现

非递归实现方法一

非递归实现方法二

---

自建栈

过程中需要利用栈的先进后出特点，以链式结构利用泛型编程实现一个栈，也可以用#include 使用STL里现有的stack类

templatestruct node
{
	T data; node*next;
	node(T&t):data(t),next(nullptr){}
};
templateclass myStack
{
	node*head;
public:
	myStack() { T t(0); head = new node(t); head->next = nullptr; }
	myStack(T& t) { head = new node(t); head->next = new node(t); }
	bool empty() { return head->next == nullptr; }
	void push(T& t) {
		node* ptr = new node(t);
		if (head->next == nullptr) head->next = ptr;
		else {
			ptr->next = head->next;
			head->next = ptr;
		}
	}
	void push(node* ptr) {
		if (head->next == nullptr) head->next = ptr;
		else {
			ptr->next = head->next->next;
			head->next = ptr;
		}
	}
	void pop() { if (head->next == nullptr) cout << "the stack is empty !" << endl;
	else { node* ptr = head->next; head->next = head->next->next; delete ptr; }
	}
	T top() { return head->next->data; }
	node* topPtr() { return head->next; }
	~myStack(){
		while (head->next != nullptr) { node* ptr = head->next->next; delete head->next; head->next = ptr; }
	}
};

二叉树节点

struct treeNode
{
	double value;
	treeNode*left, *right;
	treeNode(double d) :value(d) { left = right = nullptr; }
};

递归随机建树

用于简单生成测试自己递归序程序的正确性的数据

void buildTree(treeNode**head,double n)
{
	if (n > 25) return;
	*head = new treeNode(n);
	buildTree(&(*head)->left, 2 * n);
	buildTree(&(*head)->right, 2 * n + 1);
}

先序（preOrder traversal）：头左右 递归实现

遍历实现很简单，只要将打印行为/压入队列（先进先出）的行为放在前面，这里不赘述

void preOrderRecur(treeNode*head)
{
	if (head == nullptr) return;
	cout << head->value <<'\t';
	preOrderRecur(head->left);
	preOrderRecur(head->right);
}

非递归实现 非递归实现方法一

先序保证先头，所以先压入树的根，然后d出，若栈顶元素有左、右孩子，则按照先右后左的顺序压入栈中，直至栈中为空。代码如下：

void preOrderUnrec1(treeNode*head)
{
	myStack s(head);
	while (!s.empty())
	{
		treeNode* top = s.top(); s.pop();
		cout << top->value << '\t';
		if (top->right != nullptr) s.push(top->right);
		if (top->left != nullptr) s.push(top->left);
	}
}

非递归实现方法二

弱化“右”的概念，将二叉树视为“头左”的集合，若head存在左孩子则不断压入，若没有左孩子了则此时的head为d出结点的右孩子，再次进入“头左”的循环，打印行为放在入栈时。代码如下：

void preOrderUnrec2(treeNode*head)
{
	myStacks;
	while (!s.empty() || head != nullptr)
	{
		while (head != nullptr) { s.push(head); cout << s.top()->value << '\t'; head = head->left; }
		head = s.top()->right; s.pop();
	}
}

中序（inOrder traversal）：左头右 递归实现

中序的递归实现即先遍历完左孩子再打印

void inOrderRecur(treeNode*head)
{
	if (head == nullptr) return;
	inOrderRecur(head->left);
	cout << head->value << '\t';
	inOrderRecur(head->right);
}

非递归实现

非递归实现参考先序遍历非递归方法二的思路，仍将二叉树视为“左头”的集合，但将打印行为放在出栈的时候，实现先左后头。代码如下：
 

void inOrderUnrec(treeNode*head)
{
	myStacks(head); head = head->left;
	while (!s.empty()||head!=nullptr)
	{
		while (head!= nullptr) { s.push(head);  head = head->left; }
		cout << s.top()->value << '\t'; 
		head = s.top()->right; s.pop();
	}
}

后序（postOrder traversal）：左右头 递归实现

递归实现后序即打印行为在右孩子遍历完之后

void postOrderRecur(treeNode*head)
{
	if (head == nullptr) return;
	postOrderRecur(head->left);
	postOrderRecur(head->right);
	cout << head->value << '\t';
}

非递归实现 非递归实现方法一

参考非递归实现先序遍历的方法一，利用两个栈，对s1压入头结点，d出栈顶元素压入s2，若其存在左、右孩子则先左后右（先序为先右后左）压入s1中，如此循环至s1为空，顺序打印栈s2中元素即可。代码如下：

void postOrderUnrec1(treeNode*head) 
{
	myStacks1(head), s2;
	while (!s1.empty())
	{
		treeNode* top = s1.top(); s2.push(top); s1.pop();
		if (top->left != nullptr) s1.push(top->left);
		if (top->right != nullptr) s1.push(top->right);
	}
	while (!s2.empty()) { cout << s2.top()->value << '\t'; s2.pop(); }
}

非递归实现方法二

后序遍历也可以用减少空间消耗的办法。参考先序非递归遍历方法二，当遍历完左孩子后，会先经历头结点，此时可以增加一个出栈的判断条件，即是否经历过了它的右孩子，若不存在右孩子或者已经历过则d出，否则压入它的右孩子。因为左右头的d出必然连续，这个判断可以用一个preNode变量来记录上次出栈的元素。代码如下：

void postOrderUnrec2(treeNode*head)
{
	myStacks;
	treeNode* preNode=nullptr,*top;
	while (!s.empty()||head!=nullptr)
	{
		while (head != nullptr) { s.push(head); preNode = head; head = head->left; }
		top = s.top();
		if (top->right == nullptr || top->right == preNode) { cout << top->value << '\t'; preNode = top; s.pop(); }
		else head = top->right;
	}
}