二叉树是一个每个最结最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。也就是说二叉树节点的度最大也就是2，而普通的树，节点的度是没有限制的。
完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树
满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
在实际使用时会根据链表和有序数组等数据结构的不同优势进行选择。有序数组的优势在于二分查找，链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢，同样在链表中查找数据项效率就很低。综合以上情况，二叉树可以利用链表和有序数组的优势，同时可以合并有序数组和链表的优势，二叉树也是一种常用的数据结构。
遍历一棵二叉树常用的有四种方法，前序（PreOrder）、中序（InOrder）、后序（PastOrder）还有层序（LevelOrder）。 前中后序三种遍历方式都是以根节点相对于它的左右孩子的访问顺序定义的。例如根->左->右便是前序遍历，左->根->右便是中序遍历，左->右->根便是后序遍历。 而层序遍历是一层一层来遍历的。
typedef int DataType; typedef struct TreeNode { DataType data; struct TreeNode *left; struct TreeNode *right; }TreeNode, *BiTree; //二叉树 typedef struct Node { BiTree node; //二叉树的节点 }Node, *node;
但是后序遍历的非递归和前序和中序的遍历不同了，而后序遍历的非递归版本则要比前序和中序的要难一些，因为在返回根节点时要分从左子树返回和右子树返回两种情况，从左子树返回时不输出，从右子树返回时才需要输出根节点的值。
void LastOrder(BiTree root) { stack<BiTree>s; BiTree cur=root; BiTree top,last=NULL; while(cur!=NULL||!s.empty()) { while(cur!=NULL) { s.push(cur); cur=cur->left; } //此时cur指向空节点 top=s.top();// if(top->right==NULL||top->right==last) { s.pop(); cout<<top->data; last=top; } else { cur=top->right; } } }原文博主
后序遍历的非递归同样要借助一个栈来保存元素，栈中保存的元素是它的右子树和自身都没有被遍历到的节点，与中序遍历不同的是先访问右子树，在回来的时候再输出根节点的值。需要多一个last指针指向上一次访问到的节点，用来确认是从根节点的左子树返回的还是从右子树返回的。
1.还是沿着左子树一路往下走，将路过的节点都压栈，直到走到空节点。
2.
①然后从栈中看一下栈顶元素（只看一眼，用top指针记下，先不出栈）
②如果top节点没有右子树，或者last等于top的右孩子，说明top的右子树不存在或者遍历过了，就输出top节点的值，并将栈顶元素pop掉（出栈）
③反之则是从左子树回到根节点的，接下来要去右子树。
3.
①去向top的右孩子，发现它为空，说明右子树不存在，就可以输出top的值并pop掉栈顶了
②这时候用last指针记下top指向的节点（D），代表上一次处理的节点。
③（这一过程cur始终没有动，一直指向空）
4.
此时我们来看一下代码 ，发现cur还是指向空的，top指向了B(新的栈顶)
top->right是E,但是last还是top指向的上一次位置D,
所以cur指向了栈顶（正在访问的）右子树cur=top->right;
5.
①又回到cur！=NULL的地方，重新对E进行入栈判断的操作，cur=cur->left
发现为空，这样又跟刚开始一样 。
②top会指向栈顶，会指向E的，在top离开后l(指向B)last就跟着top的步伐指向了E
6.这时候发现top的右孩子不为空，但是last等于top->right，说明top的右子树遍历完成，下一步就要输出top的值并且将这个节点出栈，下一次再从栈中看一个栈顶元素A即为top。cur此时还是E的left(NULL)。
7.top发现top的right不为空，而且last也不等于top->right，说明top有右子树并且还没有遍历过，就让cur = top->right
指向C,C的left不是空
指向F,F的left是空
回到第一步（最终结果是把F出栈然后打印输出 top现在指向C Cur指向E的left为空 Cur的下一步操作是指向G)
又重新来一次(top指向现在的栈顶G,last是top的上一次为C,把G出栈打印输出后)
这时的top指向了栈顶A 但是last还是C Cur指向G的左还是空呢，发现top->right==C
到最后，cur访问到了G的左孩子，而top也一路出栈到了A节点，发现cur为空，并且栈中也为空，这时候便代表整个树已经遍历完成，结束循环。
层序遍历是比较接近人的思维方式的一种遍历方法，将二叉树的每一层分别遍历，直到最后的叶子节点被全部遍历完，这里要用到的辅助数据结构是队列，队列具有先进先出的性质。
层序遍历的思路是，创建一个队列，先将根节点（A）入队，然后用front指针将根节点记下来，再将根节点出队，接下来看front节点（也就是刚才的根节点）有没有左孩子或右孩子，如果有，先左（B）后右（C）入队，最后输出front节点的值，只要队列还不为空，就说明还没有遍历完，就进行下一次循环，这时的队头元素（front）则为刚才入队的左孩子（B），然后front出队，再把它的左右孩子拉进来（如果有），因为队列的先进先出性质，B的左右孩子DE是排在C后面的，然后输出B，下一次循环将会拉人C的左右孩子FG，最后因为FG没有左右孩子，一直出队，没有入队元素，队列迟早会变为空，当队列为空时，整颗树就层序遍历完成了，结束循环。
1. 根节点入队，并用front指针标记
2. 队头出队，并将它左右孩子拉进队列
3. 重复1，2
4.直到队列为空
void LevelOrder(BiTree root) { queue<TreeNode *> q; TreeNode *front; if (root == NULL)return; q.push(root); while (!q.empty()) { front = q.front(); q.pop(); if (front->left) q.push(front->left); if (front->right) q.push(front->right); cout<<front->data; } }C++完整代码：
编译环境DevC++
#include<iostream> #include<stdlib.h> #include<stack> #include<queue> using namespace std; #define len 7 typedef int DataType; typedef struct TreeNode { DataType data; struct TreeNode *left; struct TreeNode *right; }TreeNode, *BiTree; //二叉树 typedef struct Node { BiTree node; //二叉树的节点 }Node, *node; void SearchNode(BiTree &root, BiTree &s) { if(root==NULL) { return; } if(s->data>root->data) { if(root->right==NULL) { root->right=s; return; } SearchNode(root->right,s); } else if(s->data<root->data) { if(root->left==NULL) { root->left=s; return ; } SearchNode(root->left,s); } } void insert(BiTree &tree,BiTree &s) { if(tree==NULL) tree=s; else SearchNode(tree,s); } void CreateOrderBinaryTree(BiTree &tree , int *a)//创建一个二叉树 { for(int i=0;i<len;i++) { BiTree s= (BiTree)malloc(sizeof(TreeNode)); s->data=a[i]; s->left=NULL; s->right=NULL; insert(tree,s); } } void preOrder(BiTree root) { stack<BiTree>s; BiTree cur=root; while(cur!=NULL||!s.empty()) { while(cur!=NULL) { cout<<cur->data; s.push(cur); cur=cur->left; } cur=s.top();//左节点为空，便从栈中拿出栈顶节点top，让cur指向top->right s.pop(); cur=cur->right;//走向右节点 } } void MidOrder(BiTree root) { stack<BiTree>s; BiTree cur=root; while(cur!=NULL||!s.empty()) { while(cur!=NULL) { s.push(cur); cur=cur->left; } //此时cur指向了空节点，从栈中取出栈顶节点top cur=s.top(); s.pop(); cout<<cur->data; cur=cur->right; } } void LastOrder(BiTree root) { stack<BiTree>s; BiTree cur=root; BiTree top,last=NULL; while(cur!=NULL||!s.empty()) { while(cur!=NULL) { s.push(cur); cur=cur->left; } //此时cur指向空节点 top=s.top();// if(top->right==NULL||top->right==last) { s.pop(); cout<<top->data; last=top; } else { cur=top->right; } } } void LevelOrder(BiTree root) { queue<BiTree>q; BiTree front; if (root == NULL)return; q.push(root); while (!q.empty()) { front = q.front(); q.pop(); if (front->left) q.push(front->left); if (front->right) q.push(front->right); cout<<front->data; } } int main() { int a[len]={4,2,6,1,3,5,7}; BiTree tree= NULL; //创建一个二叉树 CreateOrderBinaryTree(tree,a); cout<<"前序遍历"<<endl; preOrder(tree); cout<<endl<<"中序遍历"<<endl; MidOrder(tree); cout<<endl<<"后序遍历"<<endl; LastOrder(tree); cout<<endl<<"层序遍历"<<endl; LevelOrder(tree); return 0; }运行结果：
JAVA的直接转发吧
JAVA后序遍历非递归：
原文地址
public void PostOrder(TreeNode p){ Stack<TreeNode> stack=new Stack<TreeNode>(); TreeNode node =p; while(p!=null){ //左子树入栈 for(;p.leftChild!=null;p=p.leftChild){ stack.push(p); } //当前结点无右子树或右子树已经输出 while(p!=null&&(p.rightChild==null||p.rightChild==node)){ visted(p); //纪录上一个已输出结点 node =p; if(stack.empty()) return; p=stack.pop(); } //处理右子树 stack.push(p); p=p.rightChild; } }
