你好,游客 登录 注册 搜索
背景:
阅读新闻

数据结构之---C语言实现二叉树的二叉链表存储表示

[日期:2015-06-15] 来源:CSDN博客  作者:杨鑫newlfe [字体: ]
[cpp] view plaincopyprint?
  1. //二叉树的二叉链表存储表示 
  2. //杨鑫 
  3. #include <stdio.h> 
  4. #include <stdlib.h> 
  5. #define max(a, b) a > b ? a : b                      //自定义max()函数 
  6. typedef char TELemType; 
  7. //定义结二叉树的构体 
  8. typedef struct BTree                 
  9.     TELemType data; 
  10.     struct BTree *lChild; 
  11.     struct BTree *rChild; 
  12. }BinTree; 
  13.  
  14.  
  15. //二叉树的创建 
  16. BinTree* CreateTree(BinTree *T) 
  17.     char temp; 
  18.     scanf("%c", &temp); 
  19.     if(temp == '0'
  20.             return 0; 
  21.     T = (BinTree *)malloc(sizeof(BinTree)); 
  22.     T->data = temp;                       
  23.     T->lChild = CreateTree(T->lChild);                    //递归创建左子树 
  24.     T->rChild = CreateTree(T->rChild);                    //递归创建右子树 
  25.     return T; 
  26.  
  27. //计算叶子结点的数量 
  28. int sumleft(BinTree *T) 
  29.     int sum = 0, leftNum, rightNum; 
  30.     if(T) 
  31.     { 
  32.         if((!T->lChild) && (!T->rChild)) 
  33.         { 
  34.             sum++; 
  35.         } 
  36.         leftNum = sumleft(T->lChild); 
  37.             sum += leftNum; 
  38.         rightNum = sumleft(T->lChild); 
  39.             sum += rightNum; 
  40.     } 
  41.     return sum; 
  42.  
  43.  
  44. //先序遍历二叉树 
  45. void PreOrderTraverse(BinTree *T) 
  46.     if(T) 
  47.     { 
  48.         printf("%c", T->data); 
  49.         PreOrderTraverse(T->lChild); 
  50.         PreOrderTraverse(T->rChild); 
  51.     } 
  52.  
  53.  
  54. //中序遍历二叉树 
  55. void InOrderTraverse(BinTree *T) 
  56.     if(T) 
  57.     { 
  58.         InOrderTraverse(T->lChild); 
  59.         printf("%c", T->data); 
  60.         InOrderTraverse(T->rChild); 
  61.     } 
  62.  
  63.  
  64. //后序遍历二叉树 
  65. void PostOrderTraverse(BinTree *T) 
  66.     if(T) 
  67.     { 
  68.         PostOrderTraverse(T->lChild); 
  69.         PostOrderTraverse(T->rChild ); 
  70.         printf("%c",T->data ); 
  71.    } 
  72.  
  73.  
  74. //统计树的深度 
  75. int getDepth(BinTree *T) 
  76.     int dep = 0, depleft, depright; 
  77.     if(!T) 
  78.             dep = 0; 
  79.     else 
  80.     { 
  81.         depleft = getDepth(T->lChild); 
  82.         depright = getDepth(T->rChild); 
  83.         dep = 1 + max(depleft, depright); 
  84.     } 
  85.     return dep; 
  86.  
  87.  
  88. int main() 
  89.     BinTree *Tree; 
  90.     Tree = CreateTree(Tree); 
  91.     printf("=========分隔符============\n\n"); 
  92.     printf("二叉树的先序遍历:\n"); 
  93.     PreOrderTraverse(Tree); 
  94.     printf("\n"); 
  95.     printf("二叉树的中序遍历:\n"); 
  96.     InOrderTraverse(Tree); 
  97.     printf("\n"); 
  98.     printf("二叉树的后序遍历:\n"); 
  99.     PostOrderTraverse(Tree); 
  100.     printf("\n"); 
  101.     printf("\n=========================\n"); 
  102.     printf("叶子结点数为: %d\n", sumleft(Tree)); 
  103.     printf("二叉树的深度为:%d\n", getDepth(Tree)); 
  104.     return 0; 

 

 

如图:

数据结构





收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (3)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款