c语言双序遍历二叉树T的递归算法
时间: 2023-09-12 19:10:22 浏览: 66
以下是C语言中双序遍历二叉树T的递归算法:
```c
void DLR(BiTree T) {
if (T != NULL) {
printf("%c", T->data); //访问根节点
DLR(T->lchild); //递归遍历左子树
DLR(T->rchild); //递归遍历右子树
}
}
```
其中,DLR表示先访问根节点(D),再遍历左子树(L),最后遍历右子树(R)。递归终止条件是遍历到NULL节点。
相关问题
C语言: 后序遍历二叉树的非递归算法
后序遍历二叉树的非递归算法可以使用栈来实现,具体实现步骤如下:
1. 定义一个栈,将根节点压入栈中。
2. 定义一个指针p,指向根节点。
3. 定义一个变量lastvisit,用于记录上一次访问的节点。
4. 当栈不为空时,执行以下操作:
1. 将栈顶节点p弹出,如果p的左右子树都为空或者上一次访问的节点是p的左右子树中的一个,则访问p节点并将lastvisit设为p。
2. 如果p的左右子树不为空且上一次访问的节点不是p的左右子树中的一个,则分别将p的右子树和左子树压入栈中。
5. 当栈为空时,遍历结束。
下面是一个示例代码实现:
```c
void postOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
Stack stack = createStack();
TreeNode *p = root;
TreeNode *lastvisit = NULL;
while (!isEmpty(stack) || p != NULL) {
if (p != NULL) {
push(stack, p);
p = p->left;
} else {
TreeNode *top = getTop(stack);
if (top->right != NULL && lastvisit != top->right) {
p = top->right;
} else {
visit(top);
lastvisit = top;
pop(stack);
}
}
}
}
```
其中,TreeNode表示树的节点,Stack表示栈,createStack()表示创建一个栈,isEmpty(stack)表示判断栈是否为空,push(stack, p)表示将节点p压入栈中,getTop(stack)表示获取栈顶元素,visit(top)表示访问节点top,lastvisit记录上一次访问的节点,pop(stack)表示弹出栈顶元素。
c语言里中序遍历二叉树的非递归算法讲解
好的,下面是中序遍历二叉树的非递归算法讲解:
中序遍历二叉树的非递归算法需要用到栈结构,它的基本思路如下:
1. 从根节点开始,将节点依次入栈,直到左子树为空的节点为止;
2. 弹出栈顶元素并访问,如果它有右子树,则将右子树根节点入栈,并重复步骤1;
3. 直到栈为空,算法结束。
以下是C代码实现:
```
void inorderTraversal(struct TreeNode* root){
if(root == NULL) return;
struct TreeNode* stack[1000]; //用于存放节点的栈
int top = 0; //栈顶指针
struct TreeNode* p = root;
while(top > 0 || p != NULL){
if(p != NULL){ //将当前节点及其所有左子树入栈
stack[++top] = p;
p = p->left;
}else{ //左子树为空,弹出栈顶元素并访问
p = stack[top--];
printf("%d ", p->val);
p = p->right; //若有右子树,继续遍历
}
}
}
```
我们可以调用该函数进行二叉树的中序遍历:
```
int main(){
struct TreeNode a = {1, NULL, NULL};
struct TreeNode b = {2, NULL, NULL};
struct TreeNode c = {3, &a, &b};
struct TreeNode d = {4, NULL, NULL};
struct TreeNode e = {5, &d, &c};
inorderTraversal(&e);
return 0;
}
```
输出结果为:
```
4 5 1 3 2
```
希望这个讲解能够帮到你,如有其他问题,欢迎随时向我提问。