精华内容
下载资源
问答
  • 二叉树后序遍历

    2020-07-29 18:16:26
    非递归、非栈二叉树后序遍历 二叉树的后序遍历为LRN形式,它的访问顺序与NRL形式的访问顺序是相反的,即若LRN的顺序为1,2,3,则NRL的顺序为3,2,1。 NRL访问与NLR(前序遍历)访问的方法是类似,通过与Morris前序遍历...

    二叉树结点定义

    struct TreeNode {
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    };
    

    非递归、非栈二叉树后序遍历

    1. 二叉树的后序遍历为LRN形式,它的访问顺序与NRL形式的访问顺序是相反的,即若LRN的顺序为1,2,3,4,5,则NRL的顺序为5,4,3,2,1。
    2. NRL访问与NLR(前序遍历)访问的方法是类似,通过与Morris前序遍历的简单修改可以得到NRL的遍历结果。
    3. 综上,可以先求出NRL的遍历结果,然后遍历结果的相反顺序就是后序遍历的结果
    vector<int> postorder(TreeNode *root){
    	vector<int> traversal;
    	TreeNode *p = root;
    	while(p!=nullptr){
    		if(p->right!=nullptr){
    			TreeNode *tmp = p->right;
    			while(tmp->left!=nullptr && tmp->left!=p)tmp=tmp->left;
    			if(tmp->left==nullptr){ // p还没有被访问
    				traversal.push_back(p->val);
    				tmp->left = p; // N
    				p = p->right; // R
    			}else{
    				tmp->left = nullptr; // p已经被访问过了
    				p = p->left; // L
    			}
    		}else{
    			traversal.push_back(p->val);
    			p = p->left;
    		}
    	}
    	return vector<int>(traversal.rbegin(), traversal.rend()); // NRL访问结果的逆序就是后序遍历的结果
    }
    
    展开全文
  • 本文运用网格环境下的并行计算模型G-PRAM来研究二叉树的后序遍历问题,提出了二叉树后序遍历的一种并行算法,并给出示例和说明。
  • 二叉树后序遍历寻找结点路径

    千次阅读 2019-07-16 00:48:19
    二叉树后序遍历

    LEETCODE236. 二叉树的最近公共祖先
    1. 二叉树后序遍历算法(LRN),通过该算法最后访问根节点等特性,能找到根节点到二叉树中特定结点的路径,或者说能找到二叉树中特定结点的所有祖先。
    2. 方法:在二叉树后序非递归遍历过程中,进左子树不说,进入右子树由于根结点不出栈,所以可以通过栈获取路径。访问到目标结点(后序非递归会有两次访问root,注意区分),此时栈中存放的元素即为从当前结点到根节点的路径。
    在这里插入图片描述

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    //对于上图4,则打印2 5 3
    typedef struct TreeNode* Tree;
    typedef struct{
        Tree* array;
        int top;
    }Stack;
    
    struct TreeNode* getAncestor(struct TreeNode* root, struct TreeNode* p) {    
        Stack* s=(Stack *)malloc(sizeof(Stack));
        s->array=(Tree *)malloc(100*sizeof(Tree));
        s->top=0;
        Tree t=NULL;										//最近访问节点
        while(root||s->top){					
            if(root){            
                s->array[s->top++]=root;          	    
                root=root->left;        	    	    
            }
            else{
                root=s->array[s->top-1];
                if(root->right&&root->right!=t){
                    root=root->right;    
                }
                else{				                     //真正访问到节点
                    root=s->array[--s->top];       	    
                    if(root==p){						 //找到
                        while(s->top){                   //打印出栈中元素
                            printf("%d ",s->array[--s->top]->val);   
                        }                    
                    }
                    t=root;
                    root=NULL;
                }            
            }
        }
        return p;
    }
    
    展开全文
  • 二叉树后序遍历算法

    2016-05-04 19:54:34
    二叉树后序遍历

    二叉树后序遍历算法


    #include <iostream>
    //#include <climits>
    using namespace std;


    #define  MAXNUM 50
    typedef int Elemtype;
    typedef struct BiTNode 
    {
    Elemtype data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
    }BiTNode,*BiTree;


    typedef struct
    {
    BiTree bt;
    int tag;       // 标签
    }Elem;


    typedef struct sqStack         //  栈
    {
    Elem s_elem[MAXNUM];       
    int top;
    }sqStack;


    void InitStack(sqStack &s)      //  初始化栈
    {
    s.top=-1;
    }
    bool IsEmpty(sqStack s)      //  判断栈是否为空
    {
    if (s.top==-1)
    return true;
    else
    return false;
    }


    bool Push(sqStack &s,Elem e)            //  进栈
    {
    if ((s.top+1)==MAXNUM)   //  栈满    
    return false;
    s.s_elem[++s.top]=e;
    return true;
    }


    bool Pop(sqStack &s,Elem &e)            //  出栈
    {
    if (s.top==-1)   //  栈满    
    return false;
    e=s.s_elem[s.top--];
    return true;
    }


    bool GetTop(sqStack s,Elem &e)         //  获取栈顶元素
    {
    if (s.top==-1)   //  栈满    
    return false;
    e=s.s_elem[s.top];
    return true;
    }
    void CreateBiTree(BiTree &T)
    {
    Elemtype data;
    scanf("%d",&data);


    if(data!=99)
    {
    T=new BiTNode;
    T->data=data;
    T->lchild=NULL;
    T->rchild=NULL;
    CreateBiTree(T->lchild);
    CreateBiTree(T->rchild);
    }
    }

    void PostOrder(BiTree T)     //  二叉树非递归后序遍历
    {
    sqStack s;


    InitStack(s);
    BiTNode *p=T;     //  指向头结点
    do 
    {
    while (p)
    {
    Elem et;
    et.bt=p;
    et.tag=1;
    Push(s,et);
    p=p->lchild;        //  将左孩子全部进栈
    }
    if (!IsEmpty(s))
    {
    Elem ee;
    Pop(s,ee);            
    if (ee.tag==1){
    ee.tag=2;
    p=ee.bt->rchild;
    Push(s,ee);

    else{
    cout<<ee.bt->data<<"  ";
    }
    }
    } while (!IsEmpty(s));
    }

    展开全文
  • 数据结构实验之求二叉树后序遍历和层次遍历 Description 已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历和层序遍历。 Input 输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括...

    数据结构实验之求二叉树后序遍历和层次遍历
    Description
    已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历和层序遍历。

    Input
    输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的先序遍历序列,第二个字符串表示二叉树的中序遍历序列。

    Output
    每组第一行输出二叉树的后序遍历序列,第二行输出二叉树的层次遍历序列。

    Sample
    Input
    2
    abdegcf
    dbgeafc
    xnliu
    lnixu
    Output
    dgebfca
    abcdefg
    linux
    xnuli

    /*需要好好学习一下这个层次遍历
    void cengci(node *T)
    {
        queue<node *>t;
        t.push(T);
        while(!t.empty())
        {
            T = t.front();
            t.pop();
            if(T)
            {
                cout<<T->data;
                t.push(T->l);
                t.push(T->r);
            }
        }
    }
    */
    ```cpp
    #include<bits/stdc++.h>
    
    using namespace std;
    typedef struct node
    {
        char data;
        node *l;
        node *r;
    } node;
    node *buildtree(int len, char *pre, char *mid)
    {
        if(!len)
        {
            return NULL;
        }
        node *root;
        root = new(node);
        root->data = pre[0];
        int i;
        for(i = 0; i < len; i++)
        {
            if(mid[i] == pre[0])
            {
                break;
            }
        }
        root->l = buildtree(i, pre + 1, mid);
        root->r = buildtree(len - i - 1, pre + i + 1, mid + i + 1);
        return root;
    }
    void postorder(node *T)
    {
        if(T != NULL)
        {
            postorder(T->l);
            postorder(T->r);
            printf("%c", T->data);
        }
    }
    void cengci(node *T)
    {
        queue<node *>t;
        t.push(T);//先将树的根节点入队
        while(!t.empty())//如果队列不空,则进入循环
        {
            T = t.front();//将队首元素出队
            t.pop();
            if(T)//保证进来的所有都有不为空
            {
                cout<<T->data;//输出队首元素;
                t.push(T->l);
                t.push(T->r);
            }
        }
    }
    int main()
    {
        int t;
        char pre[100], mid[100];
        while(~scanf("%d", &t))
        {
            while(t--)
            {
                node *root;
                scanf("%s", pre);
                scanf("%s", mid);
                int len = strlen(pre);
                root = buildtree(len, pre, mid);
                postorder(root);
                printf("\n");
                cengci(root);
                printf("\n");
            }
        }
        return 0;
    }
    
    
    
    展开全文
  • - PAGE PAGE 2 欢迎下载 数据结构实验报告 实验题目: 创建并遍历二叉树 实验目的熟悉二叉树存储结构熟悉二叉树的三种遍历方法并能用非递归的方法建立并且遍历二叉树 实验内容用先序和中序建立二叉树后序遍历并输出...
  • golang二叉树后序遍历

    2020-09-07 14:49:20
    题面 给定一个二叉树,返回它的 后序 ...已知前序遍历和中序遍历,就能确定后序遍历 递归遍历 后序遍历左子树 后序遍历右子树 访问根结点 二叉树为空则结束返回 type TreeNode struct { Val int Left *TreeNode
  • 数据结构实验之求二叉树后序遍历和层次遍历 Description 已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历和层序遍历。 Input 输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括...
  • 二叉树后序遍历 python

    2019-08-31 23:08:09
    题目描述 给定一个二叉树的前序遍历和中序遍历的序列,输出对应这个二叉树的后续遍历序列。 输入描述: 输入为一行。 两个字符串,分别表示...采取的是先重建二叉树,然后后序遍历的方法 # -*- coding:utf-8 -*...
  • 二叉树后序遍历的两种易写的非递归写法二叉树的后序遍历较它的前序中序遍历会复杂一点,原因在于非递归写法与前序中序的思路并不是完全一致,导致很多时候都容易忘记。所以今天我就来总结一下,二叉树后序遍历的两种...
  • 数据结构实验之求二叉树后序遍历和层次遍历 Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^ 题目描述  已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历。 输入  输入数据有多组,第一...
  • 二叉树后序遍历非递归实现是三种遍历实现里面最复杂的一种了。后序遍历的顺序是左节点-右节点-根节点,因为二叉树每个节点只有指向子节点的指针而没有指向父节点的指针,因此我们需要一个额外的变量来记录是否访问...
  • 数据结构实验之求二叉树后序遍历和层次遍历 Time Limit: 1000MS Memory limit: 65536K 题目描述 已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历。 输入 输入数据有多组,第一行是一个整数t (t<...
  • 二叉树后序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的后序遍历的特性,该二叉树后序遍历顺序为: D G E B H I F C A 2. 一般遍历一颗二叉树,先序中序或者后序...
  • 2.后序遍历 3.中序遍历 4.层序遍历 口诀: 后序:左右根 后序遍历:若树为空,则空操作返回,否则从左到右先叶子后结点的方式访问遍历左右子树,最后访问根节点。 后序遍历结果:H I D J E B K F G C A 后序遍历:8...
  • 数据结构实验之求二叉树后序遍历和层次遍历 Time Limit: 1000MS Memory Limit: 65536KB Problem Description  已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历和层序遍历。 Input  输入...
  • 数据结构实验之求二叉树后序遍历和层次遍历 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description  已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历和层序遍历。 ...
  • LeetCode 145 二叉树后序遍历 递归非递归 通俗易懂的万能模板方法1.递归 二叉树后序遍历2.非递归 二叉树后序遍历 万能模板法 二叉树的遍历方式作为面试热门考点,相信递归的方式大家都很容易能够写出来,但只掌握...
  • python 二叉树后序遍历 非递归

    千次阅读 2018-08-18 21:19:28
    今天拼多多面试,面试官让我写非递归的二叉树后序遍历,听到这个题目我就感觉不妙,根本不记得了啊,唯一记得的是后序是最难的,还有,需要用栈。 没办法,只能先硬着头皮试试,一开始大脑跟纸一样空白,后来突然...
  • 数据结构实验之求二叉树后序遍历和层次遍历 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Discuss Problem Description  已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历和层序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,596
精华内容 10,238
关键字:

二叉树后序遍历