1.概念
二叉树以一个根节点为出发点，每个节点均遵循如下规则：该节点可以有一个左子节点，一个右子节点，且每个节点的值需大于其左子节点值，同时小于其右子节点值。
2.待实现功能列表
（1）添加节点：
实现思路：从根节点开始遍历，直至找到一个节点满足如下任一条件：
1）节点值大于待添加值，且无左子节点；
2）节点值小于待添加值，且无右子节点。
（2）删除某个节点（不含子节点）；
实现思路：（注意处理删除根节点以及将树删空的情况）
1）若被删除节点无子节点，则断开父节点到该节点的指向，释放节点资源，返回；
2）若被删除节点有左子节点，则找到其左子树中的最大值节点，暂存该最大值，删除该最大值左子节点，用暂存的值覆盖原本要删除的节点值，返回；
3）若被删除节点有右子节点，则找到其右子树中的最小值节点，暂存该最小值，删除该最小值右子节点，用暂存的值覆盖原本要删除的节点值，返回。
（3）升序遍历；
实现思路：从根节点开始递归，首先遍历左子节点，无左子节点后，输出该节点值，若该节点有右子节点，则调用同样方法递归其右子节点。
（4）二叉树转双向链表，不能额外申请内存空间（据说是一道微软面试题）；
实现思路：主要依据升序遍历的思路，额外记录上一次输出的节点，用于与下一次输出的节点进行链表关联。
3.二叉树节点数据结构
struct node{ int val; struct node *left; struct node *right; };
4.具体实现
#include <stdio.h> #include <stdlib.h>
//二叉树节点数据结构 struct node{ int val; struct node *left; struct node *right; }; //添加节点 void add(struct node* root,int val){ if(val < root->val){ if(root->left != NULL){ add(root->left,val); }else{ struct node *pleft = (struct node*)malloc(sizeof(struct node)); pleft->val = val; root->left = pleft; } }else{ if(root->right != NULL){ add(root->right,val); }else{ struct node *pright = (struct node*)malloc(sizeof(struct node)); pright->val = val; root->right = pright; } } } //获得最小值子节点 struct node *getMin(struct node *pnode){ if(pnode->left != NULL){ return getMin(pnode->left); } return pnode; }
//获得最大值子节点 struct node *getMax(struct node* pnode){ if(pnode->right != NULL){ return getMax(pnode->right); } return pnode; } //获得父节点 struct node* getParent(struct node *root,struct node *pnode){ if(root->left == pnode || root->right == pnode){ return root; } if(root->val > pnode->val){ return getParent(root->left,pnode); }else{ return getParent(root->right,pnode); } }
//根据数值找到节点 struct node* getNode(struct node* root,int val){ if(root->val == val){ return root; } if(root->val > val){ return getNode(root->left,val); }else{ return getNode(root->right,val); } }
//删除某个节点 struct node* delNode(struct node* root,struct node* pnode){ struct node* parent; if(root != pnode){ parent = getParent(root,pnode); } if(pnode->left == NULL && pnode->right == NULL){ if(parent == NULL){ free(pnode); return NULL; } if(parent->left == pnode){ parent->left = NULL; free(pnode); return root; } if(parent->right == pnode){ parent->right = NULL; free(pnode); return root; } } if(pnode->left != NULL){ struct node *pmax = getMax(pnode->left);
//此处暂存该数值，删除该子节点后再进行数值替换 int tmpVal = pmax->val; delNode(pnode,pmax); pnode->val = tmpVal; return root; } if(pnode->right != NULL){ struct node *pmin = getMin(pnode->right); int tmpVal = pmin->val; delNode(pnode,pmin); pnode->val = tmpVal; return root; } }
//指定要删除的节点值 struct node* del(struct node* root,int val){ struct node* pnode = getNode(root,val); if(pnode == NULL){ return root; } return delNode(root,pnode); }
//升序遍历输出二叉树void printTree(struct node *root){ if(root->left != NULL){ printTree(root->left); } printf("%6d",root->val); if(root->right != NULL){ printTree(root->right); } }
//二叉树转链表时临时记录上一次被关联的节点 struct node *pre;
//二叉树转双向链表 void tree2link(struct node* root){ if(root->left != NULL){ tree2link(root->left); } if(pre == NULL){ pre = root; }else{ pre->right = root; root->left = pre; pre = root; } if(root->right != NULL){ tree2link(root->right); } }
//遍历转换后的双向链表 void printLink(struct node* start){ while(start->left != NULL){ start = start->left; } while(start != NULL){ printf("%6d",start->val); start = start->right; } }
//释放二叉树申请的内存空间 void freeTree(struct node* root){ if(root->left != NULL){ freeTree(root->left); } if(root->right != NULL){ free(root); freeTree(root->right); }else{ free(root); } }
//释放二叉树转换的双向链表占用的内存空间 void freeLink(struct node* start){ while(start->left != NULL){ start = start->left; } while(start != NULL){ struct node *tmp = start->right; free(start); start = tmp; tmp = NULL; } } int main(int argc,char *argv){ struct node* root = (struct node*)malloc(sizeof(struct node)); root->val = 65; int i,count=10; int arr[10] = {7,45,34,23,11,78,89,56,90,88}; for(i = 0; i < count; ++i){ add(root,arr[i]); } printTree(root); printf(" "); //tree2link(root); //pre = NULL; //printLink(root); //printf(" "); //freeLink(root);//注意：二叉树转换成双向链表后需调用此方法释放内存 printf("input a number to delete:"); int delval; scanf("%d",&delval); root = del(root,delval); printTree(root); printf(" "); freeTree(root); }