精华内容
下载资源
问答
  •   在之前学习的二叉树遍历(前文传送门)当中,其时间复杂度均为O(1)\mathcal{O}(1)O(1),而空间复杂度为O(n)\mathcal{O}(n)O(n),其或是利用递归调用栈或是数据结构中的栈结构来完成对树中节点的多次访问,也就是...

      在之前学习的二叉树遍历(前文传送门)当中,其时间复杂度均为 O ( 1 ) \mathcal{O}(1) O(1),而空间复杂度为 O ( n ) \mathcal{O}(n) O(n),其或是利用递归调用栈或是数据结构中的栈结构来完成对树中节点的多次访问,也就是利用了辅助空间来实现二叉树的遍历。


    1. 实现思路

    • 将当前所遍历到的节点记为 c u r cur cur;
    • (1) 如果 c u r cur cur无左孩子,则 c u r cur cur迭代为其右子节点,即cur = cur->right;
    • (2) 如果 c u r cur cur有左孩子,则 c u r cur cur的左子树的最右叶子节点记为 m o s t R i g h t mostRight mostRight
      ① 如果 m o s t R i g h t mostRight mostRight的右孩子为空,则将右孩子指针指向当前所遍历的节点(mostRight->right = cur;),同时将当前所遍历的节点 c u r cur cur遍历为其左孩子(cur = cur->left;);
      ② 如果 m o s t R i g h t mostRight mostRight的右孩子指向了当前所遍历的节点 c u r cur cur(mostRight->right == cur;),将其右孩子指向空指针(mostRight->right = nullptr;),同时将当前所遍历节点 c u r cur cur迭代为其右孩子节点(cur = cur->right;)。

    2. 代码实现

    void MorrisTraversal(TreeNode* root) {
    	if(!root) return;
    	TreeNode *cur = root, *mostRight = nullptr;
    	while(cur != nullptr) {
    		mostRight = cur->left;
    		//当前cur节点有左子树,则需先遍历左子树
    		if(mostRight != nullptr) {
    			//寻找当前cur节点左子树的最右节点,包括两种情况:
    			//1.左子树最右节点为nullptr,此时表明cur是第一次遍历到
    			//2.左子树最右节点==cur,此时表明cur是第二次遍历到
    			while(mostRight->right && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//1.cur第一次遍历到
    			if(mostRight == nullptr) {
    				mostRight->right = cur;
    				cur = cur->left;
    			//2.cur第二次遍历到
    			} else {
    				mostRight->right = nullptr;
    				cur = cur->right;
    			}
    		//当前cur节点没有左子树,则直接遍历右子树即可
    		} else {
    			cur = cur->right;
    		}
    	}
    }
    

    以下代码对上面的条件进行了合并,显得有些生涩难懂,但是以下实现均是在该版本上实现的,请知悉:

    void MorrisTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	TreeNode *cur = root, *mostRight = nullptr;	
    	while(cur != nullptr) {
    		mostRight = cur->left; //获取cur的左子树
    		//(1)若cur的左子树不为空
    		if(mostRight != nullptr) { 
    			//寻找cur左子树的最右叶子节点
    			while(mostRight->right != nullptr && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//①若是cur左子树的最右叶子节点为空,则将其指向cur,并将cur迭代至其左孩子节点
    			if(mostRight->right == nullptr) {
    				mostRight->right = cur;
    				cur = cur->left;
    				continue;
    			//②若是左子树的最右叶子节点不为空,则将叶子节点的右孩子指向空,cur迭代至其右孩子节点
    			} else { 
    				mostRight->right = nullptr;
    			}
    		} //(2)若cur的左子树为空;或是cur的左子树不为空,但是左子树已经遍历完毕
    		cur = cur->right;
    	}
    }
    

    3. 分析推导

    3.1 Morris遍历的规律和与递归栈方式的对比

    对下图的二叉树进行分析,可以看出如下规律:

    • (1) 左子树非空的节点会遍历两次
      ① 左子树的最右叶子节点为空时,该节点第一次遍历;
      ② 左子树的最右叶子节点非空时,该节点第二次遍历;
    • (2) 左子树为空的节点只遍历一次

    结合递归方法的二叉树遍历方式(如下代码),进行分析:

    void recursiveTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	//递归栈中的第一次遍历,此时进行输出打印则为前序遍历
    	//cout << root->val << ' ';
    	recursiveTraversal(root->left);
    	//递归栈中的第二次遍历,此时进行输出打印则为中序遍历
    	//cout << root->val << ' ';
    	recursiveTraversal(root->right);
    	//递归栈中的第三次遍历,此时进行输出打印则为后序遍历
    	//cout << root->val << ' ';
    }
    

    可以看到结合节点被遍历的次数,选择合适的输出打印时机,即可得到相应的遍历序列
    那么借鉴选择输出打印时机的这一思路,我们就可以较为便捷的实现 M o r r i s Morris Morris前序遍历和中序遍历了。

    3.2 Morris前序遍历

      在递归栈方式进行前序遍历的过程中,在首次遍历到节点的时候输出该节点的值,即可得到二叉树的先序遍历。

    那么我们要寻找到何时是二叉树中节点第一次遍历,经过 3.1 3.1 3.1节的分析,我们发现:
      (1) 对于左子树不为空的节点,第一次遍历时机是其左子树的最右叶子节点为空的时候;
      (2) 对于左子树为空的节点,第一次遍历时机是 c u r cur cur在当前节点,且当前节点要迭代为 c u r cur cur的右孩子节点 的时候;

    有了如上的分析,则可以实现 M o r r i s Morris Morris前序遍历,代码如下:

    void MorrisPreTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	TreeNode *cur = root, *mostRight = nullptr;	
    	while(cur != nullptr) {
    		mostRight = cur->left; //获取cur的左子树
    		//(1)若cur的左子树不为空
    		if(mostRight != nullptr) { 
    			//寻找cur左子树的最右叶子节点
    			while(mostRight->right != nullptr && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//①若是cur左子树的最右叶子节点为空,则将其指向cur,并将cur迭代至其左孩子节点
    			if(mostRight->right == nullptr) {
    				//★★★时机(1):左子树不为空的节点第一次遍历
    				cout << cur->val << ' ';
    				mostRight->right = cur;
    				cur = cur->left;
    				continue;
    			//②若是左子树的最右叶子节点不为空,则将叶子节点的右孩子指向空,cur迭代至其右孩子节点
    			} else { 
    				mostRight->right = nullptr;
    			} 
    		} else {
    			//★★★时机(2):左子树为空的节点第一次遍历
    			cout << cur->val << ' ';
    		} 
    		//(2)若cur的左子树为空;或是cur的左子树不为空,但是左子树已经遍历完毕
    		cur = cur->right;
    	}
    	cout << endl;
    }
    

    3.3 Morris中序遍历

      中序遍历和前序遍历的分析,其实就是个套娃过程,对于中序遍历,就是在第二次遍历节点的时机进行打印输出。而 3.1 3.1 3.1节的分析中说了,对于左子树为空的节点只有一次遍历,思考一下,中序遍历的顺序是左中右,对于没有左子树的节点而言,其中序遍历和中右别无二样。所以其第一次遍历即可认为是第二次遍历。

    那么可以得到第二次遍历的时机如下:
      (1) 对于左子树不为空的节点,第二次遍历时机是其左子树的最右叶子节点不为空的时候;
      (2) 对于左子树为空的节点,第二次遍历时机是 c u r cur cur在当前节点,且当前节点要迭代为 c u r cur cur的右孩子节点 的时候;

    代码如下:

    void MorrisInTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	TreeNode *cur = root, *mostRight = nullptr;	
    	while(cur != nullptr) {
    		mostRight = cur->left; //获取cur的左子树
    		//(1)若cur的左子树不为空
    		if(mostRight != nullptr) { 
    			//寻找cur左子树的最右叶子节点
    			while(mostRight->right != nullptr && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//①若是cur左子树的最右叶子节点为空,则将其指向cur,并将cur迭代至其左孩子节点
    			if(mostRight->right == nullptr) {
    				mostRight->right = cur;
    				cur = cur->left;
    				continue;
    			//②若是左子树的最右叶子节点不为空,则将叶子节点的右孩子指向空,cur迭代至其右孩子节点
    			} else { 
    				mostRight->right = nullptr;
    			} 
    		} else {
    			//★★★时机(1)&(2):左子树的最右叶子节点非空 或 左子树为空的节点第二(一)次遍历
    			cout << cur->val << ' ';
    		} 
    		//(2)若cur的左子树为空;或是cur的左子树不为空,但是左子树已经遍历完毕
    		cur = cur->right;
    	}
    	cout << endl;
    }
    

    3.4 Morris后序遍历

      对于后序遍历,就无法使用套娃了,因为递归栈方法中的第三次遍历根本就没有啊!!!思路是,使用左子树非空的节点的第二次遍历这个时间节点,①此时逆序输出其左子树的所有右边界边节点,②最后输出整棵二叉树的右边界边界点,至于为啥是可以这么来搞,确实得感叹青出于蓝而胜于蓝(据说Morris只在论文中给出了前序和中序的遍历方法,后序遍历是后来人搞出来的,只能大喊:真牛批!!!)

    画图分析一下,会发现确实是这么回事:

      就是这么神奇,同时注意到 M o r r i s Morris Morris算法实现是空间复杂度为 O ( 1 ) \mathcal{O}(1) O(1)的,所以如何实现不使用辅助空间的限制下逆序打印左子树右边界这一要求呢,哦对了,就是使用链表反转的方法,这里的实现没有进行树的还原,其实,在使用中再调用一次该函数即可实现二叉树的还原。代码如下:

    TreeNode* reverseRightBdry(TreeNode* from) {
    	if(from == nullptr || from->right == nullptr) return from;
    	TreeNode *pre = nullptr, *next = nullptr;
    	while(from != nullptr) {
    		next = from->right; //next节点指向当前节点的右孩子节点
    		from->right = pre; //from的右孩子指针指向其父节点
    		//节点前移
    		pre = from;
    		from = next;
    	}
    	return pre;
    }
    

    那么有了逆序打印的功能实现,就可以完成 M o r r i s Morris Morris后序遍历的过程了,其中链表的反转过程只增加了时间复杂度n的常数系数,所以时间复杂度仍为 O ( n ) \mathcal{O}(n) O(n),代码如下:

    void MorrisPosTraversal(TreeNode* root) {
    	if(root == nullptr) return;
    	TreeNode *cur = root, *mostRight = nullptr;	
    	while(cur != nullptr) {
    		mostRight = cur->left; //获取cur的左子树
    		//(1)若cur的左子树不为空
    		if(mostRight != nullptr) { 
    			//寻找cur左子树的最右叶子节点
    			while(mostRight->right != nullptr && mostRight->right != cur)
    				mostRight = mostRight->right;
    			//①若是cur左子树的最右叶子节点为空,则将其指向cur,并将cur迭代至其左孩子节点
    			if(mostRight->right == nullptr) {
    				mostRight->right = cur;
    				cur = cur->left;
    				continue;
    			//②若是左子树的最右叶子节点不为空,则将叶子节点的右孩子指向空,cur迭代至其右孩子节点
    			} else { //★★★时机:左子树非空的节点的第二次遍历的时间节点
    				mostRight->right = nullptr;
    				printRightBdry(cur->left);
    			} 
    		} 
    		//(2)若cur的左子树为空;或是cur的左子树不为空,但是左子树已经遍历完毕
    		cur = cur->right;
    	}
    	printRightBdry(root);//★★★时机:逆序输出整棵二叉树的右边界节点
    	cout << endl;
    }
    
    void printRightBdry(TreeNode* head) {
    	TreeNode* tail = reverseRightBdry(head); //对二叉树左子树右边界进行反转
    	TreeNode* cur = tail;
    	while(cur != nullptr) {
    		cout << cur->val << ' ';
    		cur = cur->next;
    	}
    	reverseRightBdry(tail); //对二叉树进行还原
    }
    

    4. Morris遍历实例

    NC45 实现二叉树先序,中序和后序遍历,实现代码如下:

    /**
     * struct TreeNode {
     *	int val;
     *	struct TreeNode *left;
     *	struct TreeNode *right;
     * };
     */
    
    class Solution {
    public:
        /**
         * 
         * @param root TreeNode类 the root of binary tree
         * @return int整型vector<vector<>>
         */
        vector<vector<int> > threeOrders(TreeNode* root) {
            // write code here
            vector<vector<int>> ret;
            ret.push_back(morrisPreTraversal(root));
            ret.push_back(morrisInTraversal(root));
            ret.push_back(morrisPostTraversal(root));
            //MorrisPreTraversal(root);
            return ret;
        }
        
    private:
    	//先序遍历
        vector<int> morrisPreTraversal(TreeNode* root) {
            vector<int> ret;
            if(!root) return ret;
            TreeNode *cur = root, *mostRight = nullptr;
            while(cur) {
                mostRight = cur->left;
                if(mostRight) {
                    //while(mostRight->right /*&& mostRight->right != cur*/)
                    while(mostRight->right && mostRight->right != cur)
                        mostRight = mostRight->right;
                    if(!mostRight->right) {
                        ret.push_back(cur->val);
                        mostRight->right = cur;
                        cur = cur->left;
                        continue;
                    } else {
                        mostRight->right = nullptr;
                    }
                } else {
                    ret.push_back(cur->val);
                }
                cur = cur->right;
            }
            return ret;
        }
        
        //中序遍历
        vector<int> morrisInTraversal(TreeNode* root) {
            vector<int> ret;
            if(!root) return ret;
            TreeNode *cur = root, *mostRight = nullptr;
            while(cur) {
                mostRight = cur->left;
                if(mostRight) {
                    while(mostRight->right && mostRight->right != cur) 
                        mostRight = mostRight->right;
                    if(!mostRight->right) {
                        mostRight->right = cur;
                        cur = cur->left;
                        //continue;
                    } else {
                        ret.push_back(cur->val);
                        mostRight->right = nullptr;
                        cur = cur->right;
                    }
                } else {
                    ret.push_back(cur->val);
                    cur = cur->right;
                }
                //cur = cur->right;
            }
            return ret;
        }
        
        //后序遍历
        TreeNode* reverseList(TreeNode* root) {
            if(!root || !root->right) return root;
            TreeNode *cur = root, *pre = nullptr;
            while(cur) {
                TreeNode* next = cur->right;
                cur->right = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
        
        void printPath(vector<int>& ret, TreeNode* head) {
            TreeNode *newHead = reverseList(head), *cur = newHead;
            while(cur) {
                //cout << cur->val << ' ';
                ret.push_back(cur->val);
                cur = cur->right;
            }
            reverseList(newHead);
        }
        
        vector<int> morrisPostTraversal(TreeNode* root) {
            vector<int> ret;
            if(!root) return ret;
            TreeNode *cur = root, *mostRight = nullptr;
            while(cur) {
                mostRight = cur->left;
                if(mostRight) {
                    while(mostRight->right && mostRight->right != cur) 
                        mostRight = mostRight->right;
                    if(!mostRight->right) {
                        mostRight->right = cur;
                        cur = cur->left;
                    } else {
                        mostRight->right = nullptr;
                        printPath(ret, cur->left);
                        cur = cur->right;
                    }
                } else {
                    cur = cur->right;
                }
            }
            printPath(ret, root);
            return ret;
        }
    };
    
    展开全文
  • 本文实现了二叉树的递归遍历和非递归遍历,当然,还包括一些堆栈操作.遍历二叉树本质上是一个堆栈和堆栈的问题. 递归算法简单易懂,但效率始终是一个问题. 非递归算法可以清楚地知道实现的每个步骤的细节,但是乍一...

    060be319cb84caa398588b94ae359ef4.png

    本文实现了二叉树的递归遍历和非递归遍历,当然,还包括一些堆栈操作.

    遍历二叉树本质上是一个堆栈和堆栈的问题. 递归算法简单易懂,但效率始终是一个问题. 非递归算法可以清楚地知道实现的每个步骤的细节,但是乍一看并不想很好地理解递归算法,每个都有其自己的好处. 接下来,根据下图讨论树遍历.

    a68727064fbcd8b573b77a750eb7ea06.png

    bad6103cd494317a3723a40fc78e989c.png

    1. 一阶遍历: 一阶遍历是首先输出根节点,然后是左子树,最后是右子树. 上图中的上一个遍历结果为: ABCDEF

    c6c2a3faf43a3bdd798b330a483c6783.png

    2. 中阶遍历: 中阶遍历是首先输出左子树二叉树的遍历算法c实现,然后是根节点,最后是右子树. 上图中的中间序列遍历结果为: CBDAEF

    3. 后序遍历: 后序遍历是先输出左子树,然后输出右子树二叉树的遍历算法c实现,最后是根节点. 上图的后遍历结果为: CDBFEA

    img_2_788672286D373542272_26.jpg

    其中,用于后序遍历的非递归算法最为复杂. 我使用了一个标识符isOut来指示是否需要弹出打印. 因为仅当打印节点的左右子树时,才能从堆栈中弹出该节点以进行打印,所以当isOut为1且isOut的初始值为0时才打印该节点,主要用于处理非叶节点. 根据后遍历的原则确定,左右子树只能由该节点打印,因此该节点肯定会被访问两次,而不是第一次打印,而第二次打印右子树. 叶子节点打印完成后,将isOut设置为1. (仔细考虑一下,应该有一个逻辑更简单的算法)

    isOut的处理如下:

    537bb555ade2766ae282c2fc7711b42c.png

    以有序遍历为例,查看堆栈内容如何变化:

    571b91a1f9e911602b8da1ff5dbf79d0.png

    具体代码实现如下: 请参见

    本文来自电脑杂谈,转载请注明本文网址:

    http://www.pc-fly.com/a/jisuanjixue/article-182602-1.html

    展开全文
  • 二叉树遍历是指按照一定规律对二叉树中的每个结点进行访问且仅访问一次。其中的访问可知计算二叉树中结点的数据信息,打印该结点的信息们也包括对结点进行任何其他操作。

    数据结构–递归遍历二叉树的c语言实现(超详细注释/实验报告)

    知识小回顾

    二叉树的遍历是指按照一定规律对二叉树中的每个结点进行访问且仅访问一次。其中的访问可知计算二叉树中结点的数据信息,打印该结点的信息们也包括对结点进行任何其他操作。

    实验题目

    输出二叉树的遍历结果

    实验目的

    1. 熟悉二叉树的结点的结构
    2. 采用二叉链表作为存储结构建立二叉树
    3. 采用递归算法对其进行遍历(先序、中序、后序)
    4. 将遍历结果输出
      在这里插入图片描述

    实验要求

    1. 采用二叉链表作为存储结构建立二叉树
    2. 采用递归算法对其进行遍历(先序、中序、后序)
    3. 将遍历结果输出

    实验内容和实验步骤

    1.需求分析

    用户输入二叉树的广义表形式,程序输出二叉树和遍历结果。

    2. 概要设计

    设计创建和输出二叉树的函数以及三种遍历的函数,然后再主函数中调用这几个函数来实现操作。

    3. 详细设计

    建立二叉树并输出二叉树的代码,之前写过了
    创建并输出二叉树
    下面来看看遍历的操作
    因为采用了递归方法,故三种方式都差不多,只用改变一下visit的顺序即可。

    //中序遍历
    void Inorder(BiTree *bt)
    {
        if(bt!=NULL)
        {
            Inorder(bt->lc);
            printf("%c ",bt->data);
            Inorder(bt->rc);
        }
    }
    
    //先序遍历
    void Preorder(BiTree *bt)
    {
        if(bt!=NULL)
        {
            printf("%c ",bt->data);
            Preorder(bt->lc);
            Preorder(bt->rc);
        }
    }
    
    //后序遍历
    void Postorder(BiTree *bt)
    {
        if(bt!=NULL)
        {
            Postorder(bt->lc);
            Postorder(bt->rc);
            printf("%c ",bt->data);
        }
    }
    

    主函数部分,把程序功能打印出来,并对用户做一个引导。
    在这里插入图片描述

    int main()//(A(B(D,),C(,E)))   (A(B(D,E),C(F,G)))  ((((A),B)),(((),D),(E,F)))这个不是树
    //来个波兰表达式的例子 (-(+(a,*(b,c)),/(d,e)))
    {
        BiTree *bt;
        char *gyb,str[MAXSIZE];
        int j=1;
        printf("-------------------------------------------------------");
        printf("\n            程序功能");
        printf("\n 1.将按照输入的二叉广义表表示字符串 ");
        printf("\n · 生成对应的二叉树链式结构。");
        printf("\n 2.输出二叉树的凹入法表示形式。");
        printf("\n · G--根 L--左孩子 R--右孩子");
        printf("\n 3.树状打印二叉树。");
        printf("\n · 逆时针旋转90度显示二叉树");
        printf("\n 4.打印出先序、中序和后续遍历的结果。");
        printf("\n * 输入示例:(A(B(D,),C(,E)))或(-(+(a,*(b,c)),/(d,e)))");
        printf("\n-------------------------------------------------------\n");
        printf("请输入二叉树的广义表形式:\n");
        gyb=str;
        scanf("%s",str);
        bt =CreatBiTreepre(gyb);
        printf("二叉树建立成功!\n");
        printf("此二叉树的凹入法表示为:\n");
        OutBiTree(bt);
        printf("树状打印二叉树:\n");
        PrintTree(bt,1);
        printf("先序遍历序列为:\n");
        Preorder(bt);
        printf("\n中序遍历序列为:\n");
        Inorder(bt);
        printf("\n后序遍历序列为:\n");
        Postorder(bt);
        return 0;
    }
    

    在这里插入图片描述

    4. 调试分析

    遇到的问题及解决方法

    • 有了前面创建和输出二叉树做铺垫,实现递归的遍历算法还是很简单的。

    算法的时空分析

    设二叉树有n个结点,对每个结点都要进行一次入栈和出栈的操作,即入栈和出栈各执行n次,对结点的访问也是n次。这些二叉树递归遍历算法的时间复杂度为 O ( n ) O(n) O(n)

    实验结果

    实验结果很不错,所有操作都能正常执行,用波兰表达式做例子得到了正确的输出。
    这是上面分析的例子的程序给出的输出。

    下面这个例子大家也可以看看。
    在这里插入图片描述

    实验总结

    有了前面工作的铺垫,递归遍历就很简单了,多多重复,百炼成钢!

    最后附上完整的代码

    #include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 255
    //定义二叉树的链式存储结构,有三个域:数据域,左孩子域,右孩子域
    typedef struct BiNode
    {
        char data;
        struct BiNode *lc;
        struct BiNode *rc;
    }BiTree;
    
    //以广义表的形式创建二叉树
    BiTree *CreatBiTreepre(char *str)
    {
        BiTree *bt,*stack[MAXSIZE],*p=NULL;
        int top=-1,k,j=0;
        char ch;
        bt=NULL;
        ch=str[j];
        while(ch!='\0')
        {
            switch(ch)
            {
            case '(':
                {
                    top++;
                    stack[top]=p;
                    k=1;
                    break;
                }
            case ')':
                {
                    top--;
                    break;
                }
            case ',':
                {
                    k=2;
                    break;
                }
            default:
                {
                    p=(BiTree *)malloc(sizeof(BiTree));
                    p->data=ch;
                    p->lc=p->rc=NULL;
                    if(bt==NULL)
                    {
                        bt=p;
                    }
                    else
                    {
                        switch(k)
                        {
                        case 1:
                            {
                                stack[top]->lc=p;
                                break;
                            }
                        case 2:
                            {
                                stack[top]->rc=p;
                                break;
                            }
                        }
                    }
                }
            }
            j++;
            ch=str[j];
        }
        return bt;//链式存储只用知道一个,后面顺藤摸瓜就都知道了
    }
    
    //采用凹入法输出二叉树
    void OutBiTree(BiTree *bt)
    {
        BiTree *stack[MAXSIZE],*p;
        int feature[MAXSIZE][2],top,n,i,width=4;
        char type;
        if(bt!=NULL)
        {
            top=1;
            stack[top]=bt;
            feature[top][0]=width;
            feature[top][1]=2;
            while(top>0)
            {
                p=stack[top];
                n=feature[top][0];
                switch(feature[top][1])
                {
                case 0:
                    {
                        type='l';
                        break;
                    }
                case 1:
                    {
                        type='R';
                        break;
                    }
                case 2:
                    {
                        type='G';
                        break;
                    }
                }
                for(i=1;i<=n;i++)
                    printf(" ");
                printf("%c(%c)\n",p->data,type);
                top--;
                if(p->lc!=NULL)
                {
                    top++;
                    stack[top]=p->lc;
                    feature[top][0]=n+width;
                    feature[top][1]=0;
                }
                if(p->rc!=NULL)
                {
                    top++;
                    stack[top]=p->rc;
                    feature[top][0]=n+width;
                    feature[top][1]=1;
                }
    
            }
        }
    }
    
    void PrintTree(BiTree *bt,int nLayer)
    {
        if(bt==NULL)
            return ;
        PrintTree(bt->rc,nLayer+1);
        for(int i=0;i<nLayer;i++)
            printf("  ");
        printf("%c\n",bt->data);
        PrintTree(bt->lc,nLayer+1);
    }
    
    //中序遍历
    void Inorder(BiTree *bt)
    {
        if(bt!=NULL)
        {
            Inorder(bt->lc);
            printf("%c ",bt->data);
            Inorder(bt->rc);
        }
    }
    
    //先序遍历
    void Preorder(BiTree *bt)
    {
        if(bt!=NULL)
        {
            printf("%c ",bt->data);
            Preorder(bt->lc);
            Preorder(bt->rc);
        }
    }
    
    //后序遍历
    void Postorder(BiTree *bt)
    {
        if(bt!=NULL)
        {
            Postorder(bt->lc);
            Postorder(bt->rc);
            printf("%c ",bt->data);
        }
    }
    
    int main()//(A(B(D,),C(,E)))   (A(B(D,E),C(F,G)))  ((((A),B)),(((),D),(E,F)))这个不是树
    //来个波兰表达式的例子 (-(+(a,*(b,c)),/(d,e)))
    {
        BiTree *bt;
        char *gyb,str[MAXSIZE];
        int j=1;
        printf("-------------------------------------------------------");
        printf("\n            程序功能");
        printf("\n 1.将按照输入的二叉广义表表示字符串 ");
        printf("\n · 生成对应的二叉树链式结构。");
        printf("\n 2.输出二叉树的凹入法表示形式。");
        printf("\n · G--根 L--左孩子 R--右孩子");
        printf("\n 3.树状打印二叉树。");
        printf("\n · 逆时针旋转90度显示二叉树");
        printf("\n 4.打印出先序、中序和后续遍历的结果。");
        printf("\n * 输入示例:(A(B(D,),C(,E)))或(-(+(a,*(b,c)),/(d,e)))");
        printf("\n-------------------------------------------------------\n");
        printf("请输入二叉树的广义表形式:\n");
        gyb=str;
        scanf("%s",str);
        bt =CreatBiTreepre(gyb);
        printf("二叉树建立成功!\n");
        printf("此二叉树的凹入法表示为:\n");
        OutBiTree(bt);
        printf("树状打印二叉树:\n");
        PrintTree(bt,1);
        printf("先序遍历序列为:\n");
        Preorder(bt);
        printf("\n中序遍历序列为:\n");
        Inorder(bt);
        printf("\n后序遍历序列为:\n");
        Postorder(bt);
        return 0;
    }
    
    
    展开全文
  • 复杂度分析:显然这里cur1,cur2不会回退时间复杂度O(n); 其次,对于无法通过过序列的值访问结点的情况,即步骤二无法直接访问到对应结点的情况,可通过哈希方法记录对应序列的值和结点的指针,这样来时间复杂度仍...

    先序和中序参考另一篇文章蓝桥杯试题 算法训练 绘制地图—O(n)复杂度重建整棵树

    和由前序中序推后序类似

    输入:

    第一行一个整数n,表示节点编号1~n。
    第二行n个整数,表示后序遍历。
    第三行n个整数,表示中序遍历。
    算法过程:
    post[n]为后序序列 in[n]为中序序列 vis[n]记录是否已在后序序列中出现

    初始两个下标cur1=n-1,cur2=n-1
    1.当post[cur1]!=in[cur2]时 cur1往后退一格,并且post[cur1]号结点的右孩子为post[cur1-1]号结点 并记录vis[post[cur-1]]=1。

    while (in[cur2] != post[cur1]) {
    	tree[post[cur1]].right = post[cur1 - 1];
    	vis[post[cur1 - 1]] = 1;
    	cur1--;
    }

    2.此时post[cur1]==in[cur2],我们让cur2后退,直到in[cur2]号结点未出现过,即vis[in[cur2]]=0

    while (vis[in[cur2]]) {
    	cur2--;
    }

    3.这时令in[cur2+1]号结点的左孩子为pre[cur1-1],cur1后退一格

    tree[in[cur2 + 1]].left = post[cur1 - 1];
    vis[post[cur1 - 1]] = 1;
    cur1--;


    重复1,2,3 直至cur1或cur2走到0。

    下面演示一组例子执行过程 

    绿色代表中序数组的进展 黄色代表通过步骤3连结的结点

    注意在最后一张图片中 后序数组已经走到起点 即cur1已经为0(中序数组没有走完)


    下面证明

    每次中序序列后退时第一个未在后序序列中出现的节点的后一个结点(cur2+1)是后序序列中下一个结点(cur1-1)的父亲(父亲和左孩子)
     

    由于该点的后一个点(cur2+1)在已经遍历过的后序序列中出现,那么因为中序遍历的性质,后一个点的右子树上任一个点必在该之后被遍历到,即后一点右子树上任意一点已在后序序列中出现过,并且由中序遍历性质还可得到该点为后一个点的左子树上的结点(反证法:显然该点不可能在前一点的右子树,如果为前一点的父亲/长辈结点,那么该点一定在后序序列中出现过 从而产生矛盾,这是因为后序遍历任何一个结点必在其子结点后被遍历到)而且为左子树上最右的节点。那么因为在后序序列中(从后往前)左子树上最右的结点都没有出现过,从而整棵左子树上的结点都没有出现过(反过来就是都已被遍历完),综上:
    1.后一个结点(cur2+1)的右子树在后序遍历中未被遍历过
    2.后一个结点(cur2+1)的左子树在后序遍历中已遍历完  
    (注意这里遍历完的意思是从前往后的顺序已经遍历完)
    那么可以得出结论中序序列后一个点的左孩子就是后序遍历序列中的下一个结点(从后往前)。
    这里多解释一下,后一个节点的左子树的根节点在后序遍历中一定最后被遍历到,那么在序列中的顺序就是从后往前的下一个结点。

    复杂度分析:显然这里cur1,cur2不会回退时间复杂度O(n);

    其次,对于无法通过过序列的值访问结点的情况,即步骤二无法直接访问到对应结点的情况,可通过哈希方法记录对应序列的值和结点的指针,这样来时间复杂度仍是O(n)的。

    #include<bits/stdc++.h>
    using namespace std;
    int	n;
    struct bitnode {
    	int left, right;
    	bitnode() :left(0), right(0) {}
    };
    const int maxn = 1e5 + 5;
    int post[maxn], in[maxn], vis[maxn];
    int root;
    bitnode tree[maxn];
    void solve() {
    	root = post[n-1];
    	vis[post[n-1]] = 1;
    	int cur1 = n-1, cur2 = n-1;
    	while (cur1 > 0 || cur2 > 0) {
    		//当post[cur1]!=in[cur2]时,cur1往后退一格
    		//并且post[cur1]号结点的左孩子为post[cur1-1]号结点,并记录vis[post[cur-1]]=1。
    		while (in[cur2] != post[cur1]) {
    			tree[post[cur1]].right = post[cur1 - 1];
    			vis[post[cur1 - 1]] = 1;
    			cur1--;
    		}
    		//此时post[cur1]==in[cur2],我们让cur2后退
    		//直到in[cur2]号结点未出现过,即vis[in[cur2]]=0
    		while (vis[in[cur2]]) {
    			cur2--;
    		}
    		//这时令in[cur2+1]号结点右孩子为pre[cur1-1],cur1后退一格 
    		tree[in[cur2 + 1]].left = post[cur1 - 1];
    		vis[post[cur1 - 1]] = 1;
    		cur1--;
    	}
    }
    void preorder(int root)
    {
    	cout << root << " ";
    	if (tree[root].left) {
    		preorder(tree[root].left);
    	}
    	if (tree[root].right) {
    		preorder(tree[root].right);
    	}
    }
    /*
    9
    5 4 2 6 8 9 7 3 1
    4 5 2 1 6 3 8 7 9
    */
    int main() {
    	cin >> n;
    	for (int i = 0; i < n; i++) {
    		cin >> post[i];
    	}
    	for (int i = 0; i < n; i++) {
    		cin >> in[i];
    	}
    	clock_t s = clock();
    	solve();
    	clock_t e = clock();
    	//cout << e - s;
    	preorder(root);
    	return 0;
    }

     

    展开全文
  • 二叉树链式存储的前中后递归和非递归遍历实现 1. 二叉树的链式存储结构 #define ElementType char typedef struct BTNode{ ElementType data; struct BTNode *left,*right; }BTNode,*BinTree; 2. 二叉树的前序、...
  • 中序遍历二叉树递归、迭代、Morris算法) 三种算法时间、空间复杂度的比较: 算法 时间复杂度 空间复杂度 递归 O(n) O(n) 迭代 O(n) O(n) Morris O(n) O(1) 定义树节点 public class TreeNode { ...
  • 笔者编码10载,面过很多程序员简历上写着熟悉数据结构和算法,但是对于时间复杂度稍微深入点的问题,都回答的不怎么样,其实还是没懂 搞懂算法时间复杂度是一个优先程序员的分水岭 先来看letcode一道题, 泰波那契...
  • 如果根结点存在,结点入栈,并把结点的右子树遍历结果置为0,代表没遍历;把root指向左子树;如果栈不为空,判断栈顶元素右子树是否存在以及是否已经遍历,如果存在并且没有遍历,则把root指向右子树;否则,结点...
  • 二叉树的结构体定义: struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} ...
  • morris 遍历遍历完一棵二叉树,可以实现二叉树的先序中序后序,可以做到时间复杂度O(N),额外空间复杂度O(1) 笔试以最快Ac为目标,面试时候可以吹牛逼 kmp 的 morris 和 morris遍历中的morris 是一个人 二叉树的...
  • (1)这种递归方式类似于"二叉树的后序遍历"。 (2)在每个递归层次上,我们首先对所有子节点递归地调用函数,然后根据返回值和根节点本身的值得到答案。 (3)“自底向上” 的递归函数 bottom_up(root) 为如下所示...
  • 给你二叉树的根节点 root ,返回它节点值的 前序 遍历。 示例 1: 输入:root = [1,null,2,3] 输出:[1,2,3] 示例 2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1] 输出:[1] 示例 4: 输入:root = ...
  • 二叉树递归和非递归方式中序遍历 方法一:递归 思路与算法 首先我们需要了解什么是二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树() (前序和后序遍历方式一样,就是打印root节点时,前序...
  • } // 二叉树的先序遍历递归算法 public static void preOrder(TreeNode treeNode) { if (treeNode != null) { System.out.print(treeNode.val + " "); preOrder(treeNode.left); preOrder(treeNode.right); } } ...
  • 0 题目描述 leetcode原题链接:剑指 Offer 55 - II. 平衡二叉树 1 自顶向下的递归 这道题中的平衡二叉树的定义是:二叉树的每个节点的左右子树的高度差的绝对值不超过 11,则...具体做法类似于二叉树的前序遍历,即对
  • 要求时间复杂度在O(N)以内。N为节点个数。 思路分析 求二叉树节点个数,第一反应就是常规遍历了,但是题目要求必须O(N)以内,再加上给的是完全二叉树。因此,此题肯定要利用完全二叉树的性质,来简化。 第一步,分析...
  • 不管是迭代遍历还是递归遍历二叉树遍历都只做了三件事:处理左子树,处理右子树,处理当前结点。 依据处理当前结点的时机不同,可分为:先序、中序、后序三种遍历方式。 二叉树迭代遍历的主要难点在于:如何在处理...
  • 如果直接用递归中序遍历存到数组中,然后输出,这样的时间复杂度是O(n) 为了只用O(h)的空间,我们采用非递归迭代策略。 思路: 能往左走就往左走,边走边入栈,直到不能走,弹出栈里元素往右走,重复之前操作。 ...
  • 二叉树的先中后序递归与非递归遍历 先序遍历二叉树: 若二叉树为空,则空操作。否则 (1)访问根结点; (2)先序遍历左子树; (3)先序遍历右子树。 中序遍历二叉树: 若二叉树为空,则空操作。否则 (1)中序遍历...
  • 其中,时间复杂度和空间复杂度都是O(n), 二叉树遍历递归算法不常考,主要考察非递归❤ 先序、中序、后序遍历递归递归算法的区别在于visit()函数的位置❤,代码以先序遍历为例,其顺序为根左右,if判断语句...
  • 前序遍历的复杂性

    2021-04-04 17:46:01
    二叉树中元素数目为n。遍历算法的空间复杂性均为O (n),时间复杂性为O(n)。 当t 的高度为n时(右斜二叉树的情况),通过观察其前序、中序和后序遍历时所使用的递归栈空间即可得到上述结论。 ...
  • 时间复杂度O(n) 空间复杂度O(n) 2.迭代 -关键词:层次遍历 -模式识别:一旦出现树的层次遍历,都可以用队列作为辅助结构 //二叉树的层序遍历 //递归 dfs func levelOrder1(root *TreeNode) [][]int { ans...
  • 一文通吃二叉树遍历的恩怨情仇(递归、非递归和Morris遍历) 文章目录一文通吃二叉树遍历的恩怨情仇(递归、非递归和Morris遍历)一、递归二、非递归三、Morris巧妙的遍历四、总结 这里的讨论以节点的方式存储的...
  • 层次遍历二叉树并不难,主要是队列的操作比较陌生(之前惯用栈),在这里记录一下 我这里用队列存储结点,每层循环后逐个弹出,进行一个结点进行迭代 class Solution { public int[] levelOrder(TreeNode root) ...
  • 二叉树的三种遍历方式及其分析 1,查找的两种方式 2,静态查找的方式: A 顺序查找-建立哨兵 遇到哨兵时循环退出 时间复杂度为O(n)。运气好第一个是,运气不好最后一个是,平均时间复杂度是O(N/2)。 B 二...
  • 二叉树的前中后序遍历
  • 目录 ...2.二叉树的先序、中序、后序遍历递归和非递归) 3.层次遍历 4.树的深度 5.所有结点树、叶子结点数、度为1的结点数 6.判断是否为完全二叉树、判断是否为满二叉树 创建二叉树 ...
  • (递归实现前中后序遍历,时间复杂度O(N),空间复杂度O(H),H为二叉树高度) 利用Morris算法可实现将空间复杂度降为O(1),时间复杂度不变。 实现Morris并利用Morris实现前中后序遍历和搜索二叉树的判断(java实现) 递归...
  • 递归版的先中后序遍历 (一)先序遍历算法 访问根节点 对根节点的左子树进行先序遍历 对根节点的右子树进行先序遍历 function preorder (node) { if (!node) return; console.log(node.val) preorder(node.left) ...
  • 遍历思想:遍历二叉树采用递归的方式,首先要理解递归的思想。 遍历是要先判断根节点是否为空,如果不为空时,再向下遍历。 二叉树的遍历: 按某条搜索路径访问树中某个节点,树的每个节点均被访问依次,且只...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,067
精华内容 15,226
关键字:

时间复杂度递归遍历二叉树