按层次建立二叉树
按层次建立二叉树，比较直观方便。思路与按层次遍历二叉树一样。
首先，输入数据，数据存放在数组 a[ ] 中，若输入 >0 则代表该二叉树结点的数据，若 =0 则该结点为NULL，若<0则输入结束。
1.开辟根结点内存，数据赋值。放入队列中
2.遍历数组a[ ] ；取出队头结点，判断当前 a[i] 和 a[i+1]，注意：若a[i] == 0 或 a[i+1] == 0 则不开辟内存，若a[i]>0给其左子树开辟内存，左子树的data = a[i] ，左子树放入队列尾中；若a[i + 1]>0，给其右子树开辟内存，右子树放入队列尾中。i++ 。
完整可运行代码在末尾
按层次建立二叉树 代码：
//层次遍历方式 建立二叉树
//按层次遍历方式输入，若 >0 则代表该二叉树结点的数据，若 =0 则该结点为NULL，若<0则输入结束
void createTree(node* &T) {
queue<node*> que;
int n ,i=0;
cin >> n;
while (true) { //输入，数据存放在数组a[]中
a[i] = n;
cin >> n;
if (n < 0) break;
i++;
}
T = new node;
T->data = a[0];
T->lchirld = NULL;
T->rchirld = NULL;
node *p = T , *q;
que.push(p);
i = 1;
while (!que.empty()) {
p = que.front(); //获取对头的结点指针
que.pop();
if (!p) continue; //从队头获取到的 结点，若为空，则跳过本次循环
if (a[i] > 0) { //若 >0 则创建该二叉树结点的左孩子
q = new node;
q->data = a[i];
q->lchirld = NULL;
q->rchirld = NULL;
p->lchirld = q;
}
else { //否则该结点的左孩子为空
p->lchirld = NULL;
}
que.push(p->lchirld); //左孩子进队列
if (a[i + 1] > 0) { //若 >0 则创建该二叉树结点的右孩子
q = new node;
q->data = a[i + 1];
q->lchirld = NULL;
q->rchirld = NULL;
p->rchirld = q;
}
else { //否则该结点的右孩子为空
p->rchirld = NULL;
}
que.push(p->rchirld); //右孩子进队列
i += 2;
if (a[i] == -1) return;
}
}
非递归 先序遍历二叉树
前序遍历的递归定义：先根节点，后左子树，再右子树。
首先，我们遍历左子树，边遍历边打印，并把根节点存入栈中，以后需借助这些节点进入右子树开启新一轮的循环。还得重复一句：所有的节点都可看做是根节点。
//非递归方法实现 先序遍历(栈实现)
void prePrint(node* T) {
stack<node* > s;
node* p = T;
s.push(p);
while (!s.empty()) {
p = s.top();
s.pop();
if (p) {
s.push(p->rchirld);
s.push(p->lchirld);
cout << p->data << " ";
}
}
}
非递归 中序遍历二叉树
我们直到中序排列的顺序是：左节点，根节点，右节点。那么我们在经过根节点的前面节点 不能释放， 因为后面还需要用到它。所以要用栈先储存。
它的规则大致为：
栈依次存入左节点所有点，直到最左侧在栈顶。
开始抛出栈顶并访问。(例如第一个抛出2)。如果有右节点。那么将右节点加入栈中，然后右节点一致左下遍历直到尾部。（这里5和7没有左节点，所以不加）但是如果抛出15。右节点加入23.再找23的左侧节点加入栈顶。就这样循环下去直到栈为空。
可行性分析：中序是左—中—右的顺序。访问完左侧。当抛出当前点的时候说明左侧已经访问完(或者自己就是左侧)，那么需要首先访问当前点的右侧。那么这个右节点把它当成根节点重复相同操作（因为右节点要满足先左再右的顺序）。这样其实就是模拟了一个递归的过程，需要自己思考。
//非递归方法实现 中序遍历(栈实现)
void ordPrint(node* T) {
stack<node* > s;
node* p = T;
s.push(p);
p = p->lchirld;
while (!s.empty() || p) {
while (p) {
s.push(p);
p = p->lchirld;
}
if (!s.empty()) {
cout << s.top()->data<<" ";
p = s.top()->rchirld;
s.pop();
}
}
}
非递归 后序遍历二叉树
后序遍历递归定义：先左子树，后右子树，再根节点。
后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。直接看代码，代码中有详细的注释。
//非递归 后序遍历
void postPrint(node* T) {
stack<node* > s;
node* p = T ,* lastPrint = NULL; //lastPrint记录上一次被遍历的结点
while (p) {
s.push(p);
p = p->lchirld;
}
while (!s.empty()) {
//走到这里，p都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
p = s.top();
s.pop();
//一个根节点被访问的前提是：无右子树或右子树已被访问过
if (p->rchirld == NULL || p->rchirld == lastPrint) {
cout << p->data << " ";
//修改最近被访问的节点
lastPrint = p;
}
else {
//根节点再次入栈
s.push(p);
//进入右子树，且可肯定右子树一定不为空
p = p->rchirld;
while (p) {
s.push(p);
p = p->lchirld;
}
}
}
}
完整可运行代码:
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
/*
问题描述：
按层次建立二叉树
非递归 先序、中序、后序遍历
*/
int a[100];
struct node {
int data;
struct node* lchirld;
struct node* rchirld;
};
//层次遍历方式 建立二叉树
//按层次遍历方式输入，若 >0 则代表该二叉树结点的数据，若 =0 则该结点为NULL，若<0则输入结束
void createTree(node* &T) {
queue<node*> que;
int n ,i=0;
cin >> n;
while (true) { //输入，数据存放在数组a[]中
a[i] = n;
cin >> n;
if (n < 0) break;
i++;
}
T = new node;
T->data = a[0];
T->lchirld = NULL;
T->rchirld = NULL;
node *p = T , *q;
que.push(p);
i = 1;
while (!que.empty()) {
p = que.front(); //获取对头的结点指针
que.pop();
if (!p) continue; //从队头获取到的 结点，若为空，则跳过本次循环
if (a[i] > 0) { //若 >0 则创建该二叉树结点的左孩子
q = new node;
q->data = a[i];
q->lchirld = NULL;
q->rchirld = NULL;
p->lchirld = q;
}
else { //否则该结点的左孩子为空
p->lchirld = NULL;
}
que.push(p->lchirld); //左孩子进队列
if (a[i + 1] > 0) { //若 >0 则创建该二叉树结点的右孩子
q = new node;
q->data = a[i + 1];
q->lchirld = NULL;
q->rchirld = NULL;
p->rchirld = q;
}
else { //否则该结点的右孩子为空
p->rchirld = NULL;
}
que.push(p->rchirld); //右孩子进队列
i += 2;
if (a[i] == -1) return;
}
}
void print(node* &T) { //先序遍历
if (T) {
cout << T->data<<" ";
print(T->lchirld);
print(T->rchirld);
}
}
//非递归方法实现 先序遍历(栈实现)
void prePrint(node* T) {
stack<node* > s;
node* p = T;
s.push(p);
while (!s.empty()) {
p = s.top();
s.pop();
if (p) {
s.push(p->rchirld);
s.push(p->lchirld);
cout << p->data << " ";
}
}
}
//非递归方法实现 中序遍历(栈实现)
void ordPrint(node* T) {
stack<node* > s;
node* p = T;
s.push(p);
p = p->lchirld;
while (!s.empty() || p) {
while (p) {
s.push(p);
p = p->lchirld;
}
if (!s.empty()) {
cout << s.top()->data<<" ";
p = s.top()->rchirld;
s.pop();
}
}
}
//非递归 后序遍历
void postPrint(node* T) {
stack<node* > s;
node* p = T ,* lastPrint = NULL;
while (p) {
s.push(p);
p = p->lchirld;
}
while (!s.empty()) {
//走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
p = s.top();
s.pop();
//一个根节点被访问的前提是：无右子树或右子树已被访问过
if (p->rchirld == NULL || p->rchirld == lastPrint) {
cout << p->data << " ";
//修改最近被访问的节点
lastPrint = p;
}
else {
//根节点再次入栈
s.push(p);
//进入右子树，且可肯定右子树一定不为空
p = p->rchirld;
while (p) {
s.push(p);
p = p->lchirld;
}
}
}
}
int main() {
for (int i = 0; i < 100; i++)
a[i] = -1; //数组初始化
node *T;
createTree(T);
prePrint(T);
cout << endl;
ordPrint(T);
cout << endl;
postPrint(T);
return 0;
}
