二叉树的c++实现及遍历（包括递归、非递归和morris遍历）

本文主要解决问题

输入一个数组，按照层序遍历的方式生成二叉树。
实现树的前中后序遍历：递归方式，非递归方式，和morris遍历方式。

头文件（stdafx.h）

// stdafx.h : 标准系统包含文件的包含文件，
// 或是经常使用但不常更改的
// 特定于项目的包含文件
//
#pragma once
#include "targetver.h"
#include 
#include 
// TODO:  在此处引用程序需要的其他头文件
#include 
#include 
using namespace std;

二叉树类的定义（BiTree.h）

#ifndef BITREE_H_INCLUDE
#define BITREE_H_INCLUDE

#include "stdafx.h"

struct BiNode{
public:
	int value;
	BiNode *left, *right;
};

class BiTree{
private:
	BiNode *root;
	int *a;
	int n; //二叉树节点个数
	int start;
	void Release(BiNode *root); //析构函数
	BiNode *create(int *a, int n, int start); //生成树
	void PreOrder_R(BiNode *root); //递归前序遍历
	void InOrder_R(BiNode *root); //递归中序遍历
	void PosOrder_R(BiNode *root); //递归后序遍历
	void PreOrder(BiNode *root); //非递归前序遍历
	void InOrder(BiNode *root); //非递归中序遍历
	void PosOrder(BiNode *root); //非递归后序遍历
	void morris(BiNode *root); //morris遍历
	void morrisPre(BiNode *root); //morris前序遍历
	void morrisIn(BiNode *root); //morris中序遍历
	void morrisPos(BiNode *root); //morris后序遍历
public:
	BiTree(){ root = nullptr; a = nullptr; n = 0; start = 0; } //构造函数
	~BiTree(){ Release(root); } //析构函数
	void CreateBiTree(int *a, int n); //生成树
	void PreOrder_R(){ PreOrder_R(root); cout << endl; } //递归前序遍历
	void InOrder_R(){ InOrder_R(root); cout << endl; } //递归中序遍历
	void PosOrder_R(){ PosOrder_R(root); cout << endl; } //递归后序遍历
	void PreOrder(){ PreOrder(root); cout << endl; } //非递归前序遍历
	void InOrder(){ InOrder(root); cout << endl; } //非递归中序遍历
	void PosOrder(){ PosOrder(root); cout << endl; } //非递归后序遍历
	void morris(){ morris(root); cout << endl; } //morris遍历
	void morrisPre(){ morrisPre(root); cout << endl; } //morris前序遍历
	void morrisIn(){ morrisIn(root); cout << endl; } //morris中序遍历
	void morrisPos(){ morrisPos(root); cout << endl; } //morris后序遍历
};


#endif

二叉树类的成员函数（BiTree.cpp）

非递归实现前序遍历的思想为：
先把头结点压栈
1)从栈中弹出一个节点
2)打印这个节点
3)把这个节点的右孩子和左孩子依次压栈
4)重复以上三个过程

非递归实现中序遍历
先把头结点压栈
1)将每棵子树的整棵树的左边界压栈
2)依次出栈的过程中打印
3)对出栈节点的右树周而复始

非递归实现后序遍历
建立两个栈，第二个栈作为收集栈
先把头结点压栈
1)从栈中弹出一个节点
2)压入收集栈
3)把这个节点的左孩子和右孩子依次压栈
4)重复以上三个过程
最后将收集栈中的节点全部弹出并打印

morris遍历
听左程云老师的课程做的笔记

morris前序遍历
1)只到达一次的直接打印
2)可到达两次的只打印第一次

morris中序遍历
1)只到达一次的直接打印
2)可到达两次的只打印第二次

morris后序遍历
1)可两次到达的节点，在第二次到达时，逆序打印左树右边界
2)单独打印整棵树的右边界

以下是代码展示：

#include "stdafx.h"
#include "BiTree.h"

