构建如图所示的二叉树,并利用算法先序、中序、后序遍历二叉树,输出二叉树的叶子结点,树叶子节点个数,计算二叉树的高度,以及树形打印二叉树。
时间: 2023-04-25 10:03:15 浏览: 121
C语言二叉树的三种遍历方式的实现及原理
5星 · 资源好评率100%
抱歉,我是AI语言模型,无法看到您提供的图示。但是,我可以告诉您如何构建二叉树,以及如何进行先序、中序、后序遍历、输出叶子结点、计算叶子节点个数、计算二叉树的高度和树形打印二叉树。
构建二叉树:
二叉树是一种树形结构,每个节点最多有两个子节点。构建二叉树的方法有很多种,最常用的是递归法。递归法的基本思想是:先构建根节点,然后递归构建左子树和右子树。
先序遍历:
先序遍历是指先访问根节点,然后访问左子树,最后访问右子树。先序遍历的递归实现如下:
void preOrder(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
中序遍历:
中序遍历是指先访问左子树,然后访问根节点,最后访问右子树。中序遍历的递归实现如下:
void inOrder(TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
后序遍历:
后序遍历是指先访问左子树,然后访问右子树,最后访问根节点。后序遍历的递归实现如下:
void postOrder(TreeNode* root) {
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
输出叶子结点:
叶子结点是指没有子节点的节点。输出叶子结点的递归实现如下:
void printLeaves(TreeNode* root) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
cout << root->val << " ";
}
printLeaves(root->left);
printLeaves(root->right);
}
计算叶子节点个数:
计算叶子节点个数的递归实现如下:
int countLeaves(TreeNode* root) {
if (root == NULL) return ;
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
计算二叉树的高度:
二叉树的高度是指从根节点到最远叶子节点的距离。计算二叉树的高度的递归实现如下:
int height(TreeNode* root) {
if (root == NULL) return ;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return max(leftHeight, rightHeight) + 1;
}
树形打印二叉树:
树形打印二叉树可以使用递归实现。具体实现方法可以参考以下链接:https://www.cnblogs.com/grandyang/p/4606334.html
阅读全文