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

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

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 则表示当前节点为空，直接返回空指针。否则，创建一个新的节点，设置节点的值为输入的值，然后递归创建左子树和右子树，并将左右子节点指针设置为递归返回的值。

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

相关问题

以二叉链表作为二叉树的存储结构，编写递归算法，统计二叉树度为2的结点个数

二叉链表表示的二叉树中，每个节点除了保存自身的信息外，还包含了两个指向其左右子节点的指针。要计算度为2（即有两个子节点）的节点个数，我们可以使用递归的方式遍历整个二叉树。下面是Python的一种实现方式：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def count_nodes_of_degree_two(root):
    # 基本情况：如果节点为空，返回0
    if root is None:
        return 0
    
    # 对左子树和右子树递归地计数
    left_count = count_nodes_of_degree_two(root.left)
    right_count = count_nodes_of_degree_two(root.right)
    
    # 如果节点有两个子节点，则返回1，否则返回0
    if root.left and root.right:
        return left_count + right_count + 1
    else:
        return left_count + right_count

# 使用示例
root = Node(1)  # 构造任意二叉树
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(count_nodes_of_degree_two(root))  # 输出: 2，因为节点2和4各有2个子节点

这个函数会返回整个二叉树中度为2的节点总数。

C++编写程序：以二叉链表作为二叉树的存储结构，设计以下算法。 (1)统计二叉树的叶结点个数。 (2)判别两棵树是否相等。 (3)交换二叉树每个结点的左孩子和右孩子。（实验要求：采用二叉链表作为存储结构建立二叉树 ；采用递归算法对其进行遍历（先序、中序、后序） 将遍历结果输出）

在C++中，为了实现上述算法，我们需要首先创建一个二叉链表节点类，用于表示二叉树的节点，并包含左右孩子的指针。然后我们可以构建二叉树类，包括相应的功能：

1. 统计叶节点个数:

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    // 构造函数和其他必要的操作...
};

size_t countLeaves(TreeNode* root) {
    if (!root || !root->left && !root->right) return 1; // 根节点是叶子
    else return countLeaves(root->left) + countLeaves(root->right);
}

2. 判别两棵树是否相等:

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q || p->val != q->val) return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

3. 交换节点的左右孩子:

void swapChildren(TreeNode* &node) {
    if (node) {
        std::swap(node->left, node->right);
        swapChildren(node->left);
        swapChildren(node->right);
    }
}

对于递归遍历（先序、中序、后序），你可以这样实现：
- 先序遍历（根-左-右）:

void preOrderTraversal(TreeNode* root, std::string& result) {
    if (root) {
        result += to_string(root->val) + " ";
        preOrderTraversal(root->left, result);
        preOrderTraversal(root->right, result);
    }
}

- 中序遍历（左-根-右）:

void inOrderTraversal(TreeNode* root, std::string& result) {
    if (root) {
        inOrderTraversal(root->left, result);
        result += to_string(root->val) + " ";
        inOrderTraversal(root->right, result);
    }
}

- 后序遍历（左-右-根）:

void postOrderTraversal(TreeNode* root, std::string& result) {
    if (root) {
        postOrderTraversal(root->left, result);
        postOrderTraversal(root->right, result);
        result += to_string(root->val) + " ";
    }
}

实验要求部分可以通过以下方式完成：
1. 创建二叉树实例并输入数据。
2. 调用相应遍历函数并输出结果。
3. 分别计算两棵已构造好的二叉树的叶节点数，比较它们是否相等。