2021-10-15

二叉树遍历@改编自左神java(c++版本)

这是改自左神二叉树遍历Java版本程序，使用递归遍历，之后会写一篇非递归遍历。

需要注意Java没有指针，而c++版本二叉树结构需要用到指针。
左右子树的指针默认为NULL，不然遍历最后会出错。

struct Node {
	int value=0;
	Node* left = NULL；
	Node* right = NULL;

	Node(int data) {
		value = data;
	}
};

中左右

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

左中右

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

左右中

static void posOrderRecur(Node* head) {
		if (head == NULL) {
			return;
		}
		posOrderRecur((*head).left);
		posOrderRecur(head->right);
		cout << head->value << " ";
	}

#include 
using namespace std;
struct Node {
	int value=0;
	Node* left=NULL;
	Node* right = NULL;

	Node(int data) {
		value = data;
	}
};
class Code_01_PreInPosTraversal
{
public :
	
	static void preOrderRecur(Node* head) {
		if (head == NULL) {
			return;
		}
		cout << head->value << " ";
		preOrderRecur(head->left);
		preOrderRecur(head->right);
	}
	static void inOrderRecur(Node* head)
	{
		if (head == NULL) {
			return;
		}		
		inOrderRecur(head->left);
		cout << head->value << " ";
		inOrderRecur(head->right);
	}
	static void posOrderRecur(Node* head) {
		if (head == NULL) {
			return;
		}
		posOrderRecur((*head).left);
		posOrderRecur(head->right);
		cout << head->value << " ";
	}
};

int main()
{
	Code_01_PreInPosTraversal PreInPosTraversal;
	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);

	// recursive
	printf("==============recursive==============n");
	printf("pre-order: ");
	PreInPosTraversal.preOrderRecur(head);
	cout << "n";
	printf("in-order: ");
	PreInPosTraversal.inOrderRecur(head);
	cout << "n";
	printf("pos-order: ");
	PreInPosTraversal.posOrderRecur(head);
	cout << "n";
}