C语言前序遍历二叉树
时间: 2024-01-23 20:13:06 浏览: 24
以下是C语言实现二叉树前序遍历的递归和非递归方法:
1.递归方法:
```c
void PreOrderTraverse(BiTree T) {
if (T) {
printf("%d ", T->data); //访问当前结点
PreOrderTraverse(T->lchild); //遍历当前结点的左子树
PreOrderTraverse(T->rchild); //遍历当前结点的右子树
}
}
```
2.非递归方法:
```c
void PreOrderTraverse(BiTree T) {
if (!T) {
return;
}
BiTree stack[MAXSIZE];
int top = -1;
stack[++top] = T;
while (top != -1) {
BiTree p = stack[top--];
printf("%d ", p->data); //访问当前结点
if (p->rchild) {
stack[++top] = p->rchild; //先将右子树入栈
}
if (p->lchild) {
stack[++top] = p->lchild; //再将左子树入栈
}
}
}
```
相关问题
c语言实现二叉树前序遍历
以下是C语言实现二叉树前序遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 插入节点
TreeNode* insertNode(TreeNode* root, int val) {
if (root == NULL) {
return createNode(val);
}
if (val < root->val) {
root->left = insertNode(root->left, val);
} else {
root->right = insertNode(root->right, val);
}
return root;
}
// 前序遍历
void preOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
int main() {
// 创建二叉树
TreeNode* root = createNode(5);
insertNode(root, 3);
insertNode(root, 7);
insertNode(root, 1);
insertNode(root, 9);
// 前序遍历
printf("前序遍历结果:");
preOrderTraversal(root);
printf("\n");
return 0;
}
```
运行结果:
```
前序遍历结果:5 3 1 7 9
```
c语言线索二叉树及前序遍历
线索二叉树的前序遍历和普通二叉树的前序遍历类似,只是需要利用线索化的指针来判断节点的前驱和后继节点,从而高效地遍历整个线索二叉树。
具体来说,在前序遍历中,我们首先访问根节点,然后递归遍历左子树和右子树。对于每个节点,我们需要先判断它的左孩子指针是否是线索化的指针,如果是,则直接访问它的前驱节点,否则递归遍历它的左子树。然后再判断它的右孩子指针是否是线索化的指针,如果是,则直接访问它的后继节点,否则递归遍历它的右子树。
下面是一个示例代码,实现了线索二叉树的前序遍历:
```
void ThreadedTree_Preorder(ThreadedTreeNode* root) {
if (root == NULL) {
return;
}
ThreadedTreeNode* p = root;
while (p != NULL) {
printf("%d ", p->data);
if (p->left != NULL && p->ltag == 0) {
p = p->left;
} else if (p->right != NULL && p->rtag == 0) {
p = p->right;
} else {
while (p->right != NULL && p->rtag == 1) {
p = p->right;
}
p = p->right; // 跳过线索化的后继指针
}
}
}
```
在上面的代码中,我们利用一个指针p来遍历整个线索二叉树。在每次循环中,我们首先访问当前节点p,并根据它的左线索标志和右线索标志来判断它的左孩子和右孩子指针是否是线索化的指针。如果是,则直接跳转到前驱或后继节点;否则,继续遍历它的左子树或右子树,直到找到一个没有被线索化的孩子节点为止。如果当前节点的右孩子指针是线索化的指针,则需要沿着后继指针跳转到下一个未被访问的节点。
需要注意的是,线索二叉树的前序遍历不同于普通二叉树的前序遍历,因此它的时间复杂度和空间复杂度也可能有所不同。