二叉树的性质
为底，n+1为对数)
1 .若i>0，i位置结点的双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
2 .若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3 . 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
二叉树的接口和具体形式
//创建新节点
TreeNode* createNode(int value);
// 插入节点（递归）
TreeNode* insert(TreeNode* root, int value);
// 查找节点
TreeNode* search(TreeNode* root, int value);
// 前序遍历
void preorder(TreeNode* root);
// 中序遍历
void inorder(TreeNode* root);
// 后序遍历
void postorder(TreeNode* root);
// 删除节点
TreeNode* delete(TreeNode* root, int value);
// 销毁整棵树
void destroyTree(TreeNode* root);
基本代码如下
// 创建新节点
TreeNode* createNode(int value) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = value;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点（递归）
TreeNode* insert(TreeNode* root, int value) {
if (root == NULL)
return createNode(value);
if (value < root->val)
root->left = insert(root->left, value);
else if (value > root->val)
root->right = insert(root->right, value);
// 如果等于则什么也不做（不允许重复） 也就是直接返回了
return root;
}
// 查找节点
TreeNode* search(TreeNode* root, int value) {
if (root == NULL || root->val == value)
return root;
if (value < root->val)
return search(root->left, value);
else
return search(root->right, value);
}
// 前序遍历
void preorder(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->val);
preorder(root->left);
preorder(root->right);
}
// 中序遍历
void inorder(TreeNode* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
// 后序遍历
void postorder(TreeNode* root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->val);
}
// 删除节点
TreeNode* delete(TreeNode* root, int value) {
if (root == NULL)
return root;
if (value < root->val)
root->left = delete(root->left, value);
else if (value > root->val)
root->right = delete(root->right, value);
else { // 找到要删除的节点
if (root->left == NULL) {
TreeNode* tmp = root->right;
free(root);
return tmp;
}
else if (root->right == NULL) {
TreeNode* tmp = root->left;
free(root);
return tmp;
}
else {
// 找右子树最小节点
TreeNode* tmp = root->right;
while (tmp->left != NULL)
tmp = tmp->left;
root->val = tmp->val;
root->right = delete(root->right, tmp->val);
}
}
return root;
}
// 销毁整棵树
void destroyTree(TreeNode* root) {
if (root == NULL)
return;
destroyTree(root->left);
destroyTree(root->right);
free(root);
}
对应各个接口
另外有一种给出中序和前序的形式推断二叉树的形式
如前序 1 2 3 4 5 7 6
中序 3 2 1 5 7 4 6
结合两个排序来排出二叉树
从前序根->左->右的遍历顺序
可以得出根为1
以1为界限可以从中序得出左右子树
而后以中序 左->根->右 的顺序进一步推断
总结:二叉树中大量使用了 递归 的方法,而递归的关键就是:
明确函数意义：先定义清楚这个递归函数到底要解决什么问题，返回值代表什么。
找到终止条件：确定问题规模缩小到什么程度时，可以直接给出答案，不再递归。
建立递推关系：思考如何用子问题的结果，组合出当前问题的答案。
