二叉树 中序遍历 结构

二叉树的中序遍历是指按照左子树、根节点、右子树的顺序遍历一棵二叉树。具体的遍历过程如下：
1. 访问该二叉树的根节点。
2. 遍历根节点的左子树，即对根节点的左子树进行中序遍历。
3. 访问根节点。
4. 遍历根节点的右子树，即对根节点的右子树进行中序遍历。

下面是一个示例代码，实现了二叉树的中序遍历：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderTraversal(root: TreeNode) -> List[int]:
    res = []
    if not root:
        return res
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        res.append(root.val)
        root = root.right
    return res

相关问题

数据结构:线索二叉树中序遍历

线索二叉树是对普通二叉树的改进，将原本为空的左孩子指针或右孩子指针改为指向该节点在中序遍历下的前驱或后继节点。这样可以方便地在不需要使用递归或栈的情况下进行遍历。

中序遍历线索二叉树的过程如下：
1. 从根节点开始，沿着左孩子指针一直往左走，直到找到一个左孩子指针为空的节点，输出该节点的值，并转向该节点的后继节点。
2. 如果后继节点是线索指针，即指向该节点在中序遍历下的后继节点，则直接转到该后继节点。
3. 如果后继节点是孩子指针，则重复步骤1。

注意，在线索二叉树中，根节点的左孩子指针和叶子节点的右孩子指针都指向该节点在中序遍历下的前驱或后继节点的线索指针。因此，在遍历时需要注意判断节点是否为叶子节点或根节点。

c++实现以下功能1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树1 4.中序遍历二叉树2 5.后序遍历二叉树 6.层序遍历二叉树 7.求二叉树的深度 8.退出

C++可以通过定义二叉树节点结构体以及相应的函数来实现以上功能：

1. 创建二叉树：可以通过递归或者非递归方式实现，具体实现方式可以根据需求选择。递归方式实现时，可以采用前序遍历的方式，先创建根节点，再分别创建左右子树；非递归方式可以采用层序遍历的方式，从上到下、从左到右依次创建节点。

2. 先序遍历二叉树：先输出当前节点的值，再遍历左子树，最后遍历右子树。

3. 中序遍历二叉树1：先遍历左子树，再输出当前节点的值，最后遍历右子树。

4. 中序遍历二叉树2：采用非递归方式实现时，需要借助栈数据结构。从根节点开始，将左子树节点依次入栈，然后出栈，输出当前节点的值，再将右子树入栈。

5. 后序遍历二叉树：先遍历左子树，再遍历右子树，最后输出当前节点的值。

6. 层序遍历二叉树：从上到下、从左到右依次遍历每一层节点。

7. 求二叉树的深度：可以采用递归方式求解，分别求出左子树和右子树的深度，然后取较大值加1即为二叉树的深度。

8. 退出：程序结束。