二叉树是什么？
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分
思路：
首先，需要创建一个BTNode的结点，结点包含了数据，两个指针——lchild和rchild，再一个BTNode的构造函数，来初始化结点
接着，创建二叉树的类，类包含了头结点，以及各函数的实现操作。（初始化函数、创建树函数、遍历函数、求树的结点个数、求树的叶子数、求树的深度）
代码如下：
using namespace std; typedef int Element; //定义结点 struct BTNode { Element data; BTNode* lchild; BTNode* rchild; //结构体的构造函数 BTNode(Element number) { data = number; lchild = NULL; rchild = NULL; } }; //定义二叉树类 class Btree { public: BTNode* Root; //初始化创建树头 void Init() { Root = CreatBTree(); cout << "树创建成功" << endl; } //创建树(前序) BTNode* CreatBTree() { BTNode* p; Element number; cin >> number; if (number == 0) p = NULL; else { p = new BTNode(number); p->lchild = CreatBTree(); p->rchild = CreatBTree(); } return p; } //前序遍历 void preOrderTraverse(BTNode *root) { if (root) { cout << root->data << " "; preOrderTraverse(root->lchild); preOrderTraverse(root->rchild); } } //中序遍历 void inOrderTraverse(BTNode* root) { if (root) { inOrderTraverse(root->lchild); cout << root->data << " "; inOrderTraverse(root->rchild); } } //后序遍历 void lastOrderTraverse(BTNode* root) { if (root) { lastOrderTraverse(root->lchild); lastOrderTraverse(root->rchild); cout << root->data << " "; } } //求叶子结点个数 int LeafNum(BTNode* root) { if (root == NULL) { return 0; } else if (root->lchild == NULL && root->rchild == NULL) return 1; else return LeafNum(root->lchild) + LeafNum(root->rchild); } //求树的结点个数 int BTNodeNum(BTNode* root) { if (root == NULL) return 0; else return BTNodeNum(root->lchild) + BTNodeNum(root->rchild) + 1; } //求树的深度 int TreeDepth(BTNode* root) { if (root == NULL) return 0; int left = TreeDepth(root->lchild); int right = TreeDepth(root->rchild); return left > right ? left + 1 : right + 1; } }; int main() { Btree T; //初始化 T.Init(); //遍历 cout << "前序遍历为：" << endl; T.preOrderTraverse(T.Root); cout << endl; cout << "中序遍历为：" << endl; T.inOrderTraverse(T.Root); cout << endl; cout << "后序遍历为：" << endl; T.lastOrderTraverse(T.Root); cout << endl; //树的结点个数 cout << "树的结点个数为："; int nodenum = T.BTNodeNum(T.Root); cout << nodenum << endl; //树的叶子个数 cout << "树的叶子个数为："; int leaves = T.LeafNum(T.Root); cout << leaves << endl; //树的深度为： cout << "树的深度为："; int depth = T.TreeDepth(T.Root); cout << depth << endl; system("pause"); cout << endl; }
