预处理命令

#include #include #define TRUE 1#define FALSE 0typedef int elemtype;typedef struct tNode* tree;typedef struct tNode { elemtype elem; tree left; tree right;}tNode;

计算树的节点个数

//明确函数的功能：返回传入树的节点个数//定好尾头：尾：当传入的节点尾NULL时 头：1 + count(t->left) + count(t->right)int count(tree t){ if (t == NULL) return 0; return 1 + count(t->left) + count(t->right);}

求树中节点数据为num的节点个数

//明确函数功能：返回节点数据为num的节点个数//定好尾头：尾：NULL 头：1 + func(左) + func（右） // 或者 func(左) + func（右）int count_num(tree t, elemtype num){ if (t == NULL) return 0; else { if (t->elem == num) return 1 + count_num(t->left, num) + count_num(t->right, num); else return count_num(t->left, num) + count_num(t->right, num); }}

求树中节点数据的总和

//明确函数功能：返回总和//定好尾头：尾：NULL 头：root-> elem + func(左) + func（右）int add(tree t){ if (t == NULL) return 0; else return t->elem + add(t->left) + add(t->right);}

判断树中有无数据为num的节点

//两种方式：一种是可以达成目的就结束，一种是需要遍历完全才结束//明确函数功能：判断其中有没有值为num的节点返回1或0//定好尾头：尾：值为num ，头：int inTree_1(tree t, elemtype num){ if (t->elem == num) return TRUE; else { if (t->left != NULL) intree(t->left, num); // 使用递归将其递到子节点 if (t->right != NULL) intree(t->right, num); } return FALSE;}//确定函数功能：根据num的有无，返回0/非0//定好尾头：尾：NULL 头：有:return 1 + func(左)+func(右) 无：func(左)+func(右)int inTree_2(tree t, elemtype num){ if (t == NULL) return 0; int res; if (t->elem == num) res = 1+ intree(t->left, num) + intree(t->right, num);  if (t->elem == num) res = intree(t->left, num) + intree(t->right, num); return res;}

计算值为num的个数

int count_elem(tree t, elemtype val, int* num){ int val_l, val_r; if (t->left == NULL) return t->elem; if (t->right == NULL) return t->elem; else { val_l = count_elem(t->left, val, num); if (val == val_l) (*num)++; val_r = count_elem(t->right, val, num); if (val == val_r) (*num)++; return t->elem; } return *num;}

打印trunk

//明确函数功能：打印trunk//定好尾头 尾：NULL 头：第一步是判断本节点是否是树干然后打印，再func（左）去打印左边的树干 func（右）去打印右边的树干void print_trunk(tree t){ if (t == NULL) return; if (t->right != NULL || t->left != NULL) printf("%d", t->elem); print_trunk(t->right); print_trunk(t->left);}

判断两棵树是否一样

int same(tree t1, tree t2){ if (count(t1) == count(t2)) { if (t1->elem != t2->elem) return FALSE; if (t1->left != NULL && t2->left != NULL) same(t1->left, t2->left); if (t1->right != NULL && t2->right != NULL) same(t1->right, t2->right); return TRUE; } else return FALSE;}

求树的高度

#define max(x, y) (x > y) ? x : yint height(tree t){ if (t == NULL)return -1; return 1 + max(height(t->right), height(t->left));}

打印树中某值的层数

//明确函数功能：寻找放入的数的层数并打印//确定尾：//找到特定值的节点 找到NULL 头：若是则打印，若不是则去左右子树寻找layer++，当孩子寻找完都没有时layer--bool flag = false; //flag标记可以用于提前结束递归void getTreeLayer(Node * root, int num, int &layer){ if (root == NULL) return; if (flag == true) return; if (root->data == num) {  cout << "num值" << num << "的层数为：" << layer << endl;  flag = true;  return;  } layer++; getTreeLayer(root->lChild, num); getTreeLayer(root->rChild, num); layer--;}

求节点的路径

vector path;bool flag = false; //flag标记可以用于提前结束递归void getTreeLayer(Node * root, int num, int &layer){ if (root == NULL) return; if (flag == true) return; if (root->data == num) {  for(int x : path) cout << x << " "; bool flag = true; return; } path.push_back(); getTreeLayer(root->lChild, num); getTreeLayer(root->rChild, num); path.pop_back();}