首页 > 代码库 > 二叉树入门(洛谷P1305)

二叉树入门(洛谷P1305)

题目描述

输入一串完全二叉树,用遍历前序打出。

输入输出格式

输入格式:

第一行为二叉树的节点数n。

后面n行,每一个字母为节点,后两个字母分别为其左右儿子。

空节点用*表示

输出格式:

前序排列的完全二叉树

输入输出样例

输入样例:
6abcbdicj*d**i**j**
输出样例:
abdicj

这道题是最最最简单的二叉树入门,就是建树的基本。由于用到了较多的指针,个人觉得要弄懂还是要好好思考的。
代码如下:
 1 #include <bits/stdc++.h> 2  3 using namespace std; 4 struct tree 5 { 6     char elem; 7     tree *l,*r;//两个指针分别代表左右子树 8 }*t[36];//创建一个指针数组 9 void gettree ()10 {11     char c[4];12     int m=1,n;13     scanf("%d",&n);14     for (int i=1;i<=n;++i)15     {16         scanf("%s",c);17         if (i==1)//i=1时代表最上层根节点18         {19             t[i]=new tree;//t[i]这个指针指向一个新的tree结构体20             t[i]->elem=c[0];21             t[i]->l=NULL;22             t[i]->r=NULL;23         }24         if (c[1]!=*)25         {26             m++;27             t[m]=new tree;//m代表树的节点标号28             t[m]->elem=c[1];29             t[m]->l=t[m]->r=NULL;30             t[i]->l=t[m];//将t[i]的左子树指针指向t[m]31         }32         if (c[2]!=*)33         {34             m++;35             t[m]=new tree;36             t[m]->elem= c[2];37             t[m]->l=t[m]->r=NULL;38             t[i]->r=t[m];39         }40     }41 }42 void qx (tree *tr)43 {44     if (tr)45     {46         printf("%c",tr->elem);//先打印当前节点47         qx(tr->l);//再打印当前节点的左子树48         qx(tr->r);//最后打印当前节点的右子树49     }50 }51 int main()52 {53     //freopen("de.txt","r",stdin);54     gettree();//读入数据并建树55     qx(t[1]);//按照先序排列输出二叉树56     printf("\n");57     return 0;58 }

 

二叉树入门(洛谷P1305)