原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/2018/1012/68.html

二叉树的基本操作： 包括创建二叉树，遍历二叉树(先序、中序和后序)，求二叉树深度，求二叉树结点数，求叶子结点数。

其中创建二叉树是先序创建的，即输入的时候要按二叉树先序输入。

今天我们常州网站建设幻天网络就来讨论一下二叉树，废话不说直接看代码

  1 #include <iostream>

  2 using namespace std;

  3 

  4 struct BiTNode

  5 {

  6     int data;

  7     BiTNode *lchild, *rchild;

  8 };

  9 

 10 //先序建立二叉树

 11 void CreateBitTree(BiTNode *&root)

 12 {

 13     int value;

 14     cin >> value;

 15     if (value == -1)

 16         root = NULL;

 17     else

 18     {

 19         root = new BiTNode;

 20         root->data = value;

 21         CreateBitTree(root->lchild);

 22         CreateBitTree(root->rchild);

 23     }

 24 }

 25 

 26 //先序遍历

 27 void PreorderTraversal(BiTNode *root)

 28 {

 29     if (root)

 30     {

 31         cout << root->data << ' ';

 32         PreorderTraversal(root->lchild);

 33         PreorderTraversal(root->rchild);

 34     }

 35 }

 36 

 37 //中序遍历

 38 void InorderTraversal(BiTNode *root)

 39 {

 40     if (root)

 41     {

 42         InorderTraversal(root->lchild);

 43         cout << root->data << ' ';

 44         InorderTraversal(root->rchild);

 45     }

 46 }

 47 

 48 //后序遍历

 49 void PostorderTraversal(BiTNode *root)

 50 {

 51     if (root)

 52     {

 53         PostorderTraversal(root->lchild);

 54         PostorderTraversal(root->rchild);

 55         cout << root->data << ' ';

 56     }

 57 }

 58 

 59 int GetDepth(BiTNode *root)

 60 {

 61     if (root == NULL)

 62         return 0;

 63     else

 64     {

 65         int ldep = GetDepth(root->lchild);

 66         int rdep = GetDepth(root->rchild);

 67         return ldep >= rdep ? ldep + 1 : rdep + 1;

 68     }

 69 }

 70 

 71 int GetNodeCount(BiTNode *root)

 72 {

 73     if (root == NULL)

 74         return 0;

 75     return GetNodeCount(root->lchild) + GetNodeCount(root->rchild) + 1;

 76 }

 77 

 78 int GetLeafCount(BiTNode *root)

 79 {

 80     if (root == NULL)

 81         return 0;

 82     else if (root->lchild == NULL && root->rchild == NULL)

 83         return 1;

 84     else

 85         return GetLeafCount(root->lchild) + GetLeafCount(root->rchild);

 86 }

 87 

 88 int main()

 89 {

 90     BiTNode *root = NULL;

 91     CreateBitTree(root);

 92     cout << "先序遍历：" << endl;

 93     PreorderTraversal(root);

 94     cout << "中序遍历：" << endl;

 95     InorderTraversal(root);

 96     cout << "后序遍历：" << endl;

 97     PostorderTraversal(root);

 98     cout << "二叉树深度：" << GetDepth(root) << endl;

 99     cout << "结点个数：" << GetNodeCount(root) << endl;

100     cout << "叶子个数：" << GetLeafCount(root) << endl;

101     system("pause");

102 }

输出结果：

创建的是如下的一颗二叉树：

                1

        2               3

    4      -1     -1       -1

-1     -1