1、存储结构
//---指针 struct node{ int data; //数据域 int layer; //层次 node* lchild; //指向左子树根结点的指针 node* rchild; //指向右子树根结点的指针 }; //---数组 #define maxn 100 struct node{ int data; int lchild; int rchild; }Node[maxn];
2、新建结点
//---指针 node* newNode(int v) { node* Node=new node; //申请node型变量地址空间 Node->data=v; Node->lchild=Node->rchild=NULL; return Node; //返回新建结点的地址 } //---数组 int index=0; int newNode(int v) { Node[index].data=v; Node[index].lchild=-1; Node[index].rchild=-1; return index++; }
3、结点查找
3.1 二叉树结点查找
//---指针 void search(node* root,int x,int newdata) { if(root==NULL) return; //空树，递归边界 if(root->data==x) root->data=newdata; search(root->lchild,x,newdata); //递归往左子树搜索 search(root->rchild,x,newdata); //递归王右子树搜索 } //---数组 void search(int root,int x,int newdata) { if(root==-1) return; //用-1替代NULL if(Node[root].data==x) Node[root].data=newdata; search(Node[root].lchild,x,newdata); //往左子树搜索，递归 search(Node[root].rchild,x,newdata); //往右子树搜索，递归 }
3.2 二叉排序树结点查找
//1.查找操作 //最坏复杂度是O(h) //search函数查找二叉查找树中数据域为x的结点 //数据域顺序为左子树<根结点<右子树 void search(node* root,int x) { if(root==NULL){ printf("search failed! "); return; } if(x==root->data){ printf("%d ",root->data); }else if(x<root->data){ search(root->lchild,x); }else{ search(root->rchild,x); } }
4、结点插入
4.1 二叉树结点插入
//insert函数在二叉树中插入一个数据域为x的新结点 //根结点指针root要使用引用，否则插入不成功 //---指针 void insert(node* &root,int x) { if(root==NULL){ root=newNode(x); return; } if(...){ insert(root->lchild,x); }else{ insert(root->rchild,x); } } //---数组 //root为根结点在数组中的下标 void insert(int &root,int x) //要加引用 { if(root==-1){ rot=newNode(x); return; } if(...){ insert(Node[root].lchild,x); }else{ insert(Node[root].rchild,x); } }
4.2 二叉排序树结点插入
//2.插入操作 //insert函数将在二叉树中插入一个数据域为x的新结点，参数root需要加引用& void insert(node* &root,int x) { if(root==NULL) { //空树，说明查找失败，也即插入位置 root=newNode(x); return; } if(x==root->data){ //查找成功，说明结点已存在，直接返回 return; }else if(x<root->data){ insert(root->lchild,x); //往左子树搜索x }else{ insert(root->rchild,x); } }
5、树的创建
//---指针 node* Create(int data[],int n) { node* root=NULL; //根结点地址设为空 for(int i=0;i<n;i++){ insert(root,data[i]); } return root; } //---数组 int Create(int data[],int n) { int root=-1; //新建根结点 for(int i=0;i<n;i++) { insert(root,data[i]); } return root; //返回二叉树的根结点下标 }
/* root=NULL和*root=NULL区别 遍历到子树时，若子树为空，则子树不存在根结点，此时root自然为空，即root=NULL; *root是指获取地址root指向的空间的内容，但无法说明地址root是否为空 即结点地址为NULL与结点内容为NULL区别，也相当于结点不存在与结点存在但没有内容的区别 */
6.结点删除
6.1 二叉查找树结点删除
什么是前驱和后继？
//前驱：比结点权值小的最大结点称为该结点的前驱 //即从左子树根结点开始不断沿着rchild往下直到rchild为NULL时的结点 //寻找以root为根结点的树中的最大权值结点 node* findMax(node* root) { while(root->rchild!=NULL) root=root->rchild; //不断往右，直到没有右孩子 return root; } //后继：比结点权值大的最小结点为该结点的后继 //即从右子树根结点不断沿着lchild往下直到lchild为NULL时的结点 //寻找以root为根结点的树中最小权值结点 node* findMin(node* root) { while(root->lchild!=NULL) { root=root->lchild; //不断往左，直到没有左孩子 } return root; }
删除操作的基本思路？
①如果当前结点root为空，说明不存在权值为给定权值x的结点，直接返回
②如果当前权值root的权值恰为给定的权值x,说明找到了想要删除的结点，此时进入删除处理
a)如果当前结点root不存在左右孩子，说明是叶子结点，直接删除。
b)如果当前结点root存在左孩子，则在左子树中寻找结点前驱pre,然后让pre的数据覆盖root,
接着在左子树中删除结点pre
c)如果当前结点root存在右孩子，则在右孩子中寻找结点后继next，让next的数据覆盖root,
接着在右子树中删除结点next
③若当前结点的权值大于给定的权值x,则在左子树中递归删除权值为x的结点。
④若当前结点root的权值小于给定的权值x,则在右子树中递归删除权值为x的结点。
二叉排序树删除某结点的代码怎么写？
void deleteNode(node* &root,int x) { if(root==NULL) return; if(root->data==x) //找到数据域为x的结点 { if(root->lchild==NULL && root->rchild==NULL) { root=NULL; //把root地址设为NULL,父结点就无法引用它 }else if(root->lchild!=NULL) //如果左子树不为空，则用该结点的前驱替代 { node* pre=findMax(root->lchild); root->data=pre->data; //将其前驱结点数据域赋值给它 deleteNode(root->lchild,pre->data); //在左子树中删除结点pre }else{ node*next=findMin(root->rchild); root->data=next->data; deleteNode(root->rchild,next->data); //在右子树中删除结点next } }else if(root->data>x) { deleteNode(root->lchild,x); //在左子树中删除x }else{ deleteNode(root->rchild,x); //在右子树中删除x } } node* findMax(node* root) { while(root->rchild!=NULL) { root=root->rchild; } return root; } node* finMin(node* root) { while(root->lchild!=NULL) { root=root->lchild; } return root; }