数据结构-------树 非递归&&广度优先和深度优先遍历

1.前序遍历：

视屏：https://www.bilibili.com/video/av15550091?from=search&seid=17557964195432801211

//前序遍历
void PreOrder(Binode root)
{
	InitStack(S);	//建立空栈
	while(root!=NULL || !StackEMpty(S))	//栈为空且root为NULL时退出循环
	{
		while(root!=NULL)
		{
			printf(root->data);	//访问根节点
			Push(S,root);	//根进栈
			root=root->lchild;
		}
		if(!StackEMpty(S))
		{
			root=Pop(S);	//出栈
			root=root->rchild;   //遍历右子树
		}
	}
}

//中序遍历
void InOrder(Binode root)
{
	InitStack(S);	//建立空栈
	while(root!=NULL || !StackEMpty(S))	//栈为空且root为NULL时退出循环
	{
		if(root-lchild !=NULL)
		{
			Push(S,root);
			root=root-lchild;	//继续遍历左子树
		}
		else
		{
			printf(root->data);
			root=root-rchild;	//遍历有子树
			while(root = NULL && !StackEMpty(S))
			{

                root=pop(S);
				printf(root->data);
				root=root->rchild;	//访问有子树
			}
		}
	}
}

//中序遍历
void PreOrder(Binode root)
{
	InitStack(S);	//建立空栈
	while(root!=NULL || !StackEMpty(S))	//栈为空且root为NULL时退出循环
	{
		while(root!=NULL)
		{
			Push(S,root);	//根进栈
			root=root->lchild;
		}
		if(!StackEMpty(S))
		{
			root=Pop(S);	//出栈
			printf(root->data);	//访问根节点
			root=root->rchild;   //遍历右子树
		}
	}
}

//后序遍历
void EndOrder(TreeNode root)
{
	TreeNode cur = root;  //当前节点
	TreeNode prev = NULL;   //上一次打印的节点
	stack<TreeNode> s;
	
	while(cur || !s.empty())  //节点不为空或栈不空则还有元素
	{
		while(cur)  //一直往做走
		{
			s.push(cur);
			cur=cur->lchild;
		}
		
		TreeNode top = s.top(); //取栈顶元素
		
		//如果结点的右孩子为空，或者右孩子已经被打印，则可以打印本结点
		if(top->rchild == NULL || top->rchild == prev)
		{
			cout<<top->value<<endl;
			s.pop();
			prev=top;  ////将prev更新为已经打印过的结点
		}
		//如果结点的右孩子不为空，且还没有被访问，则将cur更新为右孩子，继续while循环，
        else
        {
            cur = top->right;
        }
    }
}

2.深度优先和广度优先：

二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）

深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。

广度优先遍历：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

 

DFS:ABDECFG

BFS:ABCDEFG

DFS实现：

数据结构：栈

父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可

BFS实现：

数据结构：队列

父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可

#include<iostream>
#include<stdlib.h>
#include<malloc.h>
#include<Stack>
#include<Queue>
using namespace std;

typedef struct Node
{
	char data;
	struct Node *lchild;
	struct Node *rchild;
}*Tree;    //tree是node指针类型

int index = 0;   //全局索引

void treeNodeConstructor(Tree &root, char data[])
{
	char e = data[index++];
	if (e == '#')
	{
		root = NULL;
	}
	else
	{
		root = (Node*)malloc(sizeof(Node));
		root->data = e;
		treeNodeConstructor(root->lchild, data);
		treeNodeConstructor(root->rchild, data);
	}
}

//深度优先遍历
void depthFirstSearch(Tree root)
{
	stack<Node *>nodestack;//STL
	nodestack.push(root);
	Node *node;  //保存弹出的节点
	while (!nodestack.empty())
	{
		node = nodestack.top();
		cout << node->data << endl;
		nodestack.pop();
		if (node->rchild)
			nodestack.push(node->rchild);
		if (node->lchild)
			nodestack.push(node->lchild);
	}
}

//广度优先遍历
void breathFirstSearch(Tree root)
{
	queue<Node *>nodeQueue;
	nodeQueue.push(root);
	Node* node;

	while (!nodeQueue.empty())
	{
		node = nodeQueue.front();
		nodeQueue.pop();
		cout << node->data << endl;
		if (node->lchild)
			nodeQueue.push(node->lchild);
		if (node->rchild)
			nodeQueue.push(node->rchild);
	}
}

int main()
{
	char data[15] = { 'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#' };
	Tree tree;
	treeNodeConstructor(tree, data);
	printf("深度优先遍历二叉树结果: ");
	depthFirstSearch(tree);
	printf("\n\n广度优先遍历二叉树结果: ");
	breathFirstSearch(tree);
	return 0;
}

参考资料：

1. https://blog.csdn.net/mingwanganyu/article/details/72033122