1474人阅读
数据结构（37）
#include &stdafx.h&
#include &iostream&
const int MAXSIZE = 20; //定义栈空间大小为20
struct BTNode
BTNode *m_
BTNode *m_
BTNode *stackArr[MAXSIZE] = {0};//用一个静态数组模拟栈
int nTop = -1;//初始状态下nTop=-1表示栈空
//先序创建二叉树
void CreatBTree(BTNode *&root)
char nValue = 0;
if ('#' == nValue)
root = new BTNode();
root-&m_value = nV
CreatBTree(root-&m_left);
CreatBTree(root-&m_right);
//先序遍历二叉树（递归）
void PreOrderTravse(BTNode *&pRoot)
if (pRoot != NULL)
cout && pRoot-&m_value && & &;
PreOrderTravse(pRoot-&m_left);
PreOrderTravse(pRoot-&m_right);
//中序遍历二叉树（递归）
void InOrderTravse(BTNode *&pRoot)
if (pRoot != NULL)
InOrderTravse(pRoot-&m_left);
cout && pRoot-&m_value && & &;
InOrderTravse(pRoot-&m_right);
//后序遍历二叉树（递归）
void PostOrderTravse(BTNode *&pRoot)
if (pRoot != NULL)
PostOrderTravse(pRoot-&m_left);
PostOrderTravse(pRoot-&m_right);
cout && pRoot-&m_value && & &;
//先序遍历二叉树（非递归）
void PreOrderNoReTravse(BTNode *pRoot)
BTNode *pCur = pR
while (pCur != NULL || nTop != -1)//当前指针不空或栈不空
while (pCur != NULL)//当前指针不空
cout && pCur-&m_value && & &;
stackArr[++nTop] = pC//将当前指针入栈
pCur = pCur-&m_
if (nTop != -1)//栈不空
BTNode *pTop = stackArr[nTop--];//获取栈顶指针且栈顶指针出栈
pCur = pTop-&m_
//中序遍历二叉树（非递归）//递归转换为非递归：利用栈和while循环
void InOrderNoReTravse(BTNode *pRoot)
BTNode *pCur = pR
while (pCur != NULL || nTop != -1)//当前指针不空或栈不空
while (pCur != NULL)//当前指针不空
stackArr[++nTop] = pC//将当前指针入栈
pCur = pCur-&m_
if (nTop != -1)//栈不空
BTNode *pTop = stackArr[nTop--];//获取栈顶指针且栈顶指针出栈
cout && pTop-&m_value && & &;
pCur = pTop-&m_
//后序遍历二叉树（非递归）
void PostOrderNoReTravse(BTNode *pRoot)
BTNode *pCur = pR
BTNode *pTop = NULL;
int nTag[MAXSIZE] = {0}; //标记数组标记每个元素的左右子树是否都已经被访问过了
while (pCur != NULL || nTop != -1)//当前指针不空或栈不空
while (pCur != NULL)//当前指针不空
stackArr[++nTop] = pC//将当前指针入栈
nTag[nTop] = 0;//表示第一次位于栈顶
pCur = pCur-&m_
while (nTop != -1 && nTag[nTop] == 1)
{//栈不空且栈顶指针指向的结点被标记为1即表示给结点的左右子树都已经被访问过了，第二次位于栈顶
pTop = stackArr[nTop--];//获取栈顶指针且栈顶指针出栈
cout && pTop-&m_value && & &;
if (nTop != -1)//栈不空
此时标记为0,意味着应该访问其右子树
pTop = stackArr[nTop];//取到栈顶元素，注意此时不能出栈
pCur = pTop-&m_
nTag[nTop] = 1;
// 后序遍历二叉树（非递归）思想：
// 对于一棵树t,如果t非空，首先应该进入t的左子树访问，此时由于t的右子树及根结点尚未访问，
// 因此必须将t保存起来，放入栈中，以便访问完左子树后，从栈中取出t，进行其右子树及根结点的访问。
// 这里值得注意的是，当一个元素位于栈顶即将处理时，其左子树的访问一定已经完成，
// 如果其右子树尚未遍历，接下来应该进入其右子树的访问，而此时该栈顶元素是不能出栈的，
// 因为其根结点还未被访问；只有等到其右子树也访问完成后，该栈顶元素才能出栈，并输其根结点的值。
// 因此，在二叉树后序遍历的过程中，必须使用标记数组，其每个元素取值为0或1，
// 用于标识栈中每个元素的状态。当一个元素刚进栈时，其对应的tag值置0；当它第一次位于栈顶即将
// 被处理时，其tag值为0，意味着应该访问其右子树，于是将其右子树作为当前处理的对象，
// 此时该栈顶元素仍应该保留在栈中，并将其对应的tag值改为1；当其右子树访问完成后，
// 该元素又一次位于栈顶，而此时其tag值为1，意味着应该访问其根结点，并将其出栈。
// 在整个二叉树后序遍历的过程中，程序要做的工作始终分成两个部分：当前正在处理的树（子树）
// 和保存在栈中待处理的部分。只有这两部分的工作均完成后，程序方能结束。
int _tmain(int argc, _TCHAR* argv[])
BTNode *pRoot = NULL;
CreatBTree(pRoot);
cout && &二叉树的先序、中序、后序遍历(递归)分别为：& &&
PreOrderTravse(pRoot);//先序遍历递归
InOrderTravse(pRoot);//中序遍历递归
PostOrderTravse(pRoot);//后序遍历递归
cout && &二叉树的先序、中序、后序遍历(非递归)分别为：& &&
PreOrderNoReTravse(pRoot);//先序遍历非递归
InOrderNoReTravse(pRoot);//中序遍历非递归
PostOrderNoReTravse(pRoot);//中序遍历非递归
system(&pause&);
运行结果：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：301428次
积分：3828
积分：3828
排名：第5857名
原创：108篇
转载：31篇
评论：91条
燕大小硕，研究方向：XML关键字查询；关注数据结构，算法，C++，JAVA，Linux
(3)(1)(4)(17)(34)(45)(3)(1)(1)(4)(1)(9)(16)二叉树的前序中序后序遍历（当然是非递归的！）
来源：博客园
二叉树的三种遍历方式一直都是为人津津乐道的面试题，考察一个人对递归的理解让他写个三种遍历方式是最简单的考察方式了，那么考察一个人对递归的理解更加深层次的方式就是让他用循环模拟递归（就是把递归代码转换成非递归），一般想要实现这样的东西是需要栈的，或许说使用栈的结构更加贴合函数栈的压入和弹出，更加好理解
递归的三种遍历方式分别为，前序遍历，中序遍历，后序遍历，在考虑完了递归的写法之后，非递归的写法更加难；

因为前序遍历是首先访问根节点的，所以见到节点就访问，然后再去访问左孩子和右孩子。原先使用递归的方式，栈帧的模拟可以使用栈来实现，因为是先访问了左节点，所以左节点应该在右节点之后入栈，b不难写出下面的代码
 1 void PreOrder_NonR()
 2 
 3
{
 4 
 5
if (_root == NULL )
 6 
 7
{
 8 
 9
return;
10 
11
}
12 
13
stack&BinaryTreeNode &T&*&
14 
15
s.push(_root);
16 
17
while (!s.empty())
18 
19
{
20 
21
BinaryTreeNode&T &* top = s.top();
22 
23
cout && top-&_data && " " ;
24 
25
s.pop();
26 
27
if (top-&_right)
28 
29
{
30 
31
s.push(top-&_right);
32 
33
}
34 
35
if (top-&_left)
36 
37
{
38 
39
s.push(top-&_left);
40 
41
}
42 
43
}
44 
45
cout &&
46 
47
}

 

中序遍历可以采用递归的思考方式，因为中序遍历的方式是在访问完左子树之后再去访问根节点，所以在访问完根节点之后进入右子树，右子树又相当于一个新的根节点，所以应该采取访问完根节点之后将右孩子立刻压入栈，然后进入循环可以写出下面的代码
 1 void InOrder_NonR()
 2 
 3
{
 4 
 5
stack&BinaryTreeNode &T&*&
 6 
 7
BinaryTreeNode&T & *cur = _
 8 
 9
while (cur || !s.empty())
10 
11
{
12 
13
while (cur)
14 
15
{
16 
17
s.push(cur);
18 
19
cur = cur-&_
20 
21
}
22 
23
if (!s.empty())
24 
25
{
26 
27
BinaryTreeNode&T & *top = s.top();
28 
29
cout && top-&_data && " " ;
30 
31
s.pop();
32 
33
cur = top-&_
34 
35
}
36 
37
}
38 
39
cout &&
40 
41
}

 

后序遍历是先访问左子树和右子树，所以当左孩子出栈的时候，下一个栈内节点（即根节点）不能立刻就访问，需要考虑几种情况，如果此时此刻右孩子为空，那么可以访问，如果此时有孩子不为空，那么需要考虑右孩子是否被访问过了，如果访问过了，则可以访问根节点，否则需要先访问右子树然后再去访问根节点，可以利用一个变量来保存之前访问的是哪一个节点，可以写出如下代码

 1
void PostOrder_NonR()
 2 
 3
{
 4 
 5
stack&BinaryTreeNode &T& *&
 6 
 7
BinaryTreeNode&T &* PreVisited = NULL;
 8 
 9
BinaryTreeNode&T &* cur = _
10 
11
while (cur || !s.empty())
12 
13
{
14 
15
while (cur)
16 
17
{
18 
19
s.push(cur);
20 
21
cur = cur-&_
22 
23
}
24 
25
BinaryTreeNode&T & *top = s.top();
26 
27
if (top-&_right == NULL || PreVisited == top-&_right)
28 
29
{
30 
31
cout && top-&_data && " " ;
32 
33
s.pop();
34 
35
PreVisited =
36 
37
}
38 
39
else
40 
41
{
42 
43
cur = top-&_
44 
45
}
46 
47
}
48 
49
cout &&
50 
51
}

这是我从我的笔记导出来的，话说缩进怎么变成这德行了。。。
免责声明：本站部分内容、图片、文字、视频等来自于互联网，仅供大家学习与交流。相关内容如涉嫌侵犯您的知识产权或其他合法权益，请向本站发送有效通知，我们会及时处理。反馈邮箱&&&&。
学生服务号
在线咨询，奖学金返现，名师点评，等你来互动本文部分来源于CSDN兰亭风雨大牛的原创。链接为
&因为感觉大牛讲的很好，所以这里的文字讲解采用大牛的，大家可以直接看原创！代码部分是我自己的，leetcode代码，可在leetcode Accepted
二叉树是一种非常重要的数据结构，很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式，因为树的本身就是用递归定义的，因此采用递归的方法实现三种遍历，不仅代码简洁且容易理解，但其开销也比较大，而若采用非递归方法实现三种遍历，则要用栈来模拟实现（递归也是用栈实现的）。下面先简要介绍三种遍历方式的递归实现，再详细介绍三种遍历方式的非递归实现
一、三种遍历方式的递归实现（比较简单，这里不详细讲解）
1、先序遍历&&按照&根节点-左孩子-右孩子&的顺序进行访问
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&int& preorderTraversal(TreeNode *root) {
vector&int& root_
vector&int& left_
vector&int& right_
if(root==NULL) return root_
root_vec.push_back(root-&val);
if(root-&left!=NULL) left_vec=preorderTraversal(root-&left);
if(root-&right!=NULL) right_vec=preorderTraversal(root-&right);
root_vec.insert(root_vec.end(),left_vec.begin(),left_vec.end());
root_vec.insert(root_vec.end(),right_vec.begin(),right_vec.end());
return root_
2、中序遍历&&按照&左孩子-根节点-右孩子&的顺序进行访问。
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
/*recursive*/
11 class Solution {
12 public:
vector&int& inorderTraversal(TreeNode *root) {
vector&int& root_
vector&int& left_
vector&int& right_
if(root==nullptr) return root_
if(root-&left!=nullptr) left_vec=inorderTraversal(root-&left);
root_vec.push_back(root-&val);
if(root-&right!=nullptr) right_vec=inorderTraversal(root-&right);
left_vec.insert(left_vec.end(),root_vec.begin(),root_vec.end());
left_vec.insert(left_vec.end(),right_vec.begin(),right_vec.end());
return left_
3、后序遍历&&按照&左孩子-右孩子-根节点&的顺序进行访问。&
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&int& postorderTraversal(TreeNode *root) {
vector&int& root_
vector&int& left_
vector&int& right_
if(root==NULL) return root_
if(root-&left) left_vec=postorderTraversal(root-&left);
if(root-&right) right_vec=postorderTraversal(root-&right);
root_vec.push_back(root-&val);
left_vec.insert(left_vec.end(),right_vec.begin(),right_vec.end());
left_vec.insert(left_vec.end(),root_vec.begin(),root_vec.end());
return left_
二、三种遍历方式的非递归实现
&&& 为了便于理解，这里以下图的二叉树为例，分析二叉树的三种遍历方式的实现过程。
& & & & & & & & & & & & & & & & & & & & & & & & & & &
&&&&&&&&&&1、前序遍历的非递归实现&
根据先序遍历的顺序，先访问根节点，再访问左子树，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的先序遍历顺序为：ABDECF。非递归的实现思路如下：
对于任一节点P，
1）输出节点P，然后将其入栈，再看P的左孩子是否为空；
2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作；
3）若P的左孩子为空，则将栈顶节点出栈，但不输出，并将出栈节点的右孩子置为当前节点，看其是否为空；
4）若不为空，则循环至1）操作；
5）如果为空，则继续出栈，但不输出，同时将出栈节点的右孩子置为当前节点，看其是否为空，重复4）和5）操作；
6）直到当前节点P为NULL并且栈空，遍历结束。
&& 下面以上图为例详细分析其先序遍历的非递归实现过程：
首先，从根节点A开始，根据操作1），输出A，并将其入栈，由于A的左孩子不为空，根据操作2），将B置为当前节点，再根据操作1），将B输出，并将其入栈，由于B的左孩子也不为空，根据操作2），将D置为当前节点，再根据操作1），输出D，并将其入栈，此时输出序列为ABD；
由于D的左孩子为空，根据操作3），将栈顶节点D出栈，但不输出，并将其右孩子置为当前节点；
由于D的右孩子为空，根据操作5），继续将栈顶节点B出栈，但不输出，并将其右孩子置为当前节点；
由于B的右孩子E不为空，根据操作1），输出E，并将其入栈，此时输出序列为：ABDE；
由于E的左孩子为空，根据操作3），将栈顶节点E出栈，但不输出，并将其右孩子置为当前节点；
由于E的右孩子为空，根据操作5），继续将栈顶节点A出栈，但不输出，并将其右孩子置为当前节点；
由于A的右孩子C不为空，根据操作1），输出C，并将其入栈，此时输出序列为：ABDEC；
由于A的左孩子F不为空，根据操作2），则将F置为当前节点，再根据操作1），输出F，并将其入栈，此时输出序列为：ABDECF；
由于F的左孩子为空，根据操作3），将栈顶节点F出栈，但不输出，并将其右孩子置为当前节点；
由于F的右孩子为空，根据操作5），继续将栈顶元素C出栈，但不输出，并将其右孩子置为当前节点；
此时栈空，且C的右孩子为NULL，因此遍历结束。
&&&根据以上思路，前序遍历的非递归实现代码如下：
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&int& preorderTraversal(TreeNode *root) {
vector&int& preorder_
TreeNode *p=//定义用来指向当前访问的节点的指针
if(p==NULL) return preorder_//若为空树，则返回空vector
stack&TreeNode *& treenode_//创建一个空栈
//直到当前节点p为NULL且栈空时，循环结束
while(p||!treenode_stack.empty())
//从根节点开始，输出当前节点，并将其入栈，
//同时置其左孩子为当前节点，直至其没有左孩子，及当前节点为NULL
preorder_vec.push_back(p-&val);
treenode_stack.push(p);
//如果当前节点p为NULL且栈不空，则将栈顶节点出栈，
//同时置其右孩子为当前节点,循环判断，直至p不为空
while(!p&&!treenode_stack.empty())
p=treenode_stack.top();
treenode_stack.pop();
2、中序遍历的非递归实现
根据中序遍历的顺序，先访问左子树，再访问根节点，后访问右子树，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的中序遍历顺序为：DBEAFC。非递归的实现思路如下：
对于任一节点P，
1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
3）若不为空，则重复1）和2）的操作；
4）若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
5）直到当前节点P为NULL并且栈为空，则遍历结束。
&& 下面以上图为例详细分析其中序遍历的非递归实现过程：
首先，从根节点A开始，A的左孩子不为空，根据操作1）将A入栈，接着将B置为当前节点，B的左孩子也不为空，根据操作1），将B也入栈，接着将D置为当前节点，由于D的左子树为空，根据操作2），输出D；
由于D的右孩子也为空，根据操作4），执行出栈操作，将栈顶结点B出栈，并将B置为当前节点，此时输出序列为DB；
由于B的右孩子不为空，根据操作3），将其右孩子E置为当前节点，由于E的左孩子为空，根据操作1），输出E，此时输出序列为DBE；
由于E的右孩子为空，根据操作4），执行出栈操作，将栈顶节点A出栈，并将节点A置为当前节点，此时输出序列为DBEA；
此时栈为空，但当前节点A的右孩子并不为NULL，继续执行，由于A的右孩子不为空，根据操作3），将其右孩子C置为当前节点，由于C的左孩子不为空，根据操作1），将C入栈，将其左孩子F置为当前节点，由于F的左孩子为空，根据操作2），输出F，此时输出序列为：DBEAF；
由于F的右孩子也为空，根据操作4），执行出栈操作，将栈顶元素C出栈，并将其置为当前节点，此时的输出序列为：DBEAFC；
由于C的右孩子为NULL，且此时栈空，根据操作5），遍历结束。
&&&&根据以上思路，中序遍历的非递归实现代码如下：
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
/*iteratively*/
11 class Solution {
12 public:
vector&int& inorderTraversal(TreeNode *root) {
stack&TreeNode *& inorder_
TreeNode * p=
vector&int& inorder_
if(p==nullptr) return inorder_//若为空树，则返回空vector
while(p||!inorder_stack.empty())
if(p-&left!=nullptr)//若左节点不空，当前节点进栈，并使右孩子为当前节点，继续判断
inorder_stack.push(p);
//如果左孩子为空，则输出当前节点，并将其右孩子设为当前节点，看其是否为空
inorder_vec.push_back(p-&val);
//如果为空，且栈不空，则将栈顶节点出栈，并输出该节点，
//同时将它的右孩子设为当前节点，继续判断，直到当前节点不为空
while(!p&&!inorder_stack.empty())
p=inorder_stack.top();
inorder_vec.push_back(p-&val);
inorder_stack.pop();
return inorder_
3、后序遍历的非递归实现
根据后序遍历的顺序，先访问左子树，再访问右子树，后访问根节点，而对于每个子树来说，又按照同样的访问顺序进行遍历，上图的后序遍历顺序为：DEBFCA。后序遍历的非递归的实现相对来说要难一些，要保证根节点在左子树和右子树被访问后才能访问，思路如下：
对于任一节点P，
1）先将节点P入栈；
2）若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；
3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；
4）直到栈空，遍历结束。
&& 下面以上图为例详细分析其后序遍历的非递归实现过程：
首先，设置两个指针：Cur指针指向当前访问的节点，它一直指向栈顶节点，每次出栈一个节点后，将其重新置为栈顶结点，Pre节点指向上一个访问的节点；
Cur首先指向根节点A，Pre先设为NULL，由于A存在左孩子和右孩子，根据操作3），先将右孩子C入栈，再将左孩子B入栈，Cur改为指向栈顶结点B；
由于B的也有左孩子和右孩子，根据操作3），将E、D依次入栈，Cur改为指向栈顶结点D；
由于D没有左孩子，也没有右孩子，根据操作2），直接输出D，并将其出栈，将Pre指向D，Cur指向栈顶结点E，此时输出序列为：D；
由于E也没有左右孩子，根据操作2），输出E，并将其出栈，将Pre指向E，Cur指向栈顶结点B，此时输出序列为：DE；
由于B的左右孩子已经被输出，即满足条件Pre==Cur-&lchild或Pre==Cur-&rchild，根据操作2），输出B，并将其出栈，将Pre指向B，Cur指向栈顶结点C，此时输出序列为：DEB；
由于C有左孩子，根据操作3），将其入栈，Cur指向栈顶节点F；
由于F没有左右孩子，根据操作2），输出F，并将其出栈，将Pre指向F，Cur指向栈顶结点C，此时输出序列为：DEBF；
由于C的左孩子已经被输出，即满足Pre==Cur-&lchild，根据操作2），输出C，并将其出栈，将Pre指向C，Cur指向栈顶结点A，此时输出序列为：DEBFC；
由于A的左右孩子已经被输出，根据操作2），输出A，并将其出栈，此时输出序列为：DEBFCA；
此时栈空，遍历结束。
&&&根据以上思路，后序遍历的非递归实现代码如下：
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 class Solution {
11 public:
vector&int& postorderTraversal(TreeNode *root) {
vector&int& postorder_
TreeNode *cur= //定义指针，指向当前节点
TreeNode *pre=NULL;//定义指针，指向上一各访问的节点
if(cur==NULL) return postorder_
stack&TreeNode *& postorder_//创建一个空栈
postorder_stack.push(cur);//先将树的根节点入栈
//直到栈空时，结束循环
while(!postorder_stack.empty())
cur=postorder_stack.top();//当前节点置为栈顶节点
if((cur-&left==NULL&&cur-&right==NULL)||
((pre!=NULL)&&(cur-&left==pre||cur-&right==pre)))
//如果当前节点没有左右孩子，或者有左孩子或有孩子，但已经被
//访问输出,则直接输出该节点，将其出栈，将其设为上一个访问的节点
postorder_stack.pop();
postorder_vec.push_back(cur-&val);
//如果不满足上面两种情况,则将其右孩子左孩子依次入栈
if(cur-&right!=NULL) postorder_stack.push(cur-&right);
if(cur-&left!=NULL) postorder_stack.push(cur-&left);
本博文写的非常粗糙，不断修改完善中。。。
阅读(...) 评论()简单二叉树
&&&&public&&class&Node&T&
&&&&&&&&private&T&_
&&&&&&&&private&Node&T&&_leftC
&&&&&&&&private&Node&T&&_rightC
&&&&&&&&private&Node&T&&_P
&&&&&&&&private&bool&
&&&&&&&&public&&Node(){}
&&&&&&&&public&Node(T&data)&{&this._data&=&&flag&=&&}
&&&&&&&&public&override&string&ToString()
&&&&&&&&&&&&return&_data.ToString();
&&&&&&&&public&T&Data&{&get&{&return&_&}&set&{&_data&=&&}&}
&&&&&&&&public&&Node&T&&LeftChild&{&get&{&return&_leftC&}&set&{&_leftChild&=&&}&}
&&&&&&&&public&Node&T&&RightChild&{&get&{&return&_rightC&}&set&{&_rightChild&=&&}&}
&&&&&&&&public&Node&T&&Parent&{&get&{&return&_P&}&set&{&_Parent&=&&}&}
&&&&&&&&public&bool&Flag&{&get&{&return&&}&set&{&flag&=&&}&}
&&&&class&BinaryTree&T&
&&&&&&&&private&Node&T&&_
&&&&&&&&public&BinaryTree()&{&}
&&&&&&&&public&BinaryTree(Node&T&&node)&{&this._root&=&&}
&&&&&&&&//四种序列
&&&&&&&&public&Node&T&&Root&{&get&{&return&_&}&set&{&this._root&=&&}&}
&&&&&&&&public&void&ByLayerPrint()
&&&&&&&&&&&&Node&T&&temp&=&new&Node&T&();
&&&&&&&&&&&&Queue&Node&T&&&queue&=&new&Queue&Node&T&&();
&&&&&&&&&&&&queue.Enqueue(_root);
&&&&&&&&&&&&while&(queue.Count&&&0)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&temp&=&queue.Dequeue();
&&&&&&&&&&&&&&&&Console.WriteLine(temp);
&&&&&&&&&&&&&&&&if&(temp.LeftChild&!=&null)&{&queue.Enqueue(temp.LeftChild);&}
&&&&&&&&&&&&&&&&if&(temp.RightChild&!=&null)&{&queue.Enqueue(temp.RightChild);&}
&&&&&&&&&&&&}
&&public&void&PreOrderPrint()
&&&&&&&&&&&&Node&T&&temp&=&new&Node&T&();
&&&&&&&&&&&&Stack&Node&T&&&stack&=&new&Stack&Node&T&&();
&&&&&&&&&&&&temp&=&_
&&&&&&&&&&&&while&(temp&!=&null&||&stack.Count&&&0)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&while&(temp&!=&null)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&Console.WriteLine(temp);
&&&&&&&&&&&&&&&&&&&&stack.Push(temp);
&&&&&&&&&&&&&&&&&&&&temp&=&temp.LeftC
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&if&(stack.Count&&&0)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&temp&=&stack.Pop();
&&&&&&&&&&&&&&&&&&&&temp&=&temp.RightC
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&public&void&InOrderPrint()
&&&&&&&&&&&&Node&T&&temp&=&new&Node&T&();
&&&&&&&&&&&&Stack&Node&T&&&stack&=&new&Stack&Node&T&&();
&&&&&&&&&&&&temp&=&_
&&&&&&&&&&&&while&(temp&!=&null)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&stack.Push(temp);
&&&&&&&&&&&&&&&&temp&=&temp.LeftC
&&&&&&&&&&&&}
&&&&&&&&&&&&while&(stack.Count&&&0)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&temp&=&stack.Pop();
&&&&&&&&&&&&&&&&Console.WriteLine(temp);
&&&&&&&&&&&&&&&&if&(temp.RightChild&!=&null)&{&stack.Push(temp.RightChild);&}
&&&&&&&&&&&&}
&&public&void&PostOrderPrint()
&&&&&&&&&&&&Node&T&&temp&=&new&Node&T&();
&&&&&&&&&&&&Stack&Node&T&&&stack&=&new&Stack&Node&T&&();
&&&&&&&&&&&&temp&=&_
&&&&&&&&&&&&while&(temp&!=&null)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&stack.Push(temp);
&&&&&&&&&&&&&&&&temp&=&temp.LeftC
&&&&&&&&&&&&}
&&&&&&&&&&&&while&(stack.Count&&&0)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&temp&=&stack.Peek();
&&&&&&&&&&&&&&&&if&(temp.RightChild&==&null&||&temp.RightChild.Flag)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&stack.Pop();
&&&&&&&&&&&&&&&&&&&&Console.WriteLine(temp);
&&&&&&&&&&&&&&&&&&&&temp.Flag&=&
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&temp&=&temp.RightC
&&&&&&&&&&&&&&&&&&&&while&(temp&!=&null)
&&&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&stack.Push(temp);
&&&&&&&&&&&&&&&&&&&&&&&&temp&=&temp.LeftC
&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&&&&&static&void&Main(string[]&args)
&&&&&&&&&&&&Node&string&&node&=&new&Node&string&("aaa");
&&&&&&&&&&&&Node&string&&node2&=&new&Node&string&("bbb");
&&&&&&&&&&&&Node&string&&node3&=&new&Node&string&("ccc");
&&&&&&&&&&&&Node&string&&node4&=&new&Node&string&("ddd");
&&&&&&&&&&&&Node&string&&node5&=&new&Node&string&("eee");
&&&&&&&&&&&&Node&string&&node6&=&new&Node&string&("fff");
&&&&&&&&&&&&Node&string&&node7&=&new&Node&string&("ggg");
&&&&&&&&&&&&Node&string&&node8&=&new&Node&string&("hhh");
&&&&&&&&&&&&BinaryTree&string&&tree&=&new&BinaryTree&string&(node);
&&&&&&&&&&&&node.LeftChild&=&node5;
&&&&&&&&&&&&node.RightChild&=&node4;
&&&&&&&&&&&&node4.RightChild&=&node3;
&&&&&&&&&&&&node5.RightChild&=&node6;
&&&&&&&&&&&&node5.LeftChild&=&node7;
&&&&&&&&&&&&Console.WriteLine("******************************");
&&&&&&&&&&&&Console.WriteLine("*******&层序遍历&&1&**********");
&&&&&&&&&&&&Console.WriteLine("*******&前序遍历&&2&**********");
&&&&&&&&&&&&Console.WriteLine("*******&中序遍历&&3&**********");
&&&&&&&&&&&&Console.WriteLine("*******&后序遍历&&4&**********");
&&&&&&&&&&&&Console.WriteLine("*******&退出&&&&&&0&**********");
&&&&&&&&&&&&Console.WriteLine("******************************");
&&&&&&&&&&&&while&(true)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&ConsoleKeyInfo&key&=&Console.ReadKey();
&&&&&&&&&&&&&&&&switch&(key.Key)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&case&ConsoleKey.D0:
&&&&&&&&&&&&&&&&&&&&&&&&Environment.Exit(0);
&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&case&ConsoleKey.D1:
&&&&&&&&&&&&&&&&&&&&&&&&Console.WriteLine("---------层序遍历----------");
&&&&&&&&&&&&&&&&&&&&&&&&tree.ByLayerPrint();
&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&case&ConsoleKey.D2:
&&&&&&&&&&&&&&&&&&&&&&&&Console.WriteLine("---------前序遍历----------");
&&&&&&&&&&&&&&&&&&&&&&&&tree.PreOrderPrint();
&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&case&ConsoleKey.D3:
&&&&&&&&&&&&&&&&&&&&&&&&Console.WriteLine("---------中序遍历----------");
&&&&&&&&&&&&&&&&&&&&&&&&tree.InOrderPrint();
&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&case&ConsoleKey.D4:
&&&&&&&&&&&&&&&&&&&&&&&&Console.WriteLine("---------后序遍历----------");
&&&&&&&&&&&&&&&&&&&&&&&&tree.PostOrderPrint();
&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&default:
&&&&&&&&&&&&&&&&&&&&&&&&Console.WriteLine("输入有误，重新输入");
&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
& 开源中国(OSChina.NET) |
开源中国社区(OSChina.net)是工信部
指定的官方社区