二叉树简单实现(创建、遍历、叶子数等)

直接代码吧,有问题可以讨论,基本都是采用递归的方式求解,创建二叉树,这个例子对于root结点只有左孩子:

 

[cpp]
  1. #include “stdafx.h”
  2. #include<stdlib.h>
  3. #include “math.h”
  4. #include <iostream>
  5. using namespace std;
  6. typedef struct BiTreeNode
  7. {
  8.     char data;
  9.     BiTreeNode *left;
  10.     BiTreeNode *right;
  11. }BiTreeNode,*PBiTreeNode;
  12. static int iCnt = 0;
  13. void CreateBiTree(PBiTreeNode &Tree)//创建二叉树
  14. {
  15.     char s[]=”ABC$$D$EF$$G$$$”;
  16.     char ch = s[iCnt++];
  17.     if ( ch == ‘$’ )//$代表不存在
  18.         Tree = NULL;
  19.     else
  20.     {
  21.         Tree = (PBiTreeNode)malloc(sizeof(BiTreeNode));
  22.         if (!Tree)
  23.             exit(OVERFLOW);
  24.         Tree->data = ch;
  25.         CreateBiTree(Tree->left);
  26.         CreateBiTree(Tree->right);
  27.     }
  28. }
  29. void PreOder(PBiTreeNode Tree)//先序遍历
  30. {
  31.     if ( !Tree )
  32.         return;
  33.     cout << Tree->data << endl;
  34.     if ( Tree->left )
  35.         PreOder( Tree->left );
  36.     if ( Tree->right )
  37.         PreOder( Tree->right);
  38. }
  39. void InOder(PBiTreeNode Tree)//中序遍历
  40. {
  41.     if ( !Tree )
  42.         return;
  43.     if ( Tree->left )
  44.         InOder( Tree->left );
  45.     cout << Tree->data << endl;
  46.     if ( Tree->right )
  47.         InOder( Tree->right );
  48. }
  49. void PostOder(PBiTreeNode Tree)//后序遍历
  50. {
  51.     if ( !Tree )
  52.         return;
  53.     if ( Tree->left )
  54.         InOder( Tree->left );
  55.     if ( Tree->right )
  56.         InOder( Tree->right );
  57.     cout << Tree->data << endl;
  58. }
  59. void PrintBiTree(PBiTreeNode Tree)//打印二叉树
  60. {
  61.     if ( !Tree )
  62.         return;
  63.     cout << Tree->data << endl;
  64.     if ( Tree->left || Tree->right )
  65.     {
  66.         cout <<“(“;
  67.         PrintBiTree(Tree->left);
  68.         if ( !Tree->right )
  69.             cout <<“,”;
  70.         PrintBiTree(Tree->right);
  71.         cout <<“)”;
  72.     }
  73. }
  74. int TreeDepth(PBiTreeNode Tree) //二叉树的深度
  75. {
  76.     int lDepth = 0, rDepth = 0;
  77.     if ( !Tree )
  78.         return 0;
  79.     lDepth = TreeDepth( Tree->left );
  80.     rDepth = TreeDepth( Tree->right );
  81.     return lDepth > rDepth ? (lDepth + 1) : (rDepth + 1);
  82. }
  83. int LeavesNum(PBiTreeNode Tree)//叶子数
  84. {
  85.     if ( !Tree )
  86.         return 0;
  87.     else if ( !Tree->left && !Tree->right )
  88.         return 1;
  89.     else
  90.         return LeavesNum( Tree->left ) + LeavesNum( Tree->right );
  91. }
  92. void DestroyBiTree(PBiTreeNode &Tree)
  93. {
  94.     if ( !Tree)
  95.         return;
  96.     else
  97.     {
  98.         DestroyBiTree( Tree->left );
  99.         DestroyBiTree( Tree->right);
  100.         free(Tree);
  101.         Tree = NULL;
  102.     }
  103. }
  104. int main()
  105. {
  106.     PBiTreeNode Tree;
  107.     CreateBiTree( Tree );
  108.     cout <<“输出二叉树:”<<endl;
  109.     PrintBiTree( Tree );
  110.     cout << endl;
  111.     cout <<“先序遍历结果:”<<endl;
  112.     PreOder( Tree );
  113.     cout <<“中序遍历结果:”<<endl;
  114.     InOder( Tree );
  115.     cout <<“后序遍历结果:”<<endl;
  116.     PostOder( Tree );
  117.     cout <<“树的高度:”<<TreeDepth( Tree )<<endl;
  118.     cout <<“叶子结点个数:”<< LeavesNum( Tree )<<endl;
  119.     DestroyBiTree( Tree );
  120. }

标签