本次用了一个文件
#include<bits/stdc++.h>
using namespace std;typedef struct TreeNode
{struct TreeNode* left;struct TreeNode* right;int val;
}BTNode;//手搓一棵树
BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->val = val;newnode->right = NULL;newnode->left = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;
}// 前中后序
void PreOrder(BTNode* root)
{if (root == NULL){cout << "N";return;}cout << root->val;PreOrder(root->left);PreOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){cout << "N";return;}InOrder(root->left);cout << root->val;InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){cout << "N";return;}PostOrder(root->left);PostOrder(root->right);cout << root->val;
}//有线程安全的风险，有可能多个线程都在调用这个变量
//int size = 0;//但是在每次调用前都需要赋值为0//void TreeSize(BTNode* root, int* psize)
//{
// //static int size = 0;//静态变量存在静态区，不会随函数结束而被销毁。但是！！！静态变量只会被初始化一次！！！多次调用就会出现问题
// if (root == NULL)
// return ;
// else
// ++(*psize);
//
// TreeSize(root->left , psize);
// TreeSize(root->right , psize);
//}//分治法
int TreeSize(BTNode* root)
{return root == NULL ? 0 :TreeSize(root->left)+ TreeSize(root->right)+1;//1是指自己，根节点
}int maxDepth(BTNode* root)
{if (root == NULL)return 0;int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//时间复杂度是O(N)注意尽量不要在三目运算符中使用多层次递归调用//return maxDepth(root->left) > maxDepth(root->right) ? maxDepth(root->left) + 1 :maxDepth(root->right) + 1;//以上的写法，没有记录的话，在每层比较时都需要向下层询问出现二次调用，递归等比数列，公比是叉数，时间复杂度是O(2^N)
}int TreeHeight(BTNode* root)
{return maxDepth(root);
}//二叉树第k层的节点个数
int TreeKLever(BTNode* root,int k)
{assert(k);if (root == NULL)return 0;if (k == 1)return 1;//不为空,且k>1说明第k层的节点在子树里面，转换成子问题求解return TreeKLever(root->left, k - 1) + TreeKLever(root->right, k - 1);
}//查找x所在的节点
BTNode* TreeFind(BTNode* root, int x)
{if (root == NULL)return NULL;if (root->val==x)return root;BTNode* ret1 = TreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = TreeFind(root->right, x);if (ret2)return ret2;//也可以直接返回ret2//return TreeFind(root->right, x);return NULL;
}int main()
{BTNode* root = CreateTree();PreOrder(root);cout << endl;InOrder(root);cout << endl;PostOrder(root);cout << endl;/*int size = 0;TreeSize(root, &size);cout << size;*/cout << TreeSize(root);return 0;
}
