企业官网怎么编辑,游戏网站seo怎么做,广告网站布局,介绍家乡的网站怎么做文章目录 1.原题2.算法思想2.1.求树的高度2.2.求路径 3.关键代码4.完整代码5.输出结果 1.原题
试编写算法#xff0c;求给定二叉树上从根节点到叶子节点的一条路径长度等于树的深度减一的路径#xff08;即列出从根节点到该叶子节点的节点序列#xff09;#xff0c;若这样… 文章目录 1.原题2.算法思想2.1.求树的高度2.2.求路径 3.关键代码4.完整代码5.输出结果 1.原题
试编写算法求给定二叉树上从根节点到叶子节点的一条路径长度等于树的深度减一的路径即列出从根节点到该叶子节点的节点序列若这样的路径存在多条则输出路径终点在“最左”的一条。
2.算法思想
计算出树的高度然后再进行类前序遍历输出路径为最深的、最靠左的一条。分为两部分。1.求树的高度2.求路径
2.1.求树的高度
这个算法在14年某个题已经涉及到了。通过遍历的方式得出每一个结点的左子树高度和右子树高度而该结点的高度就是左子树高度和右子树高度较大的那一个1
2.2.求路径
由于是求最靠左的一条、最深的一条路径那么用类先序遍历的方式进行探索最有优势。根据先序遍历的特点我们第一次找到的路径即为最左边的。同时引入了一个变量isFound这样在找到一条路径之后可以更快跳过后续的递归嵌套。
3.关键代码
/*** struct treeNode* brief 二叉树节点的结构体*/
struct treeNode {int data; /** 节点存储的数据 */struct treeNode *lchild; /** 左子节点指针 */struct treeNode *rchild; /** 右子节点指针 */
};/*** brief 计算二叉树的高度。** 通过递归地计算左右子树的高度返回树的高度。** param root 二叉树根节点指针。* return 返回二叉树的高度。*/
int treeHeight(struct treeNode *root) {if (root NULL) {return 0; // 如果根节点为空返回0表示树的高度为0} else {int leftHeight treeHeight(root-lchild); // 递归计算左子树的高度int rightHeight treeHeight(root-rchild); // 递归计算右子树的高度// 返回左右子树中较大的高度加上当前节点的高度加1return (leftHeight rightHeight) ? leftHeight 1 : rightHeight 1;}
}/*** brief 在二叉树中查找具有特定深度的路径** 通过递归遍历二叉树查找根到叶子节点的路径其深度等于指定高度并打印该路径。** param root 二叉树根节点指针。* param isFound 指向一个布尔值的指针用于判断是否已找到特定深度的路径。* param height 期望的路径深度。* param depth 当前递归深度。* param path 用于存储路径节点值的数组。*/
void findPath(struct treeNode *root, bool *isFound, int height, int depth, int path[]) {if (root NULL || (*isFound) true) {return; // 如果根节点为空或已找到路径则直接返回}path[depth] root-data; // 将当前节点值存入路径数组中if (depth height - 1) {(*isFound) true; // 标记已找到路径for (int i 0; i height; i) {printf(%d , path[i]); // 打印路径节点值}printf(\n);return;} else {depth 1; // 增加深度findPath(root-lchild, isFound, height, depth, path); // 递归遍历左子树findPath(root-rchild, isFound, height, depth, path); // 递归遍历右子树}
}/*** brief 寻找二叉树中指定深度的路径** 通过计算二叉树的高度创建对应高度的数组并在树中查找深度为高度减一的路径。* 找到后打印该路径上的节点值。** param root 二叉树根节点指针。*/
void findSpecialPath(struct treeNode *root) {int height treeHeight(root); // 计算二叉树的高度int path[height]; // 创建与高度相同大小的数组用于存储路径节点值bool isFound false; // 指示是否找到特定深度的路径findPath(root, isFound, height, 0, path); // 查找特定深度的路径
}4.完整代码
#include stdio.h
#include stdlib.h
#include stdbool.h/*** struct treeNode* brief 二叉树节点的结构体*/
struct treeNode {int data; /** 节点存储的数据 */struct treeNode *lchild; /** 左子节点指针 */struct treeNode *rchild; /** 右子节点指针 */
};/*** brief 计算二叉树的高度。** 通过递归地计算左右子树的高度返回树的高度。** param root 二叉树根节点指针。* return 返回二叉树的高度。*/
int treeHeight(struct treeNode *root) {if (root NULL) {return 0; // 如果根节点为空返回0表示树的高度为0} else {int leftHeight treeHeight(root-lchild); // 递归计算左子树的高度int rightHeight treeHeight(root-rchild); // 递归计算右子树的高度// 返回左右子树中较大的高度加上当前节点的高度加1return (leftHeight rightHeight) ? leftHeight 1 : rightHeight 1;}
}/*** brief 在二叉树中查找具有特定深度的路径** 通过递归遍历二叉树查找根到叶子节点的路径其深度等于指定高度并打印该路径。** param root 二叉树根节点指针。* param isFound 指向一个布尔值的指针用于判断是否已找到特定深度的路径。* param height 期望的路径深度。* param depth 当前递归深度。* param path 用于存储路径节点值的数组。*/
void findPath(struct treeNode *root, bool *isFound, int height, int depth, int path[]) {if (root NULL || (*isFound) true) {return; // 如果根节点为空或已找到路径则直接返回}path[depth] root-data; // 将当前节点值存入路径数组中if (depth height - 1) {(*isFound) true; // 标记已找到路径for (int i 0; i height; i) {printf(%d , path[i]); // 打印路径节点值}printf(\n);return;} else {depth 1; // 增加深度findPath(root-lchild, isFound, height, depth, path); // 递归遍历左子树findPath(root-rchild, isFound, height, depth, path); // 递归遍历右子树}
}/*** brief 寻找二叉树中指定深度的路径** 通过计算二叉树的高度创建对应高度的数组并在树中查找深度为高度减一的路径。* 找到后打印该路径上的节点值。** param root 二叉树根节点指针。*/
void findSpecialPath(struct treeNode *root) {int height treeHeight(root); // 计算二叉树的高度int path[height]; // 创建与高度相同大小的数组用于存储路径节点值bool isFound false; // 指示是否找到特定深度的路径findPath(root, isFound, height, 0, path); // 查找特定深度的路径
}/*** brief 创建新的二叉树节点。** param data 新节点存储的数据。* return 指向新节点的指针。*/
struct treeNode *createNode(int data) {struct treeNode *newNode (struct treeNode *) malloc(sizeof(struct treeNode));newNode-data data;newNode-lchild NULL;newNode-rchild NULL;return newNode;
}/*** brief 以括号表示法打印二叉树。** param root 二叉树根节点指针。*/
void printBinaryTree(struct treeNode *root) {if (root NULL) {return;}printf((%d, root-data);if (root-lchild ! NULL || root-rchild ! NULL) {printf( );if (root-lchild NULL) {printf(( ));} else {printBinaryTree(root-lchild);}printf( );if (root-rchild NULL) {printf(( ));} else {printBinaryTree(root-rchild);}}printf());
}/*** brief 以树的结构方式打印二叉树。** param root 二叉树根节点指针。* param space 节点之间的间距。*/
void printTreeStructure(struct treeNode *root, int space) {if (root NULL) {return;}int count 5; // 调整节点之间的间距printTreeStructure(root-rchild, space count);for (int i 0; i space; i) {printf( );}printf(%d\n, root-data);printTreeStructure(root-lchild, space count);
}int main() {struct treeNode *root createNode(10); // 根节点为10root-lchild createNode(5);root-rchild createNode(15);root-lchild-lchild createNode(3);root-rchild-lchild createNode(12);root-rchild-rchild createNode(18);root-rchild-lchild-rchild createNode(13);root-rchild-rchild-rchild createNode(9);// 以括号表示法打印二叉树printf(Binary Tree Structure (Parenthesis Representation):\n);printBinaryTree(root);// 以树的结构方式打印二叉树printf(\nBinary Tree Structure:\n);printTreeStructure(root, 0);int height treeHeight(root);printf(Height of the tree: %d\n, height);// 寻找特定路径并打印printf(Special Path with length equal to tree depth - 1: \n);findSpecialPath(root);return 0;
}5.输出结果