//生成树
BiNode *BiTree::create(int *a, int n, int start){
	if (a[start] == '#'){
		return nullptr;
	}
	BiNode *root = new BiNode;
	root->value = a[start];
	root->left = nullptr;
	root->right = nullptr;
	int lnode = 2 * start + 1;
	int rnode = 2 * start + 2;
	if (lnode > n - 1) root->left = nullptr;
	else root->left = create(a, n, lnode);
	if (rnode > n - 1) root->right = nullptr;
	else root->right = create(a, n, rnode);
	return root;
}

//生成树
void BiTree::CreateBiTree(int *a, int n){
	root = create(a, n, 0);
}

//析构函数
void BiTree::Release(BiNode *root){
	if (root != nullptr){
		Release(root->left);
		Release(root->right);
		delete root;
	}
}

//递归前序遍历
void BiTree::PreOrder_R(BiNode *root){
	if (root){
		cout << root->value << " ";
		PreOrder_R(root->left);
		PreOrder_R(root->right);
	}
}

//递归中序遍历
void BiTree::InOrder_R(BiNode *root){
	if (root){
		InOrder_R(root->left);
		cout << root->value << " ";
		InOrder_R(root->right);
	}
}

//递归后序遍历
void BiTree::PosOrder_R(BiNode *root){
	if (root){
		PosOrder_R(root->left);
		PosOrder_R(root->right);
		cout << root->value << " ";
	}
}

//非递归前序遍历
void BiTree::PreOrder(BiNode *root){
	if (root != nullptr){
		stack istack;
		istack.push(root);
		while (!istack.empty()){
			cout << istack.top()->value << " "; //弹出栈顶元素并打印
			BiNode* root = istack.top();
			istack.pop();
			if (root->right != nullptr){ //先压右树
				istack.push(root->right);
			}
			if (root->left != nullptr){ //再压左树
				istack.push(root->left);
			}
		}
	}
}

//非递归中序遍历
void BiTree::InOrder(BiNode *root){
	if (root != nullptr){
		stack istack;
		while (!istack.empty() || root != nullptr){
			if (root != nullptr){ //不停把左边界入栈
				istack.push(root);
				root = root->left;
			}
			else
			{
				cout << istack.top()->value << " "; //然后出栈并打印，再对出栈节点的右树周而复始
				root = istack.top();
				istack.pop();
				root = root->right;
			}
		}
	}
}

//非递归后序遍历
void BiTree::PosOrder(BiNode *root){
	if (root != nullptr){
		stack s1;
		stack s2;
		s1.push(root);
		while (!s1.empty()){
			s2.push(s1.top()); //原本打印的节点压入收集栈s2
			BiNode* root = s1.top();
			s1.pop();
			if (root->left != nullptr){ //先压左
				s1.push(root->left);
			}
			if (root->right != nullptr){ //再压右
				s1.push(root->right);
			}
		}
		while(!s2.empty()){
			cout << s2.top()->value << " ";
			s2.pop();
		}
	}
}

