C++以二叉链表作为二叉树的存储结构，编写以下算法： 1.统计二叉树的叶结点个数。 2.判别两棵树是否相等。 3.交换二叉树每个结点的左孩子和右孩子。 4.设计二叉树的双序遍历算法。全部代码 及数据分析算法分析

1. 统计二叉树叶结点个数

#include<iostream>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

int countLeaves(TreeNode* root){
    if(!root) return 0;
    if(!root->left && !root->right) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

int main(){
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    cout << countLeaves(root) << endl; // 输出3
    return 0;
}

2. 判别两棵树是否相等

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

3. 交换二叉树每个结点的左孩子和右孩子

void invertTree(TreeNode* root){
    if(!root) return;
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    invertTree(root->left);
    invertTree(root->right);
}

4. 设计二叉树的双序遍历算法

#include<iostream>
#include<stack>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

void doubleOrder(TreeNode* root){
    stack<TreeNode*> s;
    TreeNode* cur = root;
    while(cur || !s.empty()){
        while(cur){
            cout << cur->val << " ";
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        s.pop();
        cur = cur->right;
    }
}

int main(){
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    doubleOrder(root); // 输出 4 2 5 1 6 3
    return 0;
}

数据分析：

1. 统计二叉树叶结点个数：采用递归实现，时间复杂度为O(n)，其中n为节点数。空间复杂度为O(h)，其中h为二叉树的高度。
2. 判别两棵树是否相等：采用递归实现，时间复杂度为O(n)，其中n为节点数。空间复杂度为O(h)，其中h为二叉树的高度。
3. 交换二叉树每个结点的左孩子和右孩子：采用递归实现，时间复杂度为O(n)，其中n为节点数。空间复杂度为O(h)，其中h为二叉树的高度。
4. 设计二叉树的双序遍历算法：采用栈实现，时间复杂度为O(n)，其中n为节点数。空间复杂度为O(h)，其中h为二叉树的高度。