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

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

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++算法求二叉树中第一条最长的路径长度，并输出此路径上各结点的值。

实际上，求二叉树中第一条最长的路径长度，可以通过求根节点的左右子树的深度之和来实现。具体实现方法如下：

#include<iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        maxLen = max(maxLen, leftDepth + rightDepth);
        return max(leftDepth, rightDepth) + 1;
    }

    void findLongestPath(TreeNode* root) {
        if (root == nullptr) return;
        if (maxDepth(root->left) + maxDepth(root->right) == maxLen) {
            cout << root->val << " ";
            findLongestPath(root->left);
            findLongestPath(root->right);
        }
        else if (maxDepth(root->left) == maxLen) {
            findLongestPath(root->left);
        }
        else {
            findLongestPath(root->right);
        }
    }

    int getLongestPath(TreeNode* root) {
        maxLen = 0;
        maxDepth(root);
        findLongestPath(root);
        return maxLen;
    }

private:
    int maxLen;
};

int main() {
    TreeNode* node1 = new TreeNode(1);
    TreeNode* node2 = new TreeNode(2);
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node4 = new TreeNode(4);
    TreeNode* node5 = new TreeNode(5);
    TreeNode* node6 = new TreeNode(6);
    TreeNode* node7 = new TreeNode(7);
    TreeNode* node8 = new TreeNode(8);

    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node6->right = node7;
    node5->left = node8;

    Solution solution;
    int maxLen = solution.getLongestPath(node1);
    cout << "The longest path length is: " << maxLen << endl;

    return 0;
}

在上面的代码中，我们定义了一个`Solution`类，其中包含三个函数：

- `maxDepth`函数：求以当前节点为根的子树的深度，并且更新最长路径长度。
- `findLongestPath`函数：根据最长路径长度，找到第一条最长的路径，并输出路径上的节点值。
- `getLongestPath`函数：计算整个二叉树的最长路径长度，并且调用`findLongestPath`函数输出路径上的节点值。

最后我们在`main`函数中构造了一个二叉树，并且调用`getLongestPath`函数来计算最长路径长度，并输出路径上的节点值。