首页 > 其它语言 > 二叉树创建及其遍历

二叉树创建及其遍历

还记得N年想在全盘电脑寻找一个文件,当时看那代码晦涩难懂,后来不了了之,最近复习了下二叉树,现在感觉全盘寻找文件不是想象的那么复杂。

 

[cpp][/cpp] view plaincopy在CODE上查看代码片派生到我的代码片
 
  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #include<malloc.h>  
  4. typedef char TElemType;  
  5. typedef struct SBiTNode  
  6. {  
  7.     TElemType data;  
  8.     struct SBiTNode *lchild,*rchild;  
  9. }BiTNode,*BiTree;  
  10. //采用左序遍历创建二叉树,用到的是递归算法,参数指针T有点晦涩难懂。  
  11. void CreateBiTree(BiTree *T)  
  12. {  
  13.     TElemType ch;  
  14.     scanf("%c",&ch);  
  15.     if(ch=='#')  
  16.         *T=NULL;  
  17.     else  
  18.     {  
  19.         *T=(BiTree)malloc( sizeof(BiTNode) );  
  20.         if(!*T)  
  21.             exit(-1);  
  22.         (*T)->data=ch;  
  23.         CreateBiTree(&(*T)->lchild);  
  24.         CreateBiTree(&(*T)->rchild);  
  25.     }  
  26. }  
  27. //前序遍历  
  28. void PreOrderTraverse(BiTree T)  
  29. {  
  30.     if(T==NULL)  
  31.         return;  
  32.     printf("%c",T->data);  
  33.     PreOrderTraverse(T->lchild);  
  34.     PreOrderTraverse(T->rchild);  
  35. }  
  36. //中序遍历  
  37. void InOrderTraverse(BiTree T)  
  38. {  
  39.     if(T==NULL)  
  40.         return;  
  41.     InOrderTraverse(T->lchild);  
  42.     printf("%c",T->data);  
  43.     InOrderTraverse(T->rchild);  
  44. }  
  45. //后序遍历  
  46. void PostOrderTraverse(BiTree T)  
  47. {  
  48.     if(T==NULL)  
  49.         return;  
  50.     PostOrderTraverse(T->lchild);  
  51.     PostOrderTraverse(T->rchild);  
  52.     printf("%c",T->data);  
  53. }  
  54. //主函数  
  55. int main()  
  56. {  
  57.     BiTree T;  
  58.     CreateBiTree(&T);       //创建二叉树  
  59.     PreOrderTraverse(T);    //左序遍历  
  60.     printf("\n");  
  61.     InOrderTraverse(T);     //中序遍历  
  62.     printf("\n");  
  63.     PostOrderTraverse(T);   //后序遍历  
  64.     printf("\n");  
  65.     return 0;  
  66. }   

 

        本段代码CreateBiTree函数的形参为BiTree *T,为何是这样的,值得去思考下。目的是主函数创建了结构体指针T,如果形参为BiTree T,调用CreateBinary后,它传递的是值传递,最后的结构就是二叉树创建后,你无法拥有二叉树的根节点指针,相当于创建的二叉树内存创建了,可是你却找不到它。

        程序运行效果图如下:


本文固定链接: http://www.devba.com/index.php/archives/3501.html | 开发吧

报歉!评论已关闭.