1.二叉树的查找功能的时间复杂度比链表的好
2.删除节点的稍微复杂点
>没有节点，直接删除
>只有左节点（或者右节点），直接用该节点的左节点（或者右节点）替代要删除的节点
>有左节点并且有右节点，用左节点替代
3.二叉树的遍历方式：
/*
1．中序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵访问根结点；
⑶遍历右子树。[3]
2．先序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴ 访问根结点；
⑵ 遍历左子树；
⑶ 遍历右子树。
3．后序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵遍历右子树；
⑶访问根结点
*/
typedef struct node{ int num; struct node *left; struct node *right; }Node; typedef struct { Node *root; }Tree; /** *@brief 建树 */ Tree *createTree() { Tree *tree = malloc(sizeof(Tree)); tree -> root = NULL; return tree; } /** *@brief 建树的节点 */ Node *createNode(int num) { Node *node = malloc(sizeof(Node)); node -> num = num; node -> left = NULL; node -> right = NULL; return node; } /** *@brief 非递归插入 */ void insert(Tree *tree,int n) { if(tree -> root == NULL){ tree -> root = createNode(n); }else{ Node *p = tree -> root; Node *parent = NULL; while(p != NULL) { parent = p; // 记录当前移动的位置 if(p -> num < n) { p = p -> left; } else if(p -> num > n) { p = p -> right; } else{ // 相等就不再插入 return; } } // 找到位置后插入 if (n < parent -> num) { parent -> left = createNode(n); }else{ parent -> right = createNode(n); } } } /** *@brief 递归插入 */ void insert(Node *node,int n) { if(node == NULL){ node = createNode(n); } else if(n < node-> num){ node -> left = insert(node -> left, n); } else{ node -> right = insert(node -> right, n); } } /** *@brief 查找 */ Node *search(Tree tree,int n) { Node *p = tree -> root; while(p != NULL) { if(n < p -> num) { p = p -> left; } else if (n > p -> num) { p = p -> right; } else { return p; } } return NULL; } /* 1．中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： ⑴遍历左子树； ⑵访问根结点； ⑶遍历右子树。[3] 2．先序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： ⑴ 访问根结点； ⑵ 遍历左子树； ⑶ 遍历右子树。 3．后序遍历得递归算法定义： 若二叉树非空，则依次执行如下操作： ⑴遍历左子树； ⑵遍历右子树； ⑶访问根结点 */ /** *@brief 先序遍历 *@param node tree->root */ void preOrder(Node *node) { if (node != NULL) { printf("%d",node -> num); preOrder(node -> left); preOrder(node -> right); } } /** *@brief 中序遍历 */ void inOrder(Node *node) { if (node != NULL) { inOrder(node -> left); printf("%d",node -> num); inOrder(node -> right); } } /** *@brief 后序遍历 */ void tailOrder(Node *node) { if (node != NULL) { tailOrder(node -> left); tailOrder(node -> right); printf("%d",node -> num); } } /** *@brief 删除节点
1//只有左节点，则左节点代替他的位置
2//只有右节点，则右节点代替他的位置
3//既有左节点又有右节点，则左子树的最右节点代替原节点 */ bool deleteNode(Node *node,int n) { Node *p = node; Node *q; int temp; while(p != NULL && n != p -> num) { q = p; if(p -> num < n) { p = p -> left; } else if(p -> num > n) { p = p -> right; } else{ // 相等就不再插入 } } if(p == NULL){ printf("没有此元素"); } else{ // 如果找到要删除的节点 // 1.如果找到的节点，没有左子树和右子树 if(p -> left == NULL && P -> right == NULL) { if(p == q -> left) { q -> left = NULL; } if(p == q -> right) { q -> right = NULL; } free(p); p == NULL; } // 2.找到节点，但是要删除的节点只有左子树或者右子树 // 2.1 只有左子树 else if (NULL == p -> right && NULL != p -> left) { if(p == q ->left) { q -> left = p -> left; }else if(p == q -> right) { q ->right = p -> left; } free(p); p = NULL; } // 2.2 只有右子树 else if (NULL != p -> right && NULL == p -> left) { if(p == q ->left) { q -> left = p -> right; }else if(p == q ->right) { q ->right = p -> right; } free(p); p = NULL; } // 3.如果查找到的节点，左右子树都有(本代码使用直接前驱，也可以使用直接后继) else if (NULL != P -> right && NULL != p -> left) { Node *s,sParent; sParent = p; s = sParent -> left; while (NULL != s -> right) // 找到p的直接前驱 { sParent = s; s = s -> right; } temp = s -> num; deleteNode(node,temp); // 递归 p -> num = temp; } } }