简约好看的网站,常州网站建设方案外包,页面布局方式,2002年网站建设公司二叉树遍历分为三种#xff1a;前序、中序、后序#xff0c;其中序遍历最为重要。为啥叫这个名字#xff1f;是根据根节点的顺序命名的。比如上图正常的一个满节点#xff0c;A#xff1a;根节点、B#xff1a;左节点、C#xff1a;右节点#xff0c;前序顺序是ABC(根节…二叉树遍历分为三种前序、中序、后序其中序遍历最为重要。为啥叫这个名字是根据根节点的顺序命名的。比如上图正常的一个满节点A根节点、B左节点、C右节点前序顺序是ABC(根节点排最先然后同级先左后右)中序顺序是BAC(先左后根最后右)后序顺序是BCA(先左后右最后根)。比如上图二叉树遍历结果前序遍历ABCDEFGHK中序遍历BDCAEHGKF后序遍历DCBHKGFEA分析中序遍历如下图中序比较重要(java很多树排序是基于中序后面讲解分析)下面介绍一下二叉树的三种遍历方式其中每一种遍历方式都有三种实现方式。节点定义struct TreeNode{int val;TreeNode *left,*right;TreeNode(int val){this-val val;this -left this-right NULL;}};先序遍历以上面这张图为例我们讲讲树的三种遍历方式先序遍历先访问根节点然后访问左孩子最后访问右孩子。所以上面遍历的结果是GEDACHS。下面我们来看看具体代码实现1.递归实现void preOrder(TreeNode *root){if (rootNULL)return;coutvalpreOrder(root-left);preOrder(root-right);}2.使用辅助栈实现思路1.将根节点入栈2.每次从栈顶弹出一个节点访问该节点3.把当前节点的右孩子入栈4.把当前节点的左孩子入栈具体实现void preOrder2(TreeNode *root){if (root NULL)return;stack stk; //开辟一个栈空间stk.push(root);while(!stk.empty()){TreeNode* pNode stk.pop();coutval;if (pNode-right!NULL)stk.push(pNode-right);if (pNode-left!NULL)stk.push(pNode-left);}}3.Morris遍历Morris遍历常数的空间即可在O(n)时间内完成二叉树的遍历。O(1)空间进行遍历困难之处在于在遍历的子结点的时候如何重新返回其父节点在Morris遍历算法中通过修改叶子结点的左右空指针来指向其前驱或者后继结点来实现的。其本质线索二叉树(Threaded Binary Tree)通过利用叶子节点空的right指针指向中序遍历的后继节点从而避免了对 stack 的依赖。具体实现void preOrder(TreeNode* root){if (root NULL)return;TreeNode* pNode root;while(pNode ! NULL){if (pNode-left NULL){coutvalpNode pNode-right;}else{TreeNode* pPre pNode-left;while(pPre-right ! NULL pPre-right ! pNode){pPre pPre-right;}if (pPre-right NULL){/* code */pPre-right pNode;coutvalpNode pNode-left;}else{pPre-right NULL;pNode pNode-right;}}}}中序遍历中序遍历先访问左孩点然后访问根节点最后访问右孩子。所以上面遍历的结果是DEAGHCS。下面我们来看看具体代码实现1.递归实现void InOrder(TreeNode *root){if (rootNULL)return;InOrder(root-left);coutvalInOrder(root-right);}2.使用辅助栈实现思路初始化一个二叉树结点pNode指向根结点若pNode非空那么就把pNode入栈并把pNode变为其左孩子(直到最左边的结点)若pNode为空弹出栈顶的结点并访问该结点将pNode指向其右孩子(访问最左边的结点并遍历其右子树)具体实现void InOrder(TreeNode *root){if (rootNULL){return;}stack stk;TreeNode *pNode root;while(pNode!NULL || !stk.empty()){if (pNode ! NULL){stk.push(pNode);pNode pNode-left;}else{pNode stk.pop();stk.pop();coutvalpNode pNode-right;}}}3.Morris遍历实现思路1.如果当前节点pNode的左孩子为空那么输出该节点并把该节点的右孩子作为当前节点2.如果当前节点pNode的左孩子非空那么找出该节点在中序遍历的前驱结点prev当第一次访问该前驱结点prev时其右孩子必定为空那么就将其右孩子设置为当前结点以便根据这个指针返回到当前结点pNode中并将当前结点pNode设置为其左孩子当该前驱结点pPre的右孩子为当前结点那么就输出当前结点并把前驱结点的右孩子设置为空(恢复树的结构)将当前结点更新为当前结点的右孩子3.重复以上两步直到当前结点为空。具体实现void InOrder(TreeNode *root){if (root NULL)return;TreeNode* pNode root;while(pNode ! NULL){if (pNode-left NULL){coutvalpNode pNode-right;}else{TreeNode* pPre pNode-left;while(pPre-right ! NULL pPre-right ! pNode){pPre pPre-right;}if (pPre-right NULL){/* code */pPre-right pNode;pNode pNode-left;}else{pPre-right NULL;coutvalpNode pNode-right;}}}}后序遍历后序遍历先访问左孩子然后访问右孩子最后访问根节点。所以上面遍历的结果是DAEHSCG。下面我们来看看具体代码实现1.递归实现void PostOrder(TreeNode *root){if (rootNULL)return;PostOrder(root-left);PostOrder(root-right);coutval}2.使用辅助栈void postOrder(TreeNode *root) {if(root NULL)return;stack stk;stk.push(root);TreeNode *prev NULL;while(!stk.empty()) {TreeNode *pNode stk.top();if(!prev || prev-left pNode || prev-right pNode) { // traverse downif(pNode-left)stk.push(pNode-left);else if(pNode-right)stk.push(pNode-right);/* else {cout pNode-val endl;stk.pop();}*/}else if(pNode-left prev) { // traverse up from leftif(pNode-right)stk.push(pNode-right);}/* else if(pNode-right prev) { // traverse up from rightcout pNode-val endl;stk.pop();}*/else {cout pNode-val endl;stk.pop();}prev pNode;}}双辅助栈实现思路设置两个栈stk, stk2将根结点压入第一个栈stk弹出stk栈顶的结点并把该结点压入第二个栈stk2将当前结点的左孩子和右孩子先后分别入栈stk当所有元素都压入stk2后依次弹出stk2的栈顶结点并访问之。第一个栈的入栈顺序是根结点左孩子和右孩子于是压入第二个栈的顺序是根结点右孩子和左孩子。因此弹出的顺序就是左孩子右孩子和根结点。void PostOrder2(TreeNode *root){ //两个栈实现if (root NULL)return;stack stk,stk2;stk.push(root);while(!stk.empty()){TreeNode* pNode stk.top();stk.pop();stk2.push(pNode);// 将根节点压栈if (pNode-left ! NULL) // 如果左孩子不为空则压栈{stk.push(pNode-left);}if (pNode-right ! NULL) // 如果左孩子不为空则压栈{stk.push(pNode-right);}}while(!stk2.empty()){coutvalstk2.pop();}}3.Morris遍历实现实现思路1.先建立一个临时结点dummy并令其左孩子为根结点root将当前结点设置为dummy2.如果当前结点的左孩子为空则将其右孩子作为当前结点3.如果当前结点的左孩子不为空则找到其在中序遍历中的前驱结点-如果前驱结点的右孩子为空将它的右孩子设置为当前结点将当前结点更新为当前结点的左孩子-如果前驱结点的右孩子为当前结点倒序输出从当前结点的左孩子到该前驱结点这条路径上所有的结点。将前驱结点的右孩子设置为空将当前结点更新为当前结点的右孩子。4.重复以上过程直到当前结点为空。具体实现void reverse(TreeNode* p1,TreeNode *p2){if (p1 p2)return;TreeNode* x p1;TreeNode* y p1-right;while(true){TreeNode* tmp y-right;y-right x;x y;y tmp;if (x p2)break;}}void printReverse(TreeNode* p1,TreeNode *p2){reverse(p1,p2);TreeNode* pNode p2;while(true){coutvalif (pNode p1)break;pNode pNode-right;}reverse(p2,p1);}void PostOrder3(TreeNode* root){if(root NULL)return;TreeNode *dummy new TreeNode(-1);dummy-left root;TreeNode *pNode dummy;while(pNode ! NULL) {if(pNode-left NULL)pNode pNode-right;else {TreeNode *pPrev pNode-left;while(pPrev-right ! NULL pPrev-right ! pNode)pPrev pPrev-right;if(pPrev-right NULL) {pPrev-right pNode;pNode pNode-left;}else {printReverse(pNode-left, pPrev);pPrev-right NULL;pNode pNode-right;}}}}总结上述三种遍历方式时间复杂度和空间复杂度分析1.递归遍历和非递归遍历 时间复杂度0(n) 空间复杂度O(n)2.Morris遍历 时间复杂度0(n) 空间复杂度O(1)以上就是本文的全部内容希望对大家的学习有所帮助也希望大家多多支持。
