在程序开始时用先序/中序/后序遍历的顺序建立二叉链表的递归算法

好的，这是一个经典的二叉树遍历问题。建立二叉链表的递归算法如下：

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void createBiTree(BiTree &T) {
    int ch;
    cin >> ch;
    if (ch == -1) {
        T = NULL;
    } else {
        T = new BiTNode;
        T->data = ch;
        createBiTree(T->lchild);
        createBiTree(T->rchild);
    }
}

在这里，我们使用了先序遍历的方式来建立二叉树。输入 `-1` 表示该节点为空，否则将输入的值赋给该节点，并递归地建立左子树和右子树。

如果你需要用中序或后序遍历的方式来建立二叉树，可以稍微修改一下递归的顺序即可。

相关问题

写一个完整程序开始时用先序/中序/后序遍历的顺序建立二叉链表的递归算法 要求1、先序遍历二叉树的递归算法 2、中序遍历二叉树的递归算法 3、后序遍历二叉树的递归算法 4、计算二叉树的深度的递归算法 5、统计二叉树的结点个数的递归算法 6、统计二叉树的叶子结点个数的递归算法 7、设计该二叉树第K层的结点个数。 8、求该二叉树中所有结点值最大的元素。 9、打印二叉树的叶子结点数的递归算法

好的，下面是一个完整的程序，实现了开始时用先序/中序/后序遍历的顺序建立二叉链表的递归算法，并且包含了您要求的所有功能：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <climits>

using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 先序遍历建立二叉树
TreeNode* buildTreeByPreOrder(vector<int>& preOrder, int& index) {
    if (index >= preOrder.size() || preOrder[index] == -1) {
        index++;
        return nullptr;
    }
    TreeNode* root = new TreeNode(preOrder[index++]);
    root->left = buildTreeByPreOrder(preOrder, index);
    root->right = buildTreeByPreOrder(preOrder, index);
    return root;
}

// 中序遍历建立二叉树
TreeNode* buildTreeByInOrder(vector<int>& inOrder, int& index, int start, int end) {
    if (index >= inOrder.size() || start > end) {
        return nullptr;
    }
    int i = start;
    for (; i <= end; i++) {
        if (inOrder[i] == inOrder[index]) {
            break;
        }
    }
    TreeNode* root = new TreeNode(inOrder[index++]);
    root->left = buildTreeByInOrder(inOrder, index, start, i - 1);
    root->right = buildTreeByInOrder(inOrder, index, i + 1, end);
    return root;
}

// 后序遍历建立二叉树
TreeNode* buildTreeByPostOrder(vector<int>& postOrder, int& index) {
    if (index < 0 || postOrder[index] == -1) {
        index--;
        return nullptr;
    }
    TreeNode* root = new TreeNode(postOrder[index--]);
    root->right = buildTreeByPostOrder(postOrder, index);
    root->left = buildTreeByPostOrder(postOrder, index);
    return root;
}

// 先序遍历二叉树的递归算法
void preOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历二叉树的递归算法
void inOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// 后序遍历二叉树的递归算法
void postOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

// 计算二叉树的深度的递归算法
int depth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftDepth = depth(root->left);
    int rightDepth = depth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

// 统计二叉树的结点个数的递归算法
int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftCount = countNodes(root->left);
    int rightCount = countNodes(root->right);
    return leftCount + rightCount + 1;
}

// 统计二叉树的叶子结点个数的递归算法
int countLeaves(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    int leftLeaves = countLeaves(root->left);
    int rightLeaves = countLeaves(root->right);
    return leftLeaves + rightLeaves;
}

// 设计该二叉树第K层的结点个数
int countNodesKthLevel(TreeNode* root, int k) {
    if (root == nullptr) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    int leftCount = countNodesKthLevel(root->left, k - 1);
    int rightCount = countNodesKthLevel(root->right, k - 1);
    return leftCount + rightCount;
}

// 求该二叉树中所有结点值最大的元素
int findMax(TreeNode* root) {
    if (root == nullptr) {
        return INT_MIN;
    }
    int leftMax = findMax(root->left);
    int rightMax = findMax(root->right);
    return max(max(leftMax, rightMax), root->val);
}

