自学数据结构和算法（5）-Toy模板网

这篇具有很好参考价值的文章主要介绍了自学数据结构和算法（5）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉树的遍历

分为先序、中序、和后序遍历。

这三种遍历都可以由递归序来得到：

（1）先序遍历（也是二叉树的深度优先遍历）是第一次到某个结点才打印；

（2）中序遍历是第二次到某个结点才打印；

（3）后序遍历是第三次到某个结点才打印。

自学数据结构和算法（5）,数据结构与算法,算法,数据结构

利用递归实现二叉树三序遍历十分简单，只需更换一下输出的顺序，如下：

#include<iostream>
using namespace std;

class Node{
public:
	int value;
	Node* left = NULL;
	Node* right = NULL;
//由于下面写了带形参的构造函数，因此无参的
//C++不再提供默认构造函数，导致上面的两个
//指针的初始值不为NULL，因此要手动赋值
//或写无参构造函数 
	Node(int a){
		value = a;
	}
};

void preOrder(Node* head){
	if(head == NULL)
	return;
	cout<<head->value<<' ';
	preOrder(head->left);
	preOrder(head->right);
}

void inOrder(Node* head){
	if(head == NULL)
	return;
	inOrder(head->left);
	cout<<head->value<<' ';
	inOrder(head->right);
}

void lastOrder(Node* head){
	if(head == NULL)
	return;
	lastOrder(head->left);
	lastOrder(head->right);
	cout<<head->value<<' ';
} 

int main()
{
	Node* head = new Node(5);
	head->left = new Node(3);
	head->right = new Node(8);
	head->left->left = new Node(2);
	head->left->right = new Node(4);
	head->left->left->left = new Node(1);
	head->right->left = new Node(7);
	head->right->left->left = new Node(6);
	head->right->right = new Node(10);
	head->right->right->left = new Node(9);
	head->right->right->right = new Node(11);
	preOrder(head);
	cout<<endl;
	inOrder(head);
	cout<<endl;
	lastOrder(head);
	return 0;
}

这是上面建的树自学数据结构和算法（5）,数据结构与算法,算法,数据结构