算法(二叉树的遍历)

༺ 个人主页 · 纪念229 ༻

🏠我的博客主页🏠

༒专栏目录：《数据结构》༒

༒专栏目录：《算法》༒

༒专栏目录：《MySQL数据库》༒

༒专栏目录：《前端开发》༒

༒其它有趣的计算机知识༒

༺世上本没有路，走的人多了自然就有了༻

---

这篇文章讲述的是我在刷算法题时遇到的一个题目，希望对你有所帮助

题目链接：https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef

注意本题代码用的是c语言

---

---

1.二叉树遍历

题目展示：

这里讲一个东西，ACM模式就是所有代码都是自己写，而核心代码模式就是些核心代码像是数组，结构体它系统一般会帮你写好

代码展示

#include<stdio.h>
#include<stdlib.h>
typedef struct tree {
    char val;
    struct tree* left;
    struct tree* right;
} tree;

tree* build(char* arr, int* num) {
   //先判断得到的字符是否为#,是的话不用创建节点
   //同时获得ch可直接赋值给本节点的val里
   char ch = arr[(*num)++];
   if(ch == '#'){
    return NULL;
   }
   tree* node = (tree*)malloc(sizeof(tree));
   node->val = ch;
   node->left = build(arr, num);
   node->right = build(arr, num);
   return node;
   //第一次return node返回的是头指针其它递归函数return node是将取到的节点赋值给node的下一个节点
   //要给节点添加内容首先要给节点创造空间
}
void orderprintf(tree* node) {
    if (node == NULL) return;
    orderprintf(node->left);
    printf("%c ", node->val);
    //建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果
    //这个意思就是将二叉树根据中序排序打印出来
    orderprintf(node->right);
}
int main() {
    char arr[100];
    scanf("%s", arr);
    int num = 0;
    //构建二叉树并且进行
    tree* root = build( arr, &num);
    //中序遍历
    orderprintf(root);
    return 0 ;
}

具体讲解
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

读入用户输入的一串先序遍历字符串
这个说明我们要弄一个字符数组
然后输入一段数字字符

char arr[100];
    scanf("%s", arr);
    int num = 0;

这个num是作为下标遍历数组组织给二叉树

最后将数字字符串用先序排序排好（根据此字符串建立一个二叉树（以指针方式存储））

用指针方式存储就意味着要创建malloc空间但是算法题不用将它free

tree* root = build( arr, &num);

用&是为了将num在局部变量的值在全局变量中用得上

还有就是不要随便创建指针类型，因为创建指针类型都要创建空间，我们一般用普通类型就可以
这里用指针类型的原因是二叉树由结构体构成找到地址就找到所有二叉树节点
二叉树节点怎么来的这里就不赘述了

tree* build(char* arr, int* num) {
   //先判断得到的字符是否为#,是的话不用创建节点
   //同时获得ch可直接赋值给本节点的val里
   char ch = arr[(*num)++];
   if(ch == '#'){
    return NULL;
   }
   tree* node = (tree*)malloc(sizeof(tree));
   node->val = ch;
   node->left = build(arr, num);
   node->right = build(arr, num);
   return node;
   //第一次return node返回的是头指针其它递归函数return node是将取到的节点赋值给node的下一个节点
   //要给节点添加内容首先要给节点创造空间
}

用先序遍历就要遍历这里的区别就是要加个#字符的判断如果字符是#就返回
我们这里#字符作用就是作为空（某些场景有用）
没的话我们就这样

 node->val =arr[(*num)++];
 node->left = build(arr, num);
 node->right = build(arr, num);

然后我们创建一个指针节点node用malloc给它创建空间

这里就说到指针的好处了无论是普通变量还是指针变量都是在栈上函数结束栈空间就返回
但是指针变量指向的地址在堆上（由maolloc创建）堆不会随函数结束就结束所以指针所具有的数据不会消失

这里可能有人会问如果遇到#不就结束了吗？
不会因为是递归它只是结束某个函数其它函数正常进行

最后返回二叉树地址

建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

void orderprintf(tree* node) {
    if (node == NULL) return;
    orderprintf(node->left);
    printf("%c ", node->val);
    //建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果
    //这个意思就是将二叉树根据中序排序打印出来
    orderprintf(node->right);
}

这句话的意思就是按照中序遍历把先序遍历的二叉树打印出来当然在PowerShell里是一行一行的
首先遍历二叉树的节点当然要判断节点是否为NULL是NULL的话直接返回
当然既然用到前中后序遍历当然要用递归

---

文章到这就告一段落，希望对你有所帮助，感谢观看！

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2503_94479566/article/details/164164475