二叉树-白红宇

二叉树

阅读量：5321 次

发布时间：2019-06-14

本文共 2877 字，大约阅读时间需要 9 分钟。

今天用到了二叉树，长时间不用，都快忘了，所以就练习着写了一个二叉树，采用的递归遍历。具体代码如下：

1 #include 
      
         2 using namespace std;  3 typedef struct BiTNode  4 {  5     char data;  6     struct BiTNode *lchild,*rchild;  7 }BiTNode,*biTree;  8   9 class MyBigTree 10 { 11 public: 12     MyBigTree(){} 13     ~MyBigTree(){} 14     void Create(biTree &T);//创建 15     void Preorder(biTree &T);//先序遍历打印二叉树  16     void Inorder(biTree &T);//中序遍历打印二叉树  17     void Postorder(biTree &T);//后续遍历打印二叉树  18     int LeafCount(biTree &T);//统计叶子节点的个数  19     int POstTreeDepth(biTree &T);//统计树的高度 20     void PreLeaforder(biTree &T); 21     biTree root;//数据 22     void Free(biTree &T);//释放 23 protected: 24     int MAX(int x,int y) 25     { 26         return (x>y?x:y); 27     } 28 private: 29 }; 30 //函数实现 31 void MyBigTree::Create(biTree &T) 32 { 33     char ch; 34     cin>>ch; 35     if (ch=='#') 36     { 37         T=NULL; 38     } 39     else 40     { 41         T=(BiTNode*)malloc(sizeof(BiTNode)); 42         T->data=ch; 43         Create(T->lchild); 44         Create(T->rchild); 45     } 46 } 47  48 void MyBigTree::Free(biTree &T) 49 { 50     if (T!=NULL) 51     { 52         Free(T->lchild); 53         Free(T->rchild); 54         free(T); 55         T=NULL; 56     } 57 } 58  59 void MyBigTree::Preorder(biTree &T) 60 { 61     if (T!=NULL) 62     { 63         cout<
       
        data<<" "; 64         Preorder(T->lchild); 65         Preorder(T->rchild); 66     } 67 } 68  69 void MyBigTree::Inorder(biTree &T) 70 { 71     if (T!=NULL) 72     { 73         Inorder(T->lchild); 74         cout<
        
         data<<" "; 75         Inorder(T->rchild); 76     } 77 } 78  79 void MyBigTree::Postorder(biTree &T) 80 { 81     if (T!=NULL) 82     { 83         Postorder(T->lchild); 84         Postorder(T->rchild); 85         cout<
         
          data<<" "; 86     } 87 } 88  89 int MyBigTree::LeafCount(biTree &T) 90 { 91     int leaf; 92     if (T==NULL) 93     { 94         return 0; 95     } 96     if (T->lchild==NULL&&T->rchild==NULL) 97     { 98         return 1; 99     }100     else101         leaf=LeafCount(T->lchild)+LeafCount(T->rchild);102     return leaf;103 }104 105 int  MyBigTree::POstTreeDepth(biTree &T)106 {107     int hl,hr,max;108     if (T==NULL)109     {110         return 0;111     }112     else113     {114         hl=POstTreeDepth(T->lchild);115         hr=POstTreeDepth(T->rchild);116         max=MAX(hl,hr);117         return max+1;118     }119 }120 121 void MyBigTree::PreLeaforder(biTree &T)122 {123     if (T!=NULL)124     {125         if (T->lchild==NULL&&T->rchild==NULL)126         {127             cout<
          
           data<<" ";128         }129         PreLeaforder(T->lchild);130         PreLeaforder(T->rchild);131     }132 }