算法(二叉树的遍历)

༺ 个人主页 · 纪念229 ༻我的博客主页༒专栏目录《数据结构》༒༒专栏目录《算法》༒༒专栏目录《MySQL数据库》༒༒专栏目录《前端开发》༒༒其它有趣的计算机知识༒༺世上本没有路走的人多了自然就有了༻这篇文章讲述的是我在刷算法题时遇到的一个题目希望对你有所帮助题目链接https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef注意本题代码用的是c语言文章目录1.二叉树遍历1.二叉树遍历题目展示这里讲一个东西ACM模式就是所有代码都是自己写而核心代码模式就是些核心代码像是数组结构体它系统一般会帮你写好代码展示#includestdio.h#includestdlib.htypedefstructtree{charval;structtree*left;structtree*right;}tree;tree*build(char*arr,int*num){//先判断得到的字符是否为#,是的话不用创建节点//同时获得ch可直接赋值给本节点的val里charcharr[(*num)];if(ch#){returnNULL;}tree*node(tree*)malloc(sizeof(tree));node-valch;node-leftbuild(arr,num);node-rightbuild(arr,num);returnnode;//第一次return node返回的是头指针其它递归函数return node是将取到的节点赋值给node的下一个节点//要给节点添加内容首先要给节点创造空间}voidorderprintf(tree*node){if(nodeNULL)return;orderprintf(node-left);printf(%c ,node-val);//建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果//这个意思就是将二叉树根据中序排序打印出来orderprintf(node-right);}intmain(){chararr[100];scanf(%s,arr);intnum0;//构建二叉树并且进行tree*rootbuild(arr,num);//中序遍历orderprintf(root);return0;}具体讲解编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。读入用户输入的一串先序遍历字符串这个说明我们要弄一个字符数组然后输入一段数字字符chararr[100];scanf(%s,arr);intnum0;这个num是作为下标遍历数组组织给二叉树最后将数字字符串用先序排序排好根据此字符串建立一个二叉树以指针方式存储用指针方式存储就意味着要创建malloc空间但是算法题不用将它freetree* root build( arr, num);用是为了将num在局部变量的值在全局变量中用得上还有就是不要随便创建指针类型因为创建指针类型都要创建空间我们一般用普通类型就可以这里用指针类型的原因是二叉树由结构体构成找到地址就找到所有二叉树节点二叉树节点怎么来的这里就不赘述了tree*build(char*arr,int*num){//先判断得到的字符是否为#,是的话不用创建节点//同时获得ch可直接赋值给本节点的val里charcharr[(*num)];if(ch#){returnNULL;}tree*node(tree*)malloc(sizeof(tree));node-valch;node-leftbuild(arr,num);node-rightbuild(arr,num);returnnode;//第一次return node返回的是头指针其它递归函数return node是将取到的节点赋值给node的下一个节点//要给节点添加内容首先要给节点创造空间}用先序遍历就要遍历这里的区别就是要加个#字符的判断如果字符是#就返回我们这里#字符作用就是作为空某些场景有用没的话我们就这样node-valarr[(*num)];node-leftbuild(arr,num);node-rightbuild(arr,num);然后我们创建一个指针节点node用malloc给它创建空间这里就说到指针的好处了无论是普通变量还是指针变量都是在栈上函数结束栈空间就返回但是指针变量指向的地址在堆上由maolloc创建堆不会随函数结束就结束所以指针所具有的数据不会消失这里可能有人会问如果遇到#不就结束了吗不会因为是递归它只是结束某个函数其它函数正常进行最后返回二叉树地址建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。voidorderprintf(tree*node){if(nodeNULL)return;orderprintf(node-left);printf(%c ,node-val);//建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果//这个意思就是将二叉树根据中序排序打印出来orderprintf(node-right);}这句话的意思就是按照中序遍历把先序遍历的二叉树打印出来当然在PowerShell里是一行一行的首先遍历二叉树的节点当然要判断节点是否为NULL是NULL的话直接返回当然既然用到前中后序遍历当然要用递归文章到这就告一段落希望对你有所帮助感谢观看