数据结构——遍历二叉树

数据结构——树、二叉树基础概念-CSDN博客https://blog.csdn.net/wy_05136/article/details/163543888?spm1001.2014.3001.5502一、二叉树遍历原理二叉树的遍历是指从根结点出发按照某种次序访问二叉树中所有结点使得每个结点被访问一次且仅被访问一次。二、二叉树结点定义/* 二叉链表有效结点 */ typedef int ElemType; typedef struct BTNode { ElemType data; //数据域 struct BTNode* leftchild; //左孩子指针域 struct BTNode* rightchild; //右孩子指针域 }BTNode;三、二叉树遍历方法一前序遍历根—左—右1.遍历规则若二叉树为空则空操作返回否则先访问根结点然后前序遍历左子树再前序遍历右子树。2.遍历算法及代码实现1递归版void preOrder(BTNode* root) { if (root NULL) return; //处理根结点 printf(%c , root-data); //递归处理左子树 preOrder(root-leftchild); //递归处理右子树 preOrder(root-rightchild); }2非递归版单栈法void preOrder_NoRecursion(BTNode* root) { //0.判空空树直接返回 if (root NULL) return; //1.申请一个栈并将根节点入栈 std::stackBTNode* st; st.push(root); //2.进入while循环循环条件栈不为空 while (!st.empty()) { //3.取出栈顶结点并将其值打印处理 BTNode* tmp st.top(); printf(%c , tmp-data); st.pop(); //4.将刚处理的tmp结点的两个孩子按照先右再左的顺序进行判断处理如果存在则压入栈中 if (tmp-rightchild ! NULL) { st.push(tmp-rightchild); } if (tmp-leftchild ! NULL) { st.push(tmp-leftchild); } } //5.当while结束即栈空遍历结束 }二中序遍历左—根—右1.遍历规则若二叉树为空则空操作返回否则从根结点开始注意并不是先访问根结点中序遍历根结点的左子树然后是访问根结点最后中序遍历右子树。2.遍历算法及代码实现1递归版void inOrder(BTNode* root) { if (root NULL) return; //递归处理左子树 inOrder(root-leftchild); //处理根结点 printf(%c , root-data); //递归处理右子树 inOrder(root-rightchild); }2非递归版单栈法void inOrder_NoRecursion(BTNode* root) { //0.判空空树直接返回 if (root NULL) return; //1.申请栈存储节点tag标记节点是否为第一次遇见 bool tag true; std::stackBTNode* st; st.push(root); //2.栈不为空持续循环遍历 while (!st.empty()) { //3.首次遇见节点且存在左子树持续向左入栈捋完所有左分支 while (tag st.top()-leftchild ! NULL) { st.push(st.top()-leftchild); } //4.左子树处理完毕访问当前根节点、出栈 BTNode* tmp st.top(); printf(%c , tmp-data); st.pop(); //5.判断并处理右子树更新标记位状态 if (tmp-rightchild ! NULL) { //有右孩子右节点入栈标记为首次访问 st.push(tmp-rightchild); tag true; } else { //无右孩子当前节点分支遍历完毕后续节点为回退二次访问 tag false; } } //6.栈空整棵树中序遍历结束 }三后续遍历左—右—根1.遍历规则若二叉树为空则空操作返回否则从左到右先叶子后结点的方式遍历访问左右子树最后是访问根结点。2.遍历算法及代码实现1递归版void postOrder(BTNode* root) { if (root NULL) return; //递归处理左子树 postOrder(root-leftchild); //递归处理右子树 postOrder(root-rightchild); //处理根结点 printf(%c , root-data); }2非递归版法一双栈法void postOrder_NoRecursion1(BTNode* root) { //0.判空空树直接返回 if (root NULL) return; //1.申请两个栈S1用于遍历结点S2用于逆序存储后序结果 std::stackBTNode* S1; std::stackBTNode* S2; //2.根结点先入遍历栈S1 S1.push(root); //3.S1不为空持续遍历所有结点 while (!S1.empty()) { //4.S1栈顶结点出栈存入结果栈S2暂不打印 BTNode* tmp S1.top(); S2.push(tmp); S1.pop(); //5.先左、后右入S1保证后续S2出栈顺序为左—右—根 if (tmp-leftchild ! NULL) S1.push(tmp-leftchild); if (tmp-rightchild ! NULL) S1.push(tmp-rightchild); } //6.S1遍历完毕S2中结点逆序输出即为后序遍历结果 while (!S2.empty()) { printf(%c , S2.top()-data); S2.pop(); } }法二单栈法void postOrder_NoRecursion2(BTNode* root) { //0.判空空树直接返回 if (root NULL) return; ///1.申请一个栈额外申请bool tag再额外申请BTNode *preNode std::stackBTNode* st; st.push(root); bool tag true; //标记是否首次访问节点 BTNode* preNode NULL; //记录上一个已访问的节点 //3.进入while循环循环条件是栈不空即可 while (!st.empty()) { //4.1 tag为true栈顶是新节点优先遍历左子树捋完所有左分支 while (tag true st.top()-leftchild ! NULL) { st.push(st.top()-leftchild); tag false; } //4.2 tag为false栈顶是回溯老节点左子树已处理完毕准备处理右子树 //5.判定右子树是否未被处理 //右孩子存在且不是上一个访问节点 说明右子树未遍历 if (st.top()-rightchild ! NULL st.top()-rightchild ! preNode) { st.push(st.top()-rightchild); tag true; } //5.2 右子树为空 / 右子树已处理完毕左右处理完成访问根节点 else { //6.处理根节点出栈打印更新标记位与前驱结点 BTNode* tmp st.top(); printf(%c , tmp-data); st.pop(); tag false; preNode tmp; } } //7.栈空后序遍历结束 }四层序遍历1.普通1遍历规则若树为空则空操作返回否则从树的第一层也就是根结点开始访问从上而下逐层遍历在同一层中按从左到右的顺序对结点逐个访问。2遍历算法及代码实现void Level_Traverse(BTNode* root) { //0.判空空树直接返回 if (root NULL) return; //1.申请队列根结点入队 std::queueBTNode* q; q.push(root); //2.队列不为空持续循环遍历 while (!q.empty()) { //3.取出队头结点、访问数据、出队 BTNode* tmp q.front(); printf(%c , tmp-data); q.pop(); //先左后右子结点存在则入队保证层序从左到右 if (tmp-leftchild ! NULL) { q.push(tmp-leftchild); } if (tmp-rightchild ! NULL) { q.push(tmp-rightchild); } } //4.队列为空遍历完成 }2.正S1遍历规则若树为空则空操作返回否则从树的第一层也就是根结点开始访问从上而下逐层遍历在奇数层中按从左到右的顺序对结点逐个访问在偶数层中按从右到左的顺序对结点逐个访问。2遍历算法及代码实现void S_Level_Traverse(BTNode* root) { //0.判空空树直接返回 if (root NULL) return; //1.根结点第一层/奇数层入栈S1 std::stackBTNode* s1, s2; s1.push(root); //2.两个栈任意一个非空持续遍历 while (!s1.empty() || !s2.empty()) { //3.处理奇数层S1非空、S2为空从左向右打印 while (!s1.empty()) { BTNode* tmp s1.top(); printf(%c , tmp-data); s1.pop(); //先右后左入栈保证下一层偶数层正序输出 if (tmp-rightchild ! NULL) { s2.push(tmp-rightchild); } if (tmp-leftchild ! NULL) { s2.push(tmp-leftchild); } } //4.处理偶数层S2非空、S1为空从右向左打印 while (!s2.empty()) { BTNode* tmp s2.top(); printf(%c , tmp-data); s2.pop(); //先左后右入栈保证下一层奇数层逆序输出 if (tmp-leftchild ! NULL) { s1.push(tmp-leftchild); } if (tmp-rightchild ! NULL) { s1.push(tmp-rightchild); } } } }3.倒S1遍历规则若树为空则空操作返回否则从树的第一层也就是根结点开始访问从上而下逐层遍历在奇数层中按从右到左的顺序对结点逐个访问在偶数层中按从左到右的顺序对结点逐个访问。2遍历算法及代码实现void S_Level_Traverse(BTNode* root) { //0.判空空树直接返回 if (root NULL) return; //1.根结点第一层/奇数层入栈S1 std::stackBTNode* s1, s2; s1.push(root); //2.两个栈任意一个非空持续遍历 while (!s1.empty() || !s2.empty()) { //3.处理奇数层S1非空、S2为空从右向左打印 while (!s1.empty()) { BTNode* tmp s1.top(); printf(%c , tmp-data); s1.pop(); //先左后右入栈保证下一层偶数层逆序输出 if (tmp-leftchild ! NULL) { s2.push(tmp-leftchild); } if (tmp-rightchild ! NULL) { s2.push(tmp-rightchild); } } //4.处理偶数层S2非空、S1为空从左向右打印 while (!s2.empty()) { BTNode* tmp s2.top(); printf(%c , tmp-data); s2.pop(); //先右后左入栈保证下一层奇数层正序输出 if (tmp-rightchild ! NULL) { s1.push(tmp-rightchild); } if (tmp-leftchild ! NULL) { s1.push(tmp-leftchild); } } } }