左神算法学习日记——二叉树（一）

发布时间：2023-05-07 13:00
二叉树遍历，非递归版
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;


class node
{
public:
	char num;
	node* left;
	node* right;
	node()
	{
		num = 0;
		left = NULL;
		right = NULL;
	}
	node(char n)
	{
		num = n;
		left = NULL;
		right = NULL;
	}
};

void pre(node* head)
{
	if (head != NULL)
	{
		stack sta;
		sta.push(head);
		while (!sta.empty())
		{
			head = sta.top();
			cout << head->num << \"  \";
			sta.pop();
			if (head->right)
				sta.push(head->right);
			if (head->left)
				sta.push(head->left);
		}
	}
	cout << endl;
}

void mid(node* head)
{
	if (head != NULL)
	{
		stack sta;
		while (!sta.empty()||head)
		{
			if (head)
			{
				sta.push(head);
				head = head->left;
			}
			else
			{
				head = sta.top();
				sta.pop();
				cout << head->num << \"  \";
				head = head->right;
			}
		}
	}
	cout << endl;
}

void beh(node* head)
{
	if (head != NULL)
	{
		stack sta;
		stack help;
		sta.push(head);
		while (!sta.empty())
		{
			head = sta.top();
			help.push(sta.top()->num);
			sta.pop();
			if (head->left)
				sta.push(head->left);
			if (head->right)
				sta.push(head->right);
		}
		while (!help.empty())
		{
			cout << help.top()<<\"  \";
			help.pop();
		}
	}
	cout << endl;
}

void creatT(node* head)
{
	static char n = \'B\';
	if (n == \'F\')
		return;
	node* l = new node();
	node* r = new node();
	l->num = (n ++);
	r->num = (n ++);
	head->left = l;
	head->right = r;
	creatT(head->left);
	creatT(head->right);
}

int main()
{
	node* tree = new node();
	tree->num = \'A\';
	node* head = tree;
	creatT(tree);
	mid(tree);
	pre(tree);
	beh(tree);
}
左神算法学习日记——二叉树（一）

相关推荐
