二叉树的中序遍历顺序怎么定
时间: 2024-01-23 18:13:43 浏览: 24
二叉树的中序遍历顺序是先遍历左子树,然后遍历根节点,最后遍历右子树。具体来说,对于一个二叉树的节点,先遍历它的左子树,然后访问该节点,最后遍历它的右子树。这个过程可以递归地进行,直到遍历完整棵树。
举个例子,对于下面这棵二叉树:
```
1
/ \
2 3
/ \
4 5
```
中序遍历的顺序是:4 -> 2 -> 5 -> 1 -> 3。
具体实现可以参考引用中的递归方法或引用中的非递归方法。
相关问题
二叉树中序遍历打印二叉树简单
在二叉树中,中序遍历是指先遍历该节点的左子树,然后访问该节点,最后遍历该节点的右子树。中序遍历的遍历顺序为 左-根-右。
中序遍历可以用递归或者迭代的方式实现,其中递归方法比较简单。下面是中序遍历的递归实现代码:
```c++
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
```
对于非递归的实现方法,一般使用栈来模拟递归过程。我们将二叉树中的节点压入栈中,然后依次弹出栈顶元素进行遍历,同时将其右子树和左子树压入栈中。
下面是中序遍历的非递归实现代码:
```c++
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* p = root;
while (p != NULL || !s.empty()) {
while (p != NULL) {
s.push(p);
p = p->left;
}
p = s.top();
s.pop();
cout << p->val << " ";
p = p->right;
}
}
```
二叉树的中序遍历顺序实现
二叉树的中序遍历顺序是指先遍历左子树,然后访问根节点,最后遍历右子树。
中序遍历可以使用递归或者迭代的方法实现。以下是递归实现的示例代码:
```python
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 = []
inorder(root, res)
return res
def inorder(root: TreeNode, res: List[int]):
if root:
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
```
以下是迭代实现的示例代码:
```python
def inorderTraversal(root: TreeNode) -> List[int]:
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
```
以上两种实现方式都是时间复杂度为 O(n),其中 n 是二叉树的节点数。递归实现方式需要使用系统栈,因此空间复杂度为 O(n)。迭代实现方式使用了一个辅助栈,因此空间复杂度为 O(h),其中 h 是二叉树的高度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)