关于二叉树的递归规律微总结

[bosthhe1]

在二叉树的遍历中，经常会用到递归，但是递归的方法，总是想的不是很透彻，看到一个二叉树的题总是没有递归头绪，下面我们将二叉树的递归遍历分为三种模式，但是不管什么模式，都需要写p==nullptr(不管是对于递归的条件是否需要递归到nullptr的那一层，p==nullptr都需要写) 1，不带返回值的 2，带返回值 3，不带返回值但是带数据的

[bosthhe1]

关于第一种不带返回值的，分为自己建树和他人建树，自己建树和他人建树的区别在于，顾名思义，自己建树和他人给树，自己建树容易，但是他人建树怎么理解呢，他人建树是通过特定的树的规律，来达到建树的目的，比如说告诉你该树为前序，且告诉你树的遍历节点，让你把树构建出来，并写出树的中序，这里面树的遍历节点一般为通过数组表示，空节点一般用 ' # ' ，如 char a[13] = { 'a', 'b', 'd', '#', '#', 'e', '#', '#', 'c', 'f', '#', '#', '#' };将以上看作前序的树，‘#’代表空，求树的中序，求树的中序，就需要将树构造出来

[bosthhe1]

构造树，因为树的形式为前序，需要构造树，需要将树拆分为左子树和右子树来分别构造，所以会产生左子树和右子树来接受不同的节点，又因为需要将树连接起来，所以会将将树的节点，返回回去，和上一个节点链接 typedef struct Tree { char a; Tree left; Tree right; }Tree; Tree Test1Head(char a, int i) { if (a[i] == '#') { a[i] = NULL; ( i)++;//继续像后面遍历 return NULL; } Tree ps = (Tree )malloc(sizeof(Tree)); ps->a = a[i]; ( i)++;//继续像后面遍历 ps->left = Test1Head(a, i);//接受返回的节点 ps->right = Test1Head(a, i); return ps; } void TestMod(Tree a) { if (a == NULL) { return NULL; } TestMod(a->left); printf("%c ", a->a); TestMod(a->right); } void TestTree() { char a[13] = { 'a', 'b', 'd', '#', '#', 'e', '#', '#', 'c', 'f', '#', '#', '#' }; int i = 0; Tree * p = Test1Head(a, &i); TestMod(p); }

[bosthhe1]

带返回值,带返回值的会分为2种情况，是分开遍历还是一起遍历，分开遍历的思想和上面的建树的差不多，需要将左子树和右子树分开遍历，一般是计算树的高度的情况，一起遍历就不用将左子树和右子树分开遍历，可以同时进行，一般用于计算节点的数量 int NumTreeNode(Tree p)//求树的节点 { if (p == NULL) { return 0; } return NumTreeNode(p->left) + NumTreeNode(p->right) + 1;//这里求树的所有节点，可以合起来一起求节点，不用分开求 } int NumLeafNode(Tree p)//求树的叶子节点 { if (p == NULL)//当一端为空的时候直接返回 { return 0; } if (p->left == NULL&&p->right == NULL)//当左子树和右子树同时为空的时候才为叶子节点，才返回1 { return 1; } return NumLeafNode(p->left) + NumLeafNode(p->right);//分治管理下去 } int NumTreeHigh(Tree p)//这里需要求树的高度，树的高度是由最深的跟来决定的，要求树的高度，就必须要将左子树的高度和右子树的高度分别求出来，然后比较，选出最大的值，及为树的高度 { if (p == NULL) { return 0; } int left = NumTreeHigh(p->left);//将返回值保留，然后在比较 int right = NumTreeHigh(p->right); return left > right ? left + 1 : right + 1;//选出比较大的一个树，返回 } int NumTreeHigh1(Tree p) { if (p == NULL) { return 0; } return NumTreeHigh1(p->left) > NumTreeHigh1(p->right) ? NumTreeHigh1(p->left) + 1 : NumTreeHigh1(p->right) + 1;//这个也是选出树的高度，但是这个会遍历很多次，存在栈溢出的情况，因为他每一次比较晚，都没有将返回值保留，而是再次去遍历树。 } int NumTreeKNode(Tree * p, int k)//第k层节点的个数 { if (p == NULL)//当p还没到k时，就结束了，返回0 { return 0; } if (k == 1)//当k为1时，说明已经走到了K层的节点，返回1 { return 1; } return NumTreeKNode(p->left, k - 1) + NumTreeKNode(p->right, k - 1);//遍历左子树，遍历右子树，当深度达到k，且有节点的情况下，返回1，反之返回0； }