实现二叉树先序、中序和后序遍历

【说明】【题目】

【说明】

本文是左程云老师所著的《程序员面试代码指南》第三章中“分别用递归和非递归方式实现二叉树先序、中序和后序遍历”这一题目的C++复现。 本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

【题目】

用递归和非递归的方式，分别按照二叉树先序、中序和后序打印所有的节点。我们约定：先序遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根。

头文件： binarytree.h源文件： binarytree.cpp 源.cpp

binarytree.h

#pragma once #ifndef _BINARYTREE #define _BINARYTREE #include <iostream> using namespace std; class Node { public : Node(int data) { value = data; left = NULL; right = NULL; } public: int value; Node *left; Node *right; }; //递归版 void preOrderRecur(Node *head); void inOrderRecur(Node *head); void posOrderRecur(Node *head); #endif // !_BINARYTREE

binarytree.cpp

#include <iostream> #include "binarytree.h" void preOrderRecur(Node *head) { if (head == NULL) return; cout << head->value << endl; preOrderRecur(head->left); preOrderRecur(head->right); } void inOrderRecur(Node *head) { if (head == NULL) return; inOrderRecur(head->left); cout << head->value << endl; inOrderRecur(head->right); } void posOrderRecur(Node *head) { if (head == NULL) return; posOrderRecur(head->left); posOrderRecur(head->right); cout << head->value << endl; }

源.cpp

#include <iostream> #include "binarytree.h" using namespace std; //数组方式建立二叉树 void createBT(Node **head, int arr[], int len, int index = 0) { if (index > len - 1) return; (*head) = new Node(arr[index]); createBT(&((*head)->left), arr, len, 2 * index + 1); createBT(&((*head)->right), arr, len, 2 * index + 2); } int main() { int arr[] = { 1,2,3,4,5,6,7}; Node *head = NULL; createBT(&head, arr, 7); cout << "Using recursive method to achieve pre-order traversal:" << endl; preOrderRecur(head); cout << endl; cout << "Using recursive method to achieve in-order traversal:" << endl; inOrderRecur(head); cout << endl; cout << "Using recursive method to achieve pos-order traversal:" << endl; posOrderRecur(head); cout << endl; //cout << "hello 124" << endl; system("pause"); return 0; }