精华内容
下载资源
问答
  • (数据结构)二叉树中序遍历
    千次阅读
    2022-03-30 13:18:06

    二叉树中序遍历

    二叉树中序遍历的实现思想是:

    1. 访问当前节点的左子树
    2. 访问根节点
    3. 访问当前节点的右子树

    图 1 二叉树

    以上图 1 为例,中序遍历的过程如下:

    1. 访问该二叉树的根节点,找到 1
    2. 遍历节点 1 的左子树,找到节点 2
    3. 遍历节点 2 的左子树,找到节点 4
    4. 由于节点 4 无左孩子,因此找到节点 4,并遍历节点 4 的右子树
    5. 由于节点 4 无右子树,因此节点 2 的左子树遍历完成,访问节点 2
    6. 遍历节点 2 的右子树,找到节点 5
    7. 由于节点 5 无左子树,因此访问节点 5 ,又因为节点 5 没有右子树,因此节点 1 的左子树遍历完成,访问节点 1 ,并遍历节点 1 的右子树,找到节点 3
    8. 遍历节点 3 的左子树,找到节点 6
    9. 由于节点 6 无左子树,因此访问节点 6,又因为该节点无右子树,因此节点 3 的左子树遍历完成,开始访问节点 3 ,并遍历节点 3 的右子树,找到节点 7
    10. 由于节点 7 无左子树,因此访问节点 7,又因为该节点无右子树,因此节点 1 的右子树遍历完成,即整棵树遍历完成

    因此,图 1 中二叉树采用中序遍历得到的序列为:4 2 5 1 6 3 7 

    二叉树中序遍历代码实现

    先谈一下递归实现!!!

    #include <stdio.h>
    #include <stdlib.h>
     
    typedef struct MyBiTNode{
        int data;  // 数据域
        struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
    } BiTNode;
    
    BiTNode *CreateBiTree(BiTNode *T){
    	// 结点 1 
        T = (BiTNode*)malloc(sizeof(BiTNode));
        T->data = 1;
        // 结点 2
    	T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->data = 2;
    	// 结点 3
    	T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->data = 3;
    	// 结点 4 
    	T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->lchild->data = 4;
    	T->lchild->lchild->lchild = NULL;
    	T->lchild->lchild->rchild = NULL;
    	// 结点 5
    	T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->rchild->data = 5;
    	T->lchild->rchild->lchild = NULL;
    	T->lchild->rchild->rchild = NULL;
    	// 结点 6
    	T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->lchild->data = 6;
    	T->rchild->lchild->lchild = NULL;
    	T->rchild->lchild->rchild = NULL;
    	// 结点 7
    	T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->rchild->data = 7; 
    	T->rchild->rchild->lchild = NULL;
    	T->rchild->rchild->rchild = NULL;
    	return T;
    }
     
    // 模拟操作结点元素的函数,输出结点本身的数值
    void displayElem(BiTNode* elem){
        printf("%d ", elem->data);
    }
    
    // 中序遍历
    void INOrderTraverse(BiTNode *T){
        if(T){
            INOrderTraverse(T->lchild);  // 遍历左孩子
            displayElem(T);  // 调用操作结点数据的函数方法
            INOrderTraverse(T->rchild);  // 遍历右孩子
        }
        // 如果结点为空,返回上一层
        return;
    } 
    
    int main() {
        BiTNode *Tree = NULL;  // 结构体指针指向空 
        Tree = CreateBiTree(Tree);  // 传入结构体指针 
        printf("%d\n",Tree->rchild->lchild->data);  // 4 
        
        INOrderTraverse(Tree);
        return 0;
    }

    再谈一下非递归实现!!!

    #include <stdio.h>
    #include <stdlib.h>
    
    int top = -1;  // top变量表示栈顶元素所在位置
     
    typedef struct MyBiTNode{
        int data;  // 数据域
        struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
    } BiTNode;
    
    BiTNode *CreateBiTree(BiTNode *T){
    	// 结点 1 
        T = (BiTNode*)malloc(sizeof(BiTNode));
        T->data = 1;
        // 结点 2
    	T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->data = 2;
    	// 结点 3
    	T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->data = 3;
    	// 结点 4 
    	T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->lchild->data = 4;
    	T->lchild->lchild->lchild = NULL;
    	T->lchild->lchild->rchild = NULL;
    	// 结点 5
    	T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->rchild->data = 5;
    	T->lchild->rchild->lchild = NULL;
    	T->lchild->rchild->rchild = NULL;
    	// 结点 6
    	T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->lchild->data = 6;
    	T->rchild->lchild->lchild = NULL;
    	T->rchild->lchild->rchild = NULL;
    	// 结点 7
    	T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->rchild->data = 7; 
    	T->rchild->rchild->lchild = NULL;
    	T->rchild->rchild->rchild = NULL;
    	return T;
    }
     
    // 模拟操作结点元素的函数,输出结点本身的数值
    void displayElem(BiTNode* elem){
        printf("%d ", elem->data);
    }
    
    // 先序和中序遍历使用的进栈函数
    void push(BiTNode **a, BiTNode *elem){
        a[++top] = elem;
    }
    
    // 弹栈函数
    void pop(){
        if(top == -1){
            return;
        }
        top--;
    }
    
    // 拿到栈顶元素
    BiTNode *getTop(BiTNode **a){
        return a[top];
    }
    
    // 中序遍历非递归算法
    void InOrderTraverse_1(BiTNode *Tree){
        BiTNode *a[20]; 
        BiTNode *p; 
        push(a, Tree);  
        while(top != -1){  
            while((p = getTop(a)) && p){ 
                push(a, p->lchild);
            }
            pop();
            if(top != -1){
                p = getTop(a);
                pop();
                displayElem(p);
                push(a, p->rchild);
            }
        }
    }
    
    // 中序遍历实现的另一种方法
    void InOrderTraverse_2(BiTNode *Tree){
        BiTNode *a[20];
        BiTNode *p;
        p = Tree;
        while(p || top!=-1){
            if(p){
                push(a, p);
                p = p->lchild;
            }else{  // 如果 p为 NULL,表明左子树遍历完成,需要遍历上一层结点的右子树 
                p = getTop(a);
                pop();
                displayElem(p);
                p = p->rchild;
            }
        }
    }
    
    int main() {
        BiTNode *Tree = NULL;  // 结构体指针指向空 
        Tree = CreateBiTree(Tree);  // 传入结构体指针 
        printf("%d\n",Tree->rchild->lchild->data);  // 4 
        
        InOrderTraverse_2(Tree);
        InOrderTraverse_2(Tree);
        return 0;
    }

    更多相关内容
  • 本文实例讲述了C++基于先序、中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含...
  • 本文实例讲述了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作。分享给大家供大家参考,具体如下: 实现一个功能:  输入:一颗二叉树的先序和中序遍历  输出:后续遍历 思想: 先序遍历中,第一个元素...
  • 二叉树的中序遍历 题目描述: 解题思路: 第一种:递归。又是递归,可以发现很多题都可以用到递归的思路…。二叉树的中序遍历,这里不太了解的可以看看这个博客:二叉树遍历,总结了二叉树的所有遍历情况。这道题所...
  • 主要介绍了Python二叉树的遍历操作,结合实例形式分析了Python针对二叉树的前序遍历,中序遍历,后序遍历,层序遍历等相关操作实现技巧,需要的朋友可以参考下
  • 下面小编就为大家带来一篇通过先序遍历和中序遍历后的序列还原二叉树(实现方法)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 主要介绍了Python利用前序和中序遍历结果重建二叉树的方法,实例分析了Python二叉树的定义与遍历操作技巧,需要的朋友可以参考下
  • NULL 博文链接:https://128kj.iteye.com/blog/1692248
  • 数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
  • 数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
  • js代码-二叉树中序遍历
  • 主要实现了二叉树中序遍历+左右子树交换+叶子结点数目
  • js代码-11.3 中序遍历(迭代)
  • 已知中序遍历和后序遍历,求前序遍历。有比较详尽的中文注释。
  • 课程设计报告数据结构二叉树遍历演示
  • Java二叉树中序遍历

    2015-05-18 19:34:17
    一个简单的课程设计,使用Java来实现二叉树的中序遍历
  • 中序遍历二叉排序树

    2018-06-30 21:06:55
    中序遍历二叉排序树 输入一整数序列,建立二叉排序树,然后中序遍历。 输入说明 输入第一行为整数的个数n,第二行是具体的n个整数。 输出说明 建立二叉排序树,然后输出中序遍历的结果。 输入样例 5 1 6 5 9 8 ...
  • 在这里我们对于二叉树的基本概念不做详细介绍,我们这里主要介绍二叉树的前序遍历,中序遍历,和后序遍历三种问题和如何通过他的前序遍历,中序遍历,后序遍历构造相应的二叉搜索树的问题。 在这之前,我们先简单...

    二叉树作为数据结构中一种简单而且重要的数据结构,他的存储结构和算法都相对比较简单,因此他也显得特别重要,因为很多问题都可以抽象为二叉树的问题。

    在这里我们对于二叉树的基本概念不做详细介绍,我们这里主要介绍二叉树的前序遍历,中序遍历,和后序遍历三种问题和如何通过他的前序遍历,中序遍历,后序遍历构造相应的二叉搜索树的问题。

    在这之前,我们先简单了解一下二叉树的三种遍历到底是什么样子的。

    我的记忆方式为:

                                           前序遍历-DLR(根节点,左子树,右子树)

                                           中序遍历-LDR(左子树,根节点,右子树)

                                           后序遍历-LRD(左子树,右子树,根节点)

    下面我们举例子:

                                                  

    前序遍历的结果:num1 = [1 , 2 , 4 , 5 , 3 , 6 , 7]

    中序遍历的结果:num2 = [4 , 2 , 5 , 1 , 6 , 3 , 7]

    后序遍历的结果:num3 = [4 , 5 , 2 , 6 , 7 , 3 , 1]

    这是三种遍历的结果,在这个结果中,我们发现,对于前序遍历的结果来说,二叉树的根节点为前序遍历数组的第一个值,即num1[0],后序遍历的最后一个值,即为num3[-1]。这是个很重要的信息,这对于我们根据一个二叉树他的前序遍历,中序遍历,后序遍历构造构造二叉搜索树具有非常大的帮助。

    因为如果我们要构造二叉搜索树,首先是要确定根节点的位置,在确定根节点的位置之后,我们再确定左右子树的大小和长度。干说显得比较枯燥,下面我们举例论证一下。

    1008. 前序遍历构造二叉搜索树

    难度中等205收藏分享切换为英文接收动态反馈

    给定一个整数数组,它表示BST(即 二叉搜索树 )的 序遍历 ,构造树并返回其根。

    保证 对于给定的测试用例,总是有可能找到具有给定需求的二叉搜索树。

    二叉搜索树 是一棵二叉树,其中每个节点, Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val

    二叉树的 前序遍历 首先显示节点的值,然后遍历Node.left,最后遍历Node.right

    示例 1:

    输入:preorder = [8,5,1,7,10,12]
    输出:[8,5,10,1,7,null,12]
    

    示例 2:

    输入: preorder = [1,3]
    输出: [1,null,3]
    

    提示:

    • 1 <= preorder.length <= 100
    • 1 <= preorder[i] <= 10^8
    • preorder 中的值 互不相同

    题目思路:

    我们可以得到,前序遍历结果的首字母为数的根,因此我们首先root_val = preorder[0]得到二叉搜索树的根,且由题意可知二叉树右子树的值大于左子树,因此我们遍历前序遍历的数组可以得到左子树的内容和右子树的内容,之后分别打入递归即可。

    Python代码: 

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
            if not preorder: #当为空的时候,我们输出none
                return None
            root_val = preorder[0]  #前序遍历结果的首位为二叉树的前节点
            root = TreeNode(root_val)
       
            preorder_left = [] #构造两个数组,分别用于存放左子树和右子树的结果
            preorder_right = []
    
    
            for i in range(1 , len(preorder)):
               if  preorder[i] < root_val:       #如果找到小于root_val, 则为左子树的内容,存入左子树
                    preorder_left.append(preorder[i])
               else:                             #如果找到大于root_val,则为右子树的内容,存入右子树
                    preorder_right.append(preorder[i])
    
            root.left = self.bstFromPreorder(preorder_left)   #开始递归,左子树的往树的左边递归
            root.right = self.bstFromPreorder(preorder_right)  #右子树,往树的右边递归
    
            return root
    
    

     

    889. 根据前序和后序遍历构造二叉树

    难度中等233收藏分享切换为英文接收动态反馈

    给定两个整数数组,preorder 和 postorder ,其中 preorder 是一个具有 无重复 值的二叉树的前序遍历,postorder 是同一棵树的后序遍历,重构并返回二叉树。

    如果存在多个答案,您可以返回其中 任何 一个。

    示例 1:

    输入:preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
    输出:[1,2,3,4,5,6,7]
    

    示例 2:

    输入: preorder = [1], postorder = [1]
    输出: [1]
    

    提示:

    • 1 <= preorder.length <= 30
    • 1 <= preorder[i] <= preorder.length
    • preorder 中所有值都 不同
    • postorder.length == preorder.length
    • 1 <= postorder[i] <= postorder.length
    • postorder 中所有值都 不同
    • 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

    题目思路:

    前序遍历的首位即为根节点,后续遍历的末尾为根节点,
    前序遍历的结果为(根节点,左子树,右子树)
    后续遍历的结果为(左子树,右子树,根节点)
    依照这个思想,我们进行求解,首先root = TreeNode(preorder[0]) 确定根节点的位置,然后在后续
    在后续遍历中 a_left = postorder.index(preorder[1])找到
    左子树根节点的位置,可以得到左子树的范围postorder_left = postorder[:a_left+1] ,因为左子树的长度是固定的
    可以同理得到前序遍历中左子树的范围preorder_left = preorder[1:a_left+2]
    同理,右子树的范围也可以得到,递归得到全部的root。

    Python代码: 

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
            if not preorder or not postorder:
                return None
            root = TreeNode(preorder[0])     #前序遍历的首位即为二叉树的根
            if len(preorder) == 1:   #如果为1,即为根输出即可
                return root
            a_left = postorder.index(preorder[1]) #在后序遍历中找到左子树的根节点 
    
            preorder_left = preorder[1:a_left+2] # 那么左子树的范围为,
            preorder_right = preorder[a_left+2:]  #右子树的范围
    
            postorder_left = postorder[:a_left+1] #左子树的范围
            postorder_right = postorder[a_left+1:len(postorder)-1] #右子树的范围
    
            root.left = self.constructFromPrePost(preorder_left , postorder_left)  #分别进行递归
            root.right = self.constructFromPrePost(preorder_right , postorder_right)
    
            return root
    
    

    105. 从前序与中序遍历序列构造二叉树

    难度中等1516收藏分享切换为英文接收动态反馈

    给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

    示例 1:

    输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    输出: [3,9,20,null,null,15,7]
    

    示例 2:

    输入: preorder = [-1], inorder = [-1]
    输出: [-1]

    题目思路: 

    前序遍历【根节点,左子树,右子树】
    中序遍历【左子树,根节点,右子树】参考这个求解即可
    在前序遍历中root_val = preorder[0] 确定根节点的位置,在中序遍历中找到根节点的位置,中序遍历中根节点左边的即为左子树的范围
    右边的即为右子树的范围,因为左子树右子树的长度是固定的,因此我们可以在中序遍历中也确定左右子树的范围
    打入递归即可

    Python代码:

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
            if not preorder or not inorder:
                return None
            root_val = preorder[0]  #前序遍历的首节点为根节点
            root = TreeNode(root_val)
    
            mid = inorder.index(root_val) #在中序遍历中找到根节点的位置
     
            inorder_left = inorder[:mid]  #中序遍历中根节点左边的即为左子树的范围
            inorder_right = inorder[mid+1:] #右边的即为右子树的范围
    
            preorder_left = preorder[1:len(inorder_left)+1]#因为左子树右子树的长度是固定的,因此我们可以在中序遍历中也确定左右子树的范围
            preorder_right = preorder[len(inorder_left)+1:]
            
            root.left = self.buildTree(preorder_left , inorder_left)#打入递归即可
            root.right = self.buildTree(preorder_right , inorder_right)
            
            return root
    
    

    106. 从中序与后序遍历序列构造二叉树

    难度中等709收藏分享切换为英文接收动态反馈

    给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

    示例 1:

    输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    输出:[3,9,20,null,null,15,7]
    

    示例 2:

    输入:inorder = [-1], postorder = [-1]
    输出:[-1]

    解题思路: 

    中序遍历为【左子树,根节点,右子树】
    后序遍历为【左子树,右子树,根节点】
    后序遍历的最有一个值为根节点,在中序遍历中找到根节点的位置,中序遍历中根节点左边的为左子树的长度,右边的为右子树的长度
    ,左右子树的长度一定,因此我们也可以在后序遍历中确定左右子树,打入递

    Python代码:

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
            if not inorder or not postorder: 
                return None
            
    
            val = postorder[-1]  # 后序遍历的最有一个值为根节点
            root = TreeNode(val) # 
    
            mid = inorder.index(val)  #在中序遍历中找到根节点的位置
    
            inorder_left = inorder[:mid] #中序遍历中根节点左边的为左子树的长度,右边的为右子树的长度
            inorder_right = inorder[mid+1:]
            
            postorder_left = postorder[:len(inorder_left)]  #左右子树的长度一定,因此我们也可以在后序遍历中确定左右子树
            postorder_right = postorder[len(inorder_left):len(postorder)-1]
    
            root.left = self.buildTree(inorder_left , postorder_left)#打入递归
            root.right = self.buildTree(inorder_right , postorder_right)
    
    
            
            return root
    
    

    449. 序列化和反序列化二叉搜索树

    难度中等280收藏分享切换为英文接收动态反馈

    序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。

    设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。

    编码的字符串应尽可能紧凑。

    示例 1:

    输入:root = [2,1,3]
    输出:[2,1,3]
    

    示例 2:

    输入:root = []
    输出:[]
    

    提示:

    • 树中节点数范围是 [0, 104]
    • 0 <= Node.val <= 104
    • 题目数据 保证 输入的树是一棵二叉搜索树。

    通过次数22,273提交次数38,572

    解题思路:先后序遍历得到数组,使用map函数变成字符串,然后再使用map函数变成列表,进行后序遍历构造二叉搜索树。

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Codec:
    
        def serialize(self, root: TreeNode) -> str:
            """Encodes a tree to a single string.
            """
            ans = []
            def serialize_1(root):#后序遍历,构造数组,进行所谓的序列化
                if not root: return 
                serialize_1(root.left)
                serialize_1(root.right)
                ans.append(root.val)
            serialize_1(root)
            return ' '.join(map(str , ans))#然后使用map函数,变成字符串
    
        def deserialize(self, data: str) -> TreeNode:
            """Decodes your encoded data to tree.
            """
            ads = list(map(int , data.split()))#使用map函数,拆看,变成列表
            def deserialize_1(ads): #后序遍历构造二叉搜索树
                if not ads: return None
                val = ads.pop()
                ads_right = []
                ads_left = []
                root = TreeNode(val)
                for i in range(len(ads)):
                    if ads[i]>val: ads_right.append(ads[i])
                    elif ads[i]<val: ads_left.append(ads[i])
                root.left = deserialize_1(ads_left)
                root.right = deserialize_1(ads_right)
                return root
            return deserialize_1(ads)
                
    
    

    展开全文
  • 非递归中序遍历二叉树
  • 前序遍历+中序遍历重建二叉树

    千次阅读 多人点赞 2021-12-01 16:33:18
    考研数据结构:重建二叉树,本文实现利用前序遍历+中序遍历重建二叉树并给出具体实现的代码,题目来源:剑指 Offer 07. 重建二叉树

    文章目录


    题目

    本题链接:剑指 Offer 07. 重建二叉树

    注:链接题目仅代表和本题大体相似
    因为是考研笔试,本题代码以C语言去写

    AC代码

    代码解释:本题要求就是给定两个序列:分别为树的前序遍历和树的中序遍历,我们知道,在树的各节点值均不同的情况下,给定一个树的💘前序遍历+中序遍历💘 || 💘后序遍历+中序遍历💘 || 💘层序遍历+中序遍历💘,可以唯一确定出一棵树,这里给出数据结构的相关推导过程:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    ⭐️上述笔记仅涉及重构二叉树的内容,如果想获得完整【数据结构】树与二叉树的相关笔记请访问博客:树与二叉树 (还未超链接,约12.20日完成超链接)
    从上述中我们可以看出,其实重建二叉树可以不断的通过递归去实现,递归划分左右子树的点(根节点)就是就在于在中序遍历中找到这个点,这就是我们下述代码中for循环实现的东西:

    int i;
    for (i = 0; i < inorder_size; i ++ ){
    	if (root -> val == inorder[i]) 
    		break;
    }
    

    ⭐️当然这一步我们可以用哈希表去写,这样时间复杂度会降到O(n),C++可直接调用哈希函数:STL—map,当然我们在做笔试题的时候是不允许调用函数的,我们也可以手写哈希函数:哈希表,读者可以根据我写的哈希表这个博客去优化改进下述代码,对于考研笔试而言,写成我写的下述代码就已经足够了,并不要求掌握手写哈希函数

    代码

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
     
    struct TreeNode* buildTree(int* preorder, int preorder_size, int* inorder, int inorder_size) {
        if (preorder == NULL || preorder_size == 0 || inorder == NULL || inorder_size == 0){
            return NULL;
        }
        
        struct TreeNode *root = (struct TreeNode*)malloc(sizeof (struct TreeNode));
        root -> val = preorder[0];
        
        int i;
        for (i = 0; i < inorder_size; i ++ ){
            if (root -> val == inorder[i]) 
                break;
        }
        root -> left = buildTree(&preorder[1], i, &inorder[0], i);
        root -> right = buildTree(&preorder[i + 1], preorder_size - i - 1, &inorder[i + 1], inorder_size - i - 1);
        
        return root;
    }
    

    展开全文
  • 程序运行后直接输入节点以0结束后可输出二叉树的4种遍历,然后再通过输入前序中序遍历确定后序层序遍历。
  • 根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...
  • 根据前序遍历和中序遍历创建二叉树

    千次阅读 多人点赞 2020-08-18 07:20:00
    Contents前言四种遍历树的方法简介简介两种快速获得遍历结果的方法根据前序遍历和后续遍历创建树代码实现四种遍历树的方法的代码前言昨天参加了两场笔试,都考了这个题。第一场是根据pre_...

    欢迎关注我的微信公众号:MatlabGUI QtCPP等学习记录

    Contents

    前言四种遍历树的方法简介简介两种快速获得遍历结果的方法根据前序遍历和后续遍历创建树代码实现四种遍历树的方法的代码

    前言

    昨天参加了两场笔试,都考了这个题。第一场是根据pre_order和in_order把创建二叉树的代码写出来,第二场是根据pre_order和in_order把这个二叉树画出来!

    当时第一场是C++开发的岗位的笔试,我没做出来,虽然代码写了,但是有Bug一直没改出来(主要还是不熟),他们不让在本地IDE中写,所以没法调试。。。所以第一场笔试我凉了。

    第二场是和传感器有关的岗位,虽然这个画出来了,但是其他笔试题有的没学过(没学过那个专业课),有的忘了(比如概率统计)。考的太杂了,感觉也不行。。。

    不说废话了,下面讲讲如何根据pre_order和in_order创建二叉树。

    四种遍历树的方法简介

    简介

    首先这里简单介绍一下二叉树的4种遍历方式:

    • 前序遍历(pre_order)

    • 中序遍历(in_order)

    • 后序遍历(post_order)

    • 层序遍历(level_order)

    至于这些遍历的代码放在文章的最后。

    前序遍历就是先对当前的根节点进行操作,然后到左子节点,再到右子节点!

    中序遍历就是先对当前左子节点进行操作,然后到当前根节点,再到右子节点!

    后序遍历就是先对当前左子节点进行操作,然后到右子节点,再到当前根节点!

    层序遍历就是按照从上到下从左到右的顺序对每个节点进行操作!代码写起来比前三个复杂点,得借助队列,并用迭代的方式来做。

    如下图(之前上课做的笔记):

    两种快速获得遍历结果的方法

    另外,介绍两个 可以快速地 根据树的形状 得出 前序、后序、中序 的遍历结果。

    法一:

    法二:

    根据前序遍历和后续遍历创建树

    给你一个数组,用这个数组的值来创建一个树,结果有多种可能:

    其中n是数组中元素的个数!

    但是,如果我们给了两个数组,分别是前序遍历和后续遍历的结果,那么我们就能创建唯一的一个树!

    Note:要求数组中的元素不重复,是唯一的!

    看过上面对树的那几种遍历方式后,可以发现:

    Note:下面的这个过程有点枯燥,我表述地也不太好,可以看后面的图。

    • 前序遍历的第一个元素就是树的根节点;第二个元素是根节点的左子节点,这个左子节点也是后面的根节点;

    • 根节点把中序遍历的数组一分为二,中序遍历的数组中:根节点的左边是左树,根节点的右边是右树

    • 所以,我们就对前序遍历的数组进行遍历,当前索引记为pre_i,在每次遍历中,到中序遍历的数组中找这个pre_i对应的值,用这个pre_i把中序遍历的结果一分为二。这样往复下去就能还原树了。

    下面我画一下整个流程:

    大概就是这样,不断地对中序遍历的数组一分为二(根据前序遍历的数组的当前元素进行分割);中序遍历的数组的当前元素就是当前的根节点。

    代码实现

    先定义树的节点:

    template <class T>
    struct Node{
        T val;
        Node* left;
        Node* right;
    
        explicit Node(T v) : val(v), left(nullptr), right(nullptr){}
    };
    

    根据前序遍历和中序遍历创建树:

    /**
     * @brief 根据前序遍历和中序遍历创建树
     * @param[in] pre_vec   前序遍历的数组
     * @param[in] in_vec    中序遍历的数组
     * @param[in] left_in   中序遍历当前段的左边界
     * @param[in] right_in  中序遍历当前段的右边界(超尾)
     * @static pre_i        前序遍历的当前的索引
     *
     * @note 在每一层递归中,当前的 中序遍历 数组段 被分为:[left_in, pre_i), pre_i, [pre_i+1, right_in)
     * */
    template <class T>
    Node<T>* CreateTreeR(vector<T>& pre_vec, vector<T>& in_vec, int left_in, int right_in)
    {
        static int pre_i = 0;
    
        if (left_in < right_in)
        {
            /// 从 前序遍历 的数组中 获取 当前 根节点!
            T cur_root_val = pre_vec.at(pre_i);
            auto* cur_root = new Node<T>(cur_root_val);
    
            /// 遍历 中序遍历 的数组,找到当前根节点对应的索引
            int i = left_in;
            while (i < right_in && cur_root_val != in_vec.at(i)) ++i;
    
            /// 下次递归前 pre_i 是需要向后移动一位的
            ++pre_i;
    
            /// 一分为二!(注意,i是当前节点的索引哦!)
            cur_root->left  = CreateTreeR(pre_vec, in_vec, left_in, i);              /// 左树
            cur_root->right = CreateTreeR(pre_vec, in_vec, i+1, right_in);   /// 右树
    
            return cur_root;
        }
    
        /// 当分到只剩最后一个元素时就返回空了
        return nullptr;
    }
    

    测试这段程序

    对创建出来的这个树,用四种遍历方法分别遍历一下子,四种遍历的代码在文末。

     


    上面这个是数字的,我现在拿字符串的试试:

     


    四种遍历树的方法的代码

    1.层序遍历

    /**
     * @brief 树的层序遍历
     * */
     template<class T>
     void LevelOrder(Node<T>* root, vector<T>& vec)
    {
         /// 如果根节点为空就直接返回
         if (!root) return;
    
         /// 定义一个队列放所有可能会成为 "根节点" 的节点(每次循环中都会pop出一个 "根节点" )
         queue< Node<T>* > q;
         q.push(root);
    
         while (!q.empty())
         {
             /// 从队列中拿出最前面的根节点
             Node<T>* cur_root = q.front();  /// 这个变量在while外面声明更好,不用每次都创建一个新变量。
             q.pop();
             /// 保存当前 "根节点" 的值
             vec.push_back(cur_root->val);
    
             /// 如果左子节点非空就把左子节点放入队列
             if (cur_root->left)
                 q.push(cur_root->left);
    
             /// 如果右子节点非空就把右子节点放入队列
             if (cur_root->right)
                 q.push(cur_root->right);
         }
    }
    

    2.前序遍历

    /**
     * @brief 树的前序遍历
     * */
    template<class T>
    void PreOrder(Node<T>* root, vector<T>& vec)
    {
        if (root)
        {
            vec.push_back(root->val);
            PreOrder(root->left, vec);
            PreOrder(root->right, vec);
        }
    }
    

    3.中序遍历

    /**
     * @brief 树的中序遍历
     * */
    template<class T>
    void InOrder(Node<T>* root, vector<T>& vec)
    {
        if (root)
        {
            InOrder(root->left, vec);
            vec.push_back(root->val);
            InOrder(root->right, vec);
        }
    }
    

    4.后序遍历

    /**
     * @brief 树的后序遍历
     * */
    template<class T>
    void PostOrder(Node<T>* root, vector<T>& vec)
    {
        if (root)
        {
            PostOrder(root->left, vec);
            PostOrder(root->right, vec);
            vec.push_back(root->val);
        }
    }
    

     

    展开全文
  • 设二叉树结点值为大写字母,输入二叉树的前序遍历和中序遍历序列,生成此二叉树,输出该二叉树的后序遍历和按层次遍历序列。输入某结点值,在二叉树中查找该结点,若该结点存在,则输出从根到该结点的路径,否则给出...
  • 前几天写了1020 Tree Traversals (25 分)-PAT甲级这个题目,明白了如何由二叉树的后序遍历和中序遍历得到先序遍历和层次遍历。受这道题启发,思考了一下如何由二叉树的先序遍历和中序遍历得到后序遍历和层次遍历。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 150,446
精华内容 60,178
关键字:

中序 遍历