【遍历二叉树的非递归算法,二叉树的层次遍历】

遍历二叉树的非递归算法,二叉树的层次遍历】"/>

【遍历二叉树的非递归算法,二叉树的层次遍历】

文章目录

• 遍历二叉树的非递归算法
• 二叉树的层次遍历

遍历二叉树的非递归算法

先序遍历序列建立二叉树的二叉链表

中序遍历非递归算法
二叉树中序遍历的非递归算法的关键：在中序遍历过某个结点的整个左子树后，如何找到该结点的根以及右子树。
基本思想：
（1）建立一个栈
（2）根结点进栈，遍历左子树
（3）根结点出栈，输出根结点，遍历右子树。

二叉树的层次遍历

对于一棵二叉树来说，从根结点开始从左到右，从上到下。
每个结点只访问一次。

算法设计思路：
1.按节点进队；
2.队不空时循环：从队列中出列一个结点*p，访问它：①若他有左孩子结点，将左孩子结点进队。②若它有右孩子，将右孩子先进队。

#include<iostream>
using namespace std;
#define TElemType inttypedef struct BiNode {TElemType data;struct BiNode* lchild, * rchild;//左右孩子指针
}BiNode,*BiTree;//菜单
void menu() {cout << "1.初始化" << endl;cout << "2.创建树" << endl;cout << "3.复制树" << endl;
}//初始化
void initList(BiTree T) {T = new BiNode;if (!T) {exit(0);//开辟空间失败}else {T->data = 0;}
}//创建树
BiTree createLink(){BiTree T;int data;cout << "请输入data的值：" << endl;cin >> data;if (data == -1) {//说明他的下子树不再存东西return NULL;}else {T = new BiNode;T->data = data;cout << "请输入左子树的值：" << endl;cin >> data;T->lchild = createLink();cout << "请输入右子树的值：" << endl;cin >> data;T->rchild = createLink();return T;}
}//复制二叉树
int Copy(BiTree T, BiTree& NewT) {if (T == NULL) {NewT = NULL;return 0;}else {NewT = new BiNode;NewT->data = T->data;Copy(T->lchild, NewT->lchild);Copy(T->rchild, NewT->rchild);}
}//int PreOderTraverse(BiTree T) {
//	if (T == NULL) {
//		return 1;
//	}
//	else {
//		cout << "输出T的头结点的值：" << T->data;
//		PreOderTraverse(T->lchild);//递归调用左子树
//		PreOderTraverse(T->rchild);//递归调用右子树
//	}
//}int main() {int choose = 1;BiTree T;T = new BiNode;while (true) {menu();cout << "请输入您选择的功能：" << endl;cin >> choose;switch (choose){case 1:initList(T);cout << "初始化成功！" << endl;break;case 2:createLink();cout << "创建成功！" << endl;break;default:break;}}return 0;
}