二叉链表存储的二叉树算法的结构构造

二叉链表存储的二叉树算法的结构构造通常包括以下两个部分：

1. 二叉树节点结构体

二叉树节点结构体通常包含三个成员变量，分别是左子节点指针、右子节点指针和节点值。结构体定义可以如下：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

2. 创建二叉树函数

创建二叉树函数通常使用递归实现，函数定义可以如下：

TreeNode* createBinaryTree() {
    int val;
    cin >> val;
    if (val == -1) { // -1 表示该节点为空
        return nullptr;
    }
    TreeNode* node = new TreeNode();
    node->val = val;
    node->left = createBinaryTree();
    node->right = createBinaryTree();
    return node;
}

在这个函数中，先输入当前节点的值，如果该值为 -1 则表示当前节点为空，直接返回空指针。否则，创建一个新的节点，设置节点的值为输入的值，然后递归创建左子树和右子树，并将左右子节点指针设置为递归返回的值。

这样，我们就可以使用上述结构体和函数定义来构造一个二叉链表存储的二叉树，并对其进行遍历、修改等操作。

相关问题

分别编写一个递归和非递归算法，求出二叉链表存储二叉树的叶子结点个数。满足要求的c代码如下：

### 回答1：
递归算法：

int countLeafNodes(BiTree T) {
    if (T == NULL) {
        return ;
    } else if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    } else {
        return countLeafNodes(T->lchild) + countLeafNodes(T->rchild);
    }
}

非递归算法：

int countLeafNodes(BiTree T) {
    int count = ;
    if (T == NULL) {
        return ;
    }
    Stack s;
    InitStack(&s);
    Push(&s, T);
    while (!IsEmpty(s)) {
        BiTree p;
        Pop(&s, &p);
        if (p->lchild == NULL && p->rchild == NULL) {
            count++;
        }
        if (p->rchild != NULL) {
            Push(&s, p->rchild);
        }
        if (p->lchild != NULL) {
            Push(&s, p->lchild);
        }
    }
    return count;
}

### 回答2：
非递归算法：

// 定义二叉链表结构
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 求二叉链表存储二叉树的叶子结点个数的非递归算法
int countLeaves(Node* root) {
    if (root == NULL) {
        return 0;
    }
    
    int count = 0;
    Node* stack[100];  // 使用栈来实现非递归
    int top = -1;
    Node* curr = root;
    while (curr != NULL || top != -1) {
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }
        
        curr = stack[top--];
        if (curr->left == NULL && curr->right == NULL) {
            count++;
        }
        
        curr = curr->right;
    }
    
    return count;
}

递归算法：

// 定义二叉链表结构
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 求二叉链表存储二叉树的叶子结点个数的递归算法
int countLeaves(Node* root) {
    if (root == NULL) {
        return 0;
    }
    
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    
    return countLeaves(root->left) + countLeaves(root->right);
}

上述两个函数都接受一个二叉链表表示的二叉树的根节点作为参数，计算叶子结点的数量并返回。非递归算法使用栈来模拟递归的过程，逐个遍历树的节点，如果节点没有左子节点和右子节点，则计数器加1。递归算法则是递归地遍历左子树和右子树，并将返回的叶子节点数量相加。

### 回答3：
递归算法如下：

#include <stdio.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int countLeafNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

int main() {
    // 构造一个二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;
    
    int count = countLeafNodes(root);
    printf("叶子结点个数：%d\n", count);
    
    return 0;
}

非递归算法如下：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int countLeafNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    struct TreeNode* stack[100];  // 定义一个栈来存储遍历的结点
    int top = -1;  // 栈顶指针初始化为-1
    int count = 0;  // 叶子结点个数初始化为0
    
    stack[++top] = root;  // 根结点入栈
    
    while (top > -1) {
        struct TreeNode* node = stack[top--];  // 取出栈顶结点
        
        if (node->left == NULL && node->right == NULL) {
            count++;  // 如果当前结点没有左右子结点，则为叶子结点，个数加一
        }
        
        if (node->right) {
            stack[++top] = node->right;  // 右子结点入栈
        }
        
        if (node->left) {
            stack[++top] = node->left;  // 左子结点入栈
        }
    }
    
    return count;
}

int main() {
    // 构造一个二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;
    
    int count = countLeafNodes(root);
    printf("叶子结点个数：%d\n", count);
    
    return 0;
}

用数据结构c语言编程，构造二叉链表存储二叉树T，三种方式递归遍历T，递归计算T的深度，递归统计T中结点的个数，递归统计T中叶子结点的个数的具体算法

非常感谢您的提问！这是一个关于数据结构和算法的问题。我很乐意帮助您回答这个问题。

首先，让我们来了解一下二叉树和二叉链表的概念。

二叉树是一种树形结构，它的每个节点最多有两个子节点。

二叉链表是一种利用链式存储结构表示二叉树的方法，它的每个节点包括三个字段，分别是数据域、指向左子树的指针和指向右子树的指针。

构造二叉链表存储二叉树T的算法如下：

typedef struct TreeNode *BiTree;

struct TreeNode {
    int val;
    BiTree left;
    BiTree right;
};

BiTree createTree(void) {
    int val;
    scanf("%d", &val);
    if (val == 0) {
        return NULL; // 0 表示空节点
    }
    BiTree T = (BiTree) malloc(sizeof(struct TreeNode));
    T->val = val;
    T->left = createTree();
    T->right = createTree();
    return T;
}

其中，`createTree()` 函数会从标准输入中逐层递归读入每个节点的值，直至遇到0，表示递归结束。此时，该节点的值为空，并且其指针域均为空。

接下来，让我们来看看如何递归遍历T、计算T的深度、统计T中结点的个数以及统计T中叶子结点的个数。

先来看中序遍历、前序遍历和后序遍历的算法：

// 中序遍历
void inorder(BiTree T) {
    if (!T) {
        return;
    }
    inorder(T->left);
    printf("%d ", T->val);
    inorder(T->right);
}

// 前序遍历
void preorder(BiTree T) {
    if (!T) {
        return;
    }
    printf("%d ", T->val);
    preorder(T->left);
    preorder(T->right);
}

// 后序遍历
void postorder(BiTree T) {
    if (!T) {
        return;
    }
    postorder(T->left);
    postorder(T->right);
    printf("%d ", T->val);
}

以上三个函数分别实现了中序遍历、前序遍历和后序遍历的递归算法。其中，`T` 表示当前子树的根节点。

计算T的深度的算法如下：

int depth(BiTree T) {
    if (!T) {
        return 0;
    }
    int left_depth = depth(T->left);
    int right_depth = depth(T->right);
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

统计T中结点的个数的算法如下：

int countNodes(BiTree T) {
    if (!T) {
        return 0;
    }
    return countNodes(T->left) + countNodes(T->right) + 1;
}

统计T中叶子结点的个数的算法如下：

int countLeaves(BiTree T) {
    if (!T) {
        return 0;
    }
    if (!T->left && !T->right) {
        return 1;
    }
    return countLeaves(T->left) + countLeaves(T->right);
}

以上四个函数分别实现了递归遍历T、计算T的深度、统计T中结点的个数以及统计T中叶子结点的个数的算法。

希望以上回答对您有帮助。如果您有其他问题，欢迎继续提问。