比较下列概念 叶子结点和分支结点、结点的度和树的度、孩子兄弟与双亲、结点的层数和树的深度、有序树与无序树

叶子结点是没有子节点的节点，分支结点是有子节点的节点。结点的度是其子节点的数量，树的度是所有结点中度最大的值。孩子兄弟表示每个节点只有一个孩子和一个兄弟，双亲表示每个节点只有一个父亲。结点的层数是它到根节点的距离，树的深度是根节点到叶子节点的最长距离。有序树是子节点有顺序的树，而无序树则没有子节点的顺序限制。

相关问题

c++ 创建二叉树 遍历二叉树 计算叶子结点个数和树的深度 二叉树查找指定结点的双亲和兄弟 并用主函数测试

好的，我来为你解答。

首先，我们需要设计一个二叉树的节点结构体，包含左右子树指针和节点值：

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

接着，我们可以通过递归的方式来创建二叉树：

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

创建好二叉树后，我们可以通过递归的方式来遍历二叉树：

void preOrder(TreeNode* root) { // 前序遍历
    if (!root) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root) { // 中序遍历
    if (!root) {
        return;
    }
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

void postOrder(TreeNode* root) { // 后序遍历
    if (!root) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

计算二叉树的叶子节点个数和深度可以通过递归的方式来实现：

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

int getDepth(TreeNode* root) {
    if (!root) {
        return 0;
    }
    int leftDepth = getDepth(root->left);
    int rightDepth = getDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

查找指定节点的双亲和兄弟节点可以通过递归的方式来实现：

void findSibling(TreeNode* root, int val, int& parent, int& sibling) {
    if (!root || (!root->left && !root->right)) {
        return;
    }
    if (root->left && root->left->val == val) {
        parent = root->val;
        sibling = (root->right) ? root->right->val : -1;
        return;
    }
    if (root->right && root->right->val == val) {
        parent = root->val;
        sibling = (root->left) ? root->left->val : -1;
        return;
    }
    findSibling(root->left, val, parent, sibling);
    findSibling(root->right, val, parent, sibling);
}

int findParent(TreeNode* root, int val) {
    if (!root || (!root->left && !root->right)) {
        return -1;
    }
    if ((root->left && root->left->val == val) || (root->right && root->right->val == val)) {
        return root->val;
    }
    int leftParent = findParent(root->left, val);
    if (leftParent != -1) {
        return leftParent;
    }
    int rightParent = findParent(root->right, val);
    if (rightParent != -1) {
        return rightParent;
    }
    return -1;
}

最后，我们可以在主函数中测试这些函数：

int main() {
    TreeNode* root = createTree();
    cout << "前序遍历：";
    preOrder(root);
    cout << endl;
    cout << "中序遍历：";
    inOrder(root);
    cout << endl;
    cout << "后序遍历：";
    postOrder(root);
    cout << endl;
    cout << "叶子节点个数：" << countLeaf(root) << endl;
    cout << "树的深度：" << getDepth(root) << endl;
    int parent = -1, sibling = -1;
    findSibling(root, 4, parent, sibling);
    cout << "节点 4 的双亲为：" << findParent(root, 4) << "，兄弟为：" << sibling << endl;
    return 0;
}

这样就完成了二叉树的创建、遍历、计算叶子节点个数和深度、查找指定节点的双亲和兄弟节点的操作。

c++ 二叉树 前序中序后序遍历二叉树 计算树的深度 计算叶子结点个数 查找双亲 查找兄弟 代码

二叉树的定义：

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

前序遍历：

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 countLeafNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

查找双亲节点：

TreeNode* getParent(TreeNode* root, TreeNode* child) {
    if (root == nullptr || root == child) return nullptr;
    if (root->left == child || root->right == child) return root;
    TreeNode* parent = getParent(root->left, child);
    if (parent != nullptr) return parent;
    return getParent(root->right, child);
}

查找兄弟节点：

TreeNode* getSibling(TreeNode* root, TreeNode* child) {
    if (root == nullptr || root == child) return nullptr;
    if (root->left == child) return root->right;
    if (root->right == child) return root->left;
    TreeNode* sibling = getSibling(root->left, child);
    if (sibling != nullptr) return sibling;
    return getSibling(root->right, child);
}

注意：以上代码仅供参考，实际使用中需要根据具体情况进行修改和适配。