1 //First Edit Time:    2014-11-26 12:04  2 //Last Edit Time:    2014-11-26 12:52  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 using namespace std;  7   8 struct BTreeNode  9 { 10     int data; 11     BTreeNode *lChild,*rChild; 12 }; 13  14 class BTree 15 { 16     public: 17         void Set_Root(BTreeNode* r){ root=r;} 18         BTreeNode* Get_Root() { return root;} 19         BTreeNode* CreatBTree(); 20          21         void InOrder(BTreeNode* r);//中序遍历(递归) 22         void PreOrder(BTreeNode *r); 23         void PostOrder(BTreeNode *r); 24  25         int Count_BTree(BTreeNode*); // 结点个数 26         int Leaves_BTree(BTreeNode*); //叶子结点 27         int Height_BTree(BTreeNode*); //　树高 28         BTreeNode* root; 29 }; 30  31 //建立二叉树的算法 32 BTreeNode* BTree::CreatBTree() 33 { 34     BTreeNode* current=0; 35     int val=0; 36  37     cin>>val; 38     if(val==-1) 39         return NULL; 40     else 41     { 42         current=new BTreeNode; 43         current->data=http://www.mamicode.com/val; 44         current->lChild = CreatBTree(); 45         current->rChild = CreatBTree(); 46         return current; 47     } 48 } 49  50  51 //中序访问二叉树(递归) 52 void BTree::InOrder(BTreeNode* r) 53 { 54     if(r) 55     { 56         InOrder(r->lChild); 57         cout<<r->data<<" "; 58         InOrder(r->rChild); 59     } 60 } 61  62 //前序递归访问二叉树(递归) 63 void BTree::PreOrder(BTreeNode* r) 64 { 65     if(r) 66     { 67         cout<<r->data<<" "; 68         PreOrder(r->lChild); 69         PreOrder(r->rChild); 70     } 71 } 72  73  74 //后序遍历(递归) 75 void BTree::PostOrder(BTreeNode* r) 76 { 77     if(r) 78     { 79         PostOrder(r->lChild); 80         PostOrder(r->rChild); 81         cout<<r->data<<" "; 82     } 83 } 84  85 //求二叉树结点个数的函数 86 int BTree::Count_BTree(BTreeNode* r) 87 { 88     if(r==0) 89         return 0;  90     else 91         return 1 + Count_BTree (r->lChild) + Count_BTree(r->rChild); 92 } 93  94 //求二叉树叶子结点个数的函数 95 int BTree::Leaves_BTree(BTreeNode* r) 96 { 97     if(r==0)  98         return 0;  99     else if(r->lChild == 0 && r->rChild == 0)100             return 1;101     else102         return Leaves_BTree(r->lChild) + Leaves_BTree(r->rChild);103 }104 105 //求二叉树高度的函数106 int BTree::Height_BTree(BTreeNode* r)107 {108     if(r==0)109         return 0;110     else111     {112         int left = Height_BTree(r->lChild);113         int right = Height_BTree(r->rChild);114         return (left > right) ? left + 1 : right+1;115     }116 }117 118 int main()119 {120     BTree tree;121     int op;122     tree.CreatBTree();123     while(1)124     {125         puts("操作如下：\n*******************");126         printf("1.前序遍历\n2.中序遍历\n3.后序遍历\n4.节点个数\n5.叶子结点个数\n6.二叉树高度\n7.获取跟结点\n\n");127         cin >> op;128         if(op == 1)129             tree.InOrder(tree.root);130         else if(op == 2)131             tree.PreOrder(tree.root);132         else if(op == 3)133             tree.PostOrder(tree.root);134         else if (op == 4)135             tree.Count_BTree(tree.root);136         else if(op==5)137             tree.Leaves_BTree (tree.root);138         else if(op == 6)139             tree.Height_BTree (tree.root);140         else if (op == 7)141         {142             BTreeNode* tmp = tree.Get_Root();143             cout << tmp->data << endl;144         }145         else break;146     }147     return 0;148 }