本文有些递归有些摘自以下链接：点击传送
我当时自己在编写代码的时候主要碰到的问题是：对于递归，处于一种一看就会，一写就跪的境界，然后我去找资料理解递归 递归有神人总结为以下模板，仅供参考：
function recursion(大规模) { if (end_condition) { end; } else { //在将问题转换为子问题描述的每一步，都解决该步中剩余部分的问题。 solve; //back; recursion(小规模); //go; } }下面实现的代码中并没有将基本操作定义成TreeNode的成员方法，其实想要封装好，将这些方法变成成员方法比较好。
二叉树的理解主要是递归概念的理解，二叉树是一种递归概念 还有一些二叉树的基本功能还没有实现，后序会更新。 1、通过先序遍历顺序来创建一颗二叉树 2、先序遍历、中序遍历和后序遍历（递归实现）、非递归方式实现这些遍历的会在后序补充更新。 3、计算二叉树的深度 4、计算二叉树的节点数 5、计算二叉树度数为1的节点数 6、计算二叉树的叶子节点 7、查找值为value的节点并且输出其左右子树
//TreeNode.h文件进行二叉树节点定义和函数声明 #pragma once #include<iostream> using namespace std; class TreeNode { public: char value;//节点的值 TreeNode* lTree;//左子树 TreeNode* rTree;//右子树 TreeNode(char value) { this->value = value; this->lTree = NULL; this->rTree = NULL; } }; //创建一个空树 TreeNode* creatNuTree(); //先序遍历的顺序建立二叉树 void creatBinTree(TreeNode* &root); //二叉树的先序遍历 void outTreeDLR(TreeNode* root); //二叉树的中序遍历 void outTreeLDR(TreeNode* root); //二叉树的后序遍历 void outTreeLRD(TreeNode* root); //二叉树的复制操作 void cloneTree(TreeNode* root, TreeNode* &newRoot); //计算二叉树的深度 int treeDepth(TreeNode* root); //计算二叉树的节点数量 int treeNodeNum(TreeNode* root); //计算二叉树的叶子节点的数量 int treeleNodeNum(TreeNode* root); //查找某个值为value的节点在不在二叉树中，如果在返回其左右子树,如果不在返回false bool search(TreeNode* root,char value); //计算二叉树的度数为1的节点数 int treeDegree_1(TreeNode* root); 函数实现文件 hanshu.cpp #include"TreeNode.h" #include<iostream> #include<Stack> using namespace std; //创建一个空树 TreeNode* creatNuTree() { TreeNode* binTree = new TreeNode(-1);//创建的树的根值默认为-1 return binTree; } //先序遍历的顺序建立二叉树 void creatBinTree(TreeNode* &root) { //先序遍历比较简单 char ch = '0'; cin >> ch; //递归停止的标志 if (ch == '#'){ //将根节点置空 root = NULL; return; } else{ root = new TreeNode(ch); //递归创建一个左子树 creatBinTree(root->lTree); //递归创建一个右子树 creatBinTree(root->rTree); } } //二叉树的先序遍历 void outTreeDLR(TreeNode* root) { //中序遍历可以通过递归的方式来实现或者非递归的方式来实现 if (root) { //递归按照LDR(中左右)的顺序进行实现 cout << root->value; outTreeDLR(root->lTree); outTreeDLR(root->rTree); } } //二叉树的中序遍历 void outTreeLDR(TreeNode* root) { //中序遍历可以通过递归的方式来实现或者非递归的方式来实现 if (root) { //递归按照LDR(中左右)的顺序进行实现 outTreeLDR(root->lTree); cout << root->value; outTreeLDR(root->rTree); } } //二叉树的后序遍历 void outTreeLRD(TreeNode* root) { //中序遍历可以通过递归的方式来实现或者非递归的方式来实现 if (root) { outTreeLRD(root->lTree); outTreeLRD(root->rTree); cout << root->value; } } //二叉树的复制操作 void cloneTree(TreeNode* root, TreeNode* &newRoot) { if (root == NULL) { newRoot = NULL; //递归结束标志 return; } else { newRoot = new TreeNode(root->value); cloneTree(root->lTree, newRoot->lTree); cloneTree(root->rTree, newRoot->rTree); } } //计算二叉树的深度 int treeDepth(TreeNode* root) { //二叉树的深度计算为：左子树或者右子树中深度比较大的加上1,通过递归的方式来计算 if (root == NULL) { return 0; } else { int lDepth = 0; lDepth = treeDepth(root->lTree); int rDepth = 0; rDepth = treeDepth(root->rTree); if (lDepth >= rDepth) { return lDepth + 1; } else { return rDepth + 1; } } } //计算二叉树的节点数量 int treeNodeNum(TreeNode* root) { //计算二叉树的节点数量，整棵树的节点数 == 左半边的节点数 + 右半边的节点数 if (root == NULL) { return 0; } else { int lnum = 0; lnum = treeNodeNum(root->lTree); int rnum = 0; rnum = treeNodeNum(root->rTree); return rnum + lnum + 1; } } //计算二叉树的叶子节点的数量 int treeleNodeNum(TreeNode* root) { //计算二叉树的叶子节点的数量 叶子节点 == 左子树的叶子节点 + 右子树的叶子节点 if (root == NULL) { return 0;//递归结束标志 } else { if (root->lTree == NULL && root->rTree == NULL) { return 1; } return treeleNodeNum(root->rTree) + treeleNodeNum(root->lTree); } } //查找某个值为value的节点在不在二叉树中，如果在返回其左右子树,如果不在返回false bool search(TreeNode* root, char value) { if (root == NULL) { return false; } else { if (root->value == value ) { if (root->lTree != NULL) { cout << root->lTree->value << endl;; } else { cout << "lTree is NULL" << endl; } if (root->rTree != NULL) { cout << root->rTree->value << endl;; } else { cout << "rTree is NULL" << endl; } return true; } return search(root->lTree, value) || search(root->rTree, value); } } //计算二叉树的度数为1的节点数 int treeDegree_1(TreeNode* root) { //二叉树的度 == 左子树的度 + 右子树的度 if (root == NULL) { return 0;//递归结束条件 } else { int num = 0; num = treeDegree_1(root->lTree) + treeDegree_1(root->rTree); if ((root->lTree == NULL && root->rTree != NULL) || (root->lTree != NULL && root->rTree == NULL)) { return num + 1; } else { return num; } } }数据结构菜鸟上路咯！