// 打印二叉树的叶子结点数的递归算法
void printLeaves(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        cout << root->val << " ";
        return;
    }
    printLeaves(root->left);
    printLeaves(root->right);
}

int main() {
    // 建立二叉树
    vector<int> preOrder = {1, 2, 4, -1, -1, 5, -1, -1, 3, 6, -1, -1, 7, -1, -1};
    int index = 0;
    TreeNode* root = buildTreeByPreOrder(preOrder, index);

    // 先序遍历
    cout << "PreOrder: ";
    preOrder(root);
    cout << endl;

    // 中序遍历
    cout << "InOrder: ";
    vector<int> inOrder;
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p != nullptr || !s.empty()) {
        while (p != nullptr) {
            s.push(p);
            p = p->left;
        }
        p = s.top();
        s.pop();
        inOrder.push_back(p->val);
        p = p->right;
    }
    index = 0;
    TreeNode* root2 = buildTreeByInOrder(inOrder, index, 0, inOrder.size() - 1);
    inOrder(root2);
    cout << endl;

    // 后序遍历
    cout << "PostOrder: ";
    vector<int> postOrder;
    stack<TreeNode*> s2;
    p = root;
    while (p != nullptr || !s2.empty()) {
        while (p != nullptr) {
            s2.push(p);
            postOrder.insert(postOrder.begin(), p->val);
            p = p->right;
        }
        p = s2.top();
        s2.pop();
        p = p->left;
    }
    index = postOrder.size() - 1;
    TreeNode* root3 = buildTreeByPostOrder(postOrder, index);
    postOrder(root3);
    cout << endl;

    // 计算二叉树深度
    cout << "Depth: " << depth(root) << endl;

    // 统计二叉树结点个数
    cout << "Count Nodes: " << countNodes(root) << endl;

    // 统计二叉树叶子结点个数
    cout << "Count Leaves: " << countLeaves(root) << endl;

    // 设计该二叉树第K层的结点个数
    int k = 3;
    cout << "Count Nodes in " << k << "th Level: " << countNodesKthLevel(root, k) << endl;

    // 求该二叉树中所有结点值最大的元素
    cout << "Max Value: " << findMax(root) << endl;

    // 打印二叉树的叶子结点数
    cout << "Leaves: ";
    printLeaves(root);
    cout << endl;

    return 0;
}

程序中，先序遍历、中序遍历、后序遍历建立二叉树的方法分别为buildTreeByPreOrder、buildTreeByInOrder、buildTreeByPostOrder。其他功能实现方法与前面给出的递归算法一致。

在程序开始时用先序/中序/后序遍历的顺序建立二叉链表的递归算法 1、先序遍历二叉树的递归算法 2、中序遍历二叉树的递归算法 3、后序遍历二叉树的递归算法 4、计算二叉树的深度的递归算法 5、统计二叉树的结点个数的递归算法 6、统计二叉树的叶子结点个数的递归算法 7、设计该二叉树第K层的结点个数。 8、求该二叉树中所有结点值最大的元素。 9、打印二叉树的叶子结点数的递归算法

1、先序遍历二叉树的递归算法：

void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

2、中序遍历二叉树的递归算法：

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

3、后序遍历二叉树的递归算法：

void postorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->val);
}

4、计算二叉树的深度的递归算法：

int maxDepth(struct TreeNode* root) {
    if (root == NULL) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

5、统计二叉树的结点个数的递归算法：

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

6、统计二叉树的叶子结点个数的递归算法：

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

7、设计该二叉树第K层的结点个数：

int countNodesAtKLevel(struct TreeNode* root, int k) {
    if (root == NULL || k < 1) return 0;
    if (k == 1) return 1;
    int leftCount = countNodesAtKLevel(root->left, k - 1);
    int rightCount = countNodesAtKLevel(root->right, k - 1);
    return leftCount + rightCount;
}

8、求该二叉树中所有结点值最大的元素：

int findMax(struct TreeNode* root) {
    if (root == NULL) return INT_MIN;
    int leftMax = findMax(root->left);
    int rightMax = findMax(root->right);
    return max(max(leftMax, rightMax), root->val);
}

9、打印二叉树的叶子结点数的递归算法：

void printLeafNodeCount(struct TreeNode* root) {
    printf("Leaf node count: %d\n", countLeafNodes(root));
}