用C++求二叉树中序遍历的结果并打印,打印二叉树中序遍历的最后一个结点,打印二叉树中序遍历的第n个结点。
时间: 2024-05-12 20:11:58 浏览: 98
c++二叉树中序遍历
用C++求二叉树中序遍历的结果并打印可以使用递归方法实现,具体步骤如下:
1. 如果当前结点为空,返回。
2. 递归遍历左子树。
3. 输出当前结点。
4. 递归遍历右子树。
中序遍历的最后一个结点即为二叉树的最右下角结点,可以在递归遍历时记录最后一个结点。
中序遍历的第n个结点可以在递归遍历时使用一个计数器来记录当前是第几个结点,并在遍历到第n个结点时输出。
以下是示例代码:
```c++
#include <iostream>
using namespace std;
// 二叉树结点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
TreeNode* getInorderLastNode(TreeNode* root) {
if (root == NULL) {
return NULL;
}
while (root->right != NULL) {
root = root->right;
}
return root;
}
int getInorderNthNode(TreeNode* root, int n, int& count) {
if (root == NULL) {
return -1;
}
int res = getInorderNthNode(root->left, n, count);
if (count == n) {
return root->val;
}
count++;
if (res != -1) {
return res;
}
return getInorderNthNode(root->right, n, count);
}
int main() {
// 构建一个二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 中序遍历
inorderTraversal(root);
cout << endl;
// 中序遍历的最后一个结点
TreeNode* lastNode = getInorderLastNode(root);
cout << lastNode->val << endl;
// 中序遍历的第n个结点
int n = 3;
int count = 1;
int nthNode = getInorderNthNode(root, n, count);
cout << nthNode << endl;
return 0;
}
```
阅读全文