//morris遍历
void BiTree::morris(BiNode *root){
	if (root == nullptr)return;
	BiNode* cur = root;
	BiNode* mostRight = nullptr;
	while (cur != nullptr){
		cout << cur->value << " ";
		mostRight = cur->left;
		//如果有左孩子，找到左子树上的最右节点mostRight
		if (mostRight != nullptr){
			//找到左子树最右节点mostRight
			while (mostRight->right != nullptr&&mostRight->right != cur){
				mostRight = mostRight->right;
			}
			//若morris右指针指向空，让其指向cur，cur左移
			if (mostRight->right == nullptr){
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//若morris右指针指向cur，让其指向null，cur右移
			else
			{
				mostRight->right = nullptr;
			}
		}
		//没有左孩子,cur向右移动
		cur = cur->right;
	}
}

//morris前序遍历（只到达一次的直接打印，可到达两次的只打印第一次）
void BiTree::morrisPre(BiNode *root){
	if (root == nullptr)return;
	BiNode* cur = root;
	BiNode* mostRight = nullptr;
	while (cur != nullptr){
		mostRight = cur->left;
		if (mostRight != nullptr){
			while (mostRight->right != nullptr&&mostRight->right != cur){
				mostRight = mostRight->right;
			}
			if (mostRight->right == nullptr){
				//第一次到达
				cout << cur->value << " ";
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			else{
				//第二次到达
				mostRight->right = nullptr;
			}
		}
		else{
			//只到达一次的直接打印
			cout << cur->value << " ";
		}
		cur = cur->right;
	}
}

//morris中序遍历（只到达一次的直接打印，可到达两次的只打印第二次）
void BiTree::morrisIn(BiNode *root){
	if (root == nullptr)return;
	BiNode* cur = root;
	BiNode* mostRight = nullptr;
	while (cur != nullptr){
		mostRight = cur->left;
		//如果有左孩子，找到左子树上的最右节点mostRight
		if (mostRight != nullptr){
			//找到左子树最右节点mostRight
			while (mostRight->right != nullptr&&mostRight->right != cur){
				mostRight = mostRight->right;
			}
			//若morris右指针指向空，让其指向cur，cur左移
			if (mostRight->right == nullptr){
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			//若morris右指针指向cur，让其指向null，cur右移
			else
			{
				mostRight->right = nullptr;
			}
		}
		cout << cur->value << " ";
		//没有左孩子,cur向右移动
		cur = cur->right;
	}
}

//morris后序遍历
//将边界逆序
BiNode* reverseEdge(BiNode* from){
	BiNode* pre = nullptr;
	BiNode* next = nullptr;
	while (from != nullptr){
		next = from->right;
		from->right = pre;
		pre = from;
		from = next;
	}
	return pre;
}

//逆序打印边界
void printEdge(BiNode* X){
	BiNode* tail = reverseEdge(X);
	BiNode* cur = tail;
	while (cur != nullptr){
		cout << cur->value << " ";
		cur = cur->right;
	}
	reverseEdge(tail);
}

//可两次到达的节点，在第二次到达时，逆序打印左树右边界
//单独打印整棵树的右边界
void BiTree::morrisPos(BiNode *root){
	if (root == nullptr)return;
	BiNode* cur = root;
	BiNode* mostRight = nullptr;
	while (cur != nullptr){
		mostRight = cur->left;
		if (mostRight != nullptr){
			while (mostRight->right != nullptr&&mostRight->right != cur){
				mostRight = mostRight->right;
			}
			if (mostRight->right == nullptr){
				mostRight->right = cur;
				cur = cur->left;
				continue;
			}
			else{
				mostRight->right = nullptr;
				printEdge(cur->left);
			}
		}
		cur = cur->right;
	}
	printEdge(root);
}

测试（main.cpp）

// Tree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "BiTree.h"

int main()
{
	int a[9] = { 1, 2, 3, 4, 5, 6, 7, '#', 8 };
	BiTree tree;
	tree.CreateBiTree(a, 9);

	cout << "递归前序遍历：" << endl;
	tree.PreOrder_R();
	cout << "递归中序遍历：" << endl;
	tree.InOrder_R();
	cout << "递归后序遍历：" << endl;
	tree.PosOrder_R();

	cout << "非递归前序遍历：" << endl;
	tree.PreOrder();
	cout << "非递归中序遍历：" << endl;
	tree.InOrder();
	cout << "非递归后序遍历：" << endl;
	tree.PosOrder();

	cout << "morris遍历：" << endl;
	tree.morris();
	cout << "morris前序遍历：" << endl;
	tree.morrisPre();
	cout << "morris中序遍历：" << endl;
	tree.morrisIn();
	cout << "morris后序遍历：" << endl;
	tree.morrisPos();

	system("pause");
	return 0;
}

二叉树的c++实现及遍历（包括递归、非递归和morris遍历）

C/C++/C#相关栏目本月热门文章