c语言求二叉树中序遍历的最后一个节点
时间: 2024-05-10 15:13:40 浏览: 7
对于一个二叉树,中序遍历的最后一个节点就是最右边的节点。因此,我们可以使用递归的方式来查找最右边的节点。具体实现如下:
``` c
struct Node {
int value;
struct Node* left;
struct Node* right;
};
struct Node* get_last_node(struct Node* root) {
if (root == NULL) { // 如果树为空,则最后一个节点为空
return NULL;
}
if (root->right == NULL) { // 如果当前节点没有右子树,说明该节点为最右边的节点
return root;
}
return get_last_node(root->right); // 递归查找右子树
}
```
通过以上代码,我们可以得到二叉树中序遍历的最后一个节点。
相关问题
c语言线索二叉树中序遍历
下面是使用C语言实现线索二叉树中序遍历的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 线索二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
int ltag;
int rtag;
} TreeNode;
// 中序遍历线索二叉树
void inorderTraversal(TreeNode* root) {
TreeNode* p = root;
while (p) {
// 找到最左边的节点
while (p->ltag == 0) {
p = p->left;
}
printf("%d ", p->val);
// 转向后继节点
while (p->rtag == 1 && p->right != NULL) {
p = p->right;
printf("%d ", p->val);
}
p = p->right;
}
}
// 创建线索二叉树节点
TreeNode* createTreeNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
node->ltag = 0;
node->rtag = 0;
return node;
}
// 构建线索二叉树
void createThreadedBinaryTree(TreeNode* root) {
TreeNode* pre = NULL;
if (root != NULL) {
createThreadedBinaryTree(root->left);
if (root->left == NULL) {
root->ltag = 1;
root->left = pre;
}
if (pre != NULL && pre->right == NULL) {
pre->rtag = 1;
pre->right = root;
}
pre = root;
createThreadedBinaryTree(root->right);
}
}
int main() {
// 构建线索二叉树
TreeNode* root = createTreeNode(1);
root->left = createTreeNode(2);
root->right = createTreeNode(3);
root->left->left = createTreeNode(4);
root->left->right = createTreeNode(5);
root->right->left = createTreeNode(6);
root->right->right = createTreeNode(7);
createThreadedBinaryTree(root);
// 中序遍历线索二叉树
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");
return 0;
}
```
其中,`createTreeNode()`函数用于创建一个线索二叉树节点;`createThreadedBinaryTree()`函数用于构建线索二叉树;`inorderTraversal()`函数用于中序遍历线索二叉树。在`inorderTraversal()`函数中,使用双重循环找到最左边的节点,并输出其值,然后转向其后继节点,重复操作直到遍历完整个线索二叉树。
c语言实现二叉树中序遍历非递归
C语言实现二叉树中序遍历非递归同样需要使用栈来实现,具体步骤如下:
1. 新建一个栈和一个指针变量p,初始时p指向根节点,栈为空。
2. 循环执行以下步骤,直到栈为空且p为空:
a. 如果p不为空,则将p入栈,并将p指向其左子节点。
b. 如果p为空,则将栈顶元素出栈并输出,然后将p指向栈顶元素的右子节点。
下面是该算法的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorderTraversal(struct TreeNode* root) {
struct TreeNode* stack[1000];
int top = -1;
struct TreeNode* p = root;
while (top != -1 || p != NULL) {
if (p != NULL) {
stack[++top] = p;
p = p->left;
}
else {
struct TreeNode* node = stack[top--];
printf("%d ", node->val);
p = node->right;
}
}
}
```
其中,struct TreeNode定义了二叉树节点的结构体,val是节点的值,left和right分别是左右子节点的指针。该算法的时间复杂度为O(n),空间复杂度为O(h),其中h为二叉树的高度。