网站专题建设方案,外发加工平台,网站搭建规划模板,网站必须兼容哪些浏览器简介#xff1a; 本文主要是代码实现#xff0c;二叉树遍历#xff0c;递归和非递归#xff08;用栈#xff09;。主要为了好理解#xff0c;直接在代码处#xff0c;加了详细注释#xff0c;方便复习和后期默写。主要了解其基本思想#xff0c;为后期熟练应用…简介 本文主要是代码实现二叉树遍历递归和非递归用栈。主要为了好理解直接在代码处加了详细注释方便复习和后期默写。主要了解其基本思想为后期熟练应用打基础。
遍历的意义就是为了实现在二叉树上进行各种操作给每个结点都光顾到位到根节点时进行当前节点的操作。 目录
目录
一、前序遍历。
1.1前序遍历—递归
1.2前序遍历—非递归
二、中序遍历
2.1中序遍历—递归
2.2中序遍历—非递归
三、后序遍历
3.1后序遍历—递归
3.2后序遍历—非递归 五、总代码
5.1代码
5.2运行结果图 一、前序遍历。
1.1前序遍历—递归 简介前序为先访问根结点再访问其左孩子再访问右孩子根左右。
//前序遍历递归
void PreOrder(BTNode *node)
{if(nodeNULL)//当前结点为空时返回上一层递归空间 {printf(#);return;}//结点非空时 visit(node);PreOrder(node-lchild);PreOrder(node-rchild);
} 1.2前序遍历—非递归 简介非递归就是利用栈就是一个存放树结点指针的数组再加一个栈顶标记top存放树节点的指针。树不为空的时候先入栈随后栈不为空时再进行出栈操作。前序遍历出栈时先出栈后先访问该节点信息随后再判断该节点是否有右孩子有则右孩子的指针存进栈中。再判断是否有左孩子有则左孩子指针存进栈
//前序遍历非递归
void Stack_PreOrder(BTNode *node)
{if(nodeNULL)//树为空不处理return;//创建一个栈存放树结点类型的地址 BTNode* Stack[10];int top-1;//工作指针随着p指针记录树的当前结点位置 BTNode *pNULL;//当树非空时进行操作 if(node !NULL){//入栈 top;Stack[top]node;//随后进行出栈操作只有栈非空时才可出栈 while(top ! -1){//取出此时栈顶元素 pStack[top];top--;//然后进行访问当前结点的相关操作 visit(p);//访问完根在看该根的右孩子入栈 因为是栈先进后出而前序为根左右根出来后右入栈之后左入栈最后出栈是栈顶出 if(p-rchild!NULL){top;Stack[top]p-rchild;}//访问完右孩子在看该根的左孩子入栈 if(p-lchild!NULL){top;Stack[top]p-lchild;} } }
}
二、中序遍历
2.1中序遍历—递归 简介左根右。不理解为啥的可以画图每进入一个新的函数便是一个新的空间。
//中序遍历-递归
void InOrder(BTNode *node)
{if(nodeNULL){printf(#);return;}InOrder(node-lchild);visit(node);InOrder(node-rchild);
}
2.2中序遍历—非递归 简介其实栈也好递归也罢需要操作的仅为两步第一步为进入新树的一些列操作。操作完进入第二步进到另一方向孩子树中该树中的操作还是先进性第一步再进行第二部 思想中序遍历非递归操作最外圈来个do-while循环先执行再判断。如果栈内非空或者该结点不为空都进行中序遍历操作。 do-while里面的操作先左子树操作一直遍历入栈元素随后给指针地址换成该节点的左孩子就是一直遍历到左孩子为空才停止。至此左根右中的左操作完毕。随后出栈元素进行左根右中的根操作访问根节点。至此为第一步的操作。随后第二部进入方向的树中即结点指针换为右孩子地址
//中序遍历-非递归
void StackInOrder(BTNode *node)
{if(nodeNULL)//树为空则不处理return;printf(中序遍历-非递归:);BTNode* pnode;BTNode* Stack[10];int top-1;do{//当结点不为空时入栈并进入左孩子。 ——访问左孩子 while(p!NULL){top;Stack[top]p;pp-lchild;}//一直遍历左遍历到空此时出栈pStack[top];top--;visit(p);//访问根 pp-rchild;//根访问完随后访问右孩子。随后右孩子中又是新的树然后再进行左根右操作形成循环从上面再来一圈。 }while(top!-1 || p!NULL);//只要树不为空或者栈内有元素就一直进行操作。 }
三、后序遍历
3.1后序遍历—递归 简介左右根。
// 后序遍历-递归
void PostOrder(BTNode *node)
{if(nodeNULL){printf(#);return;}PostOrder(node-lchild);PostOrder(node-rchild);visit(node);
}
3.2后序遍历—非递归 简介这个比较麻烦不过还是利用描边法去做根据描边法根节点被访问两次第一次时入栈时第二次时判断是否出栈时就看从那一层返回到根节点的如果从右孩子返回的则进行出栈操作先记录当前结点再出栈。否则则进行右子树结点的出栈 这里面跟中序略有不同入栈和出栈的情况需要判断所以需要用栈顶指针时刻对比。
先跟根结点入栈随后当栈内不为空时一直进行遍历操作。先进性第一步的入栈操作当上层遍历即不是栈顶指针的左孩子又不是右孩子时更新工作指针为左孩子随后进行一直左孩子入栈操作第二步左孩子到底了此时需要面临出栈因此给当前栈顶元素取出来如果该树没有左孩子或者pre与右孩子地址相同则进行出栈操作并记录出栈前的指针p否则则给右孩子入栈。
void StackPostOrder(BTNode *node)
{printf(后序遍历-非递归);if(nodeNULL)return; BTNode *pnode;//工作指针 BTNode *preNULL;//表示上层结点位置 //栈 BTNode *Stack[10];int top-1;//先跟根节点入栈为了方便第一次判断top;Stack[top]p;do{//先判断上层结点是否遍历过没有则进行左子树都入栈入到底if(pre!Stack[top]-lchild pre!Stack[top]-rchild){pStack[top]-lchild;//上次没有遍历过左右孩子那么开始栈顶元素的左孩子入栈操作。while(p!NULL){top;Stack[top]p;pp-lchild; } }//左孩子方向弄到底后开始判断是否需要出栈输出。pStack[top];//记录此时的栈顶元素if(p-rchildNULL || prep-rchild)//如果右孩子为空或者上一层和当前结点的右孩子相等则输出 {prep;//记录当前结点地址 visit(p);//输出 top--;//输出了栈内指针减少 }else{top;Stack[top]p-rchild;//右孩子入栈 } }while(top!-1);
} 五、总代码
5.1代码
#include stdio.h
#include stdlib.h
//创建树,孩子链表
typedef struct BTNode
{int data;struct BTNode *rchild,*lchild;}BTNode;
//创建树结点并初始化
BTNode* BuyNode(int x)
{BTNode* node(BTNode*)malloc(sizeof(BTNode));node-datax;node-lchildNULL;node-rchildNULL;return node;
}
//手动创建树
BTNode* CreatTree()
{BTNode* node1BuyNode(1);BTNode* node2BuyNode(2);BTNode* node3BuyNode(3);BTNode* node4BuyNode(4);BTNode* node5BuyNode(5);node1-lchildnode2;node1-rchildnode3;node2-lchildnode4;node2-rchildnode5;return node1;
}
//访问当前结点时的操作
void visit(BTNode *node)
{printf(%d,node-data);
}
//前序遍历递归
void PreOrder(BTNode *node)
{if(nodeNULL)//当前结点为空时返回上一层递归空间 {printf(#);return;}//结点非空时 visit(node);PreOrder(node-lchild);PreOrder(node-rchild);
}
//前序遍历非递归
void Stack_PreOrder(BTNode *node)
{if(nodeNULL)return;printf(前序遍历-非递归);//创建一个栈存放树结点类型的地址 BTNode* Stack[10];int top-1;//工作指针随着p指针记录树的当前结点位置 BTNode *pNULL;//当树非空时进行操作 if(node !NULL){//入栈 top;Stack[top]node;//随后进行出栈操作只有栈非空时才可出栈 while(top ! -1){//取出此时栈顶元素 pStack[top];top--;//然后进行访问当前结点的相关操作 visit(p);//访问完根在看该根的右孩子入栈 因为是栈先进后出而前序为根左右根出来后右入栈之后左入栈最后出栈是栈顶出 if(p-rchild!NULL){top;Stack[top]p-rchild;}//访问完右孩子在看该根的左孩子入栈 if(p-lchild!NULL){top;Stack[top]p-lchild;} } }
}
//中序遍历-递归
void InOrder(BTNode *node)
{if(nodeNULL){printf(#);return;}InOrder(node-lchild);visit(node);InOrder(node-rchild);
}
//中序遍历-非递归
void StackInOrder(BTNode *node)
{if(nodeNULL)return;printf(中序遍历-非递归:);BTNode* pnode;BTNode* Stack[10];int top-1;do{//当结点不为空时入栈并进入左孩子。 ——访问左孩子 while(p!NULL){top;Stack[top]p;pp-lchild;}//一直遍历左遍历到空此时出栈pStack[top];top--;visit(p);//访问根 pp-rchild;//根访问完随后访问右孩子。随后右孩子中又是新的树然后再进行左根右操作形成循环从上面再来一圈。 }while(top!-1 || p!NULL);//只要树不为空或者栈内有元素就一直进行操作。 }
// 后序遍历-递归
void PostOrder(BTNode *node)
{if(nodeNULL){printf(#);return;}PostOrder(node-lchild);PostOrder(node-rchild);visit(node);
}
//后序遍历-非递归
void StackPostOrder(BTNode *node)
{printf(后序遍历-非递归);if(nodeNULL)return; BTNode *pnode;//工作指针 BTNode *preNULL;//表示上层结点位置 //栈 BTNode *Stack[10];int top-1;//先跟根节点入栈为了方便第一次判断top;Stack[top]p;do{//先判断上层结点是否遍历过没有则进行左子树都入栈入到底if(pre!Stack[top]-lchild pre!Stack[top]-rchild){pStack[top]-lchild;//上次没有遍历过左右孩子那么开始栈顶元素的左孩子入栈操作。while(p!NULL){top;Stack[top]p;pp-lchild; } }//左孩子方向弄到底后开始判断是否需要出栈输出。pStack[top];//记录此时的栈顶元素if(p-rchildNULL || prep-rchild)//如果右孩子为空或者上一层和当前结点的右孩子相等则输出 {prep;//记录当前结点地址 visit(p);//输出 top--;//输出了栈内指针减少 }else{top;Stack[top]p-rchild;//右孩子入栈 } }while(top!-1);
}
int main()
{BTNode* rootCreatTree();//前序遍历打印printf(前序遍历-递归); PreOrder(root);//递归 printf(\n); Stack_PreOrder(root);//非递归栈来做 printf(\n); printf(中序遍历-递归);InOrder(root); printf(\n); StackInOrder(root); printf(\n); printf(后续遍历-递归);PostOrder(root);printf(\n); StackPostOrder(root);return 0;}
5.2运行结果图
