关于二叉树的题
复制二叉树
【算法步骤】
如果是空树，递归结束，否则执行以下操作：
●申请一个新结点空间，复制根结点。
●递归复制左子数。
●递归复制右子数。
【算法描述】
1 //复制二叉树(递归) 2 void Copy(BiTree T, BiTree &NewT) 3 {//复制一颗和T完全相同的二叉树 4 if(T == NULL)//如果是空数，递归结束 5 { 6 NewT = NULL; 7 return; 8 } 9 else 10 { 11 NewT = new BiTNode; 12 NewT->data = T->data;//复制根节点 13 Copy(T->lchild, NewT->lchild);//递归复制左指数 14 Copy(T->rchild, NewT->rchild);//递归复制右指数 15 }//else 16 }
计算二叉树的深度。
【算法步骤】
如果是空树，递归结束，否则执行以下操作：
●递归计算左子数的深度记为m。
●递归计算右子数的深度记为n。
●如果m大于n，二叉树的深度为m+1，否则为n+1。
【算法描述】
1 //计算二叉树的深度 2 int Depth(BiTree T) 3 {//计算二叉树T的深度 4 int m,n; 5 if(T == NULL)return 0;//如果是空数，深度为0，递归结束 6 else 7 { 8 m = Depth(T->lchild);//递归计算左指数的深度计为m 9 n = Depth(T->rchild);//递归计算右指数的深度计为n 10 if(m>n) return(m+1);//二叉树的深度为m与n的较大者加1 11 else return n+1; 12 }//else 13 14 }
统计二叉树中结点个数。
【算法步骤】
如果是空数，则结点个数为0；否则，结点个数为左子数的节点个数加上右子数的节点个数在加1。
【算法描述】
1 //统计二叉树中节点的个数 2 int NodeCount(BiTree T) 3 {//统计二叉树中节点T的个数 4 if(T == NULL) return 0;//如果是空数，则节点个数为0，递归结束 5 else return NodeCount(T->lchild) + NodeCount(T->rchild) +1;//否则节点个数为左子数的节点个数+右子数的节点个数+1 6 7 }
统计二叉树的叶节点个数。
【算法思想】
利用递归实现，递归结束的条件有两个：一个是二叉树为空，另一个是遇到叶子节点。当二叉树为空时，递归结束返回0；当二叉树不为空，且左、右子树为空（页子结点）时，递归结束返回1；
当二叉树不为空，且左、右子树不同时为空（非叶子节点），递归调用统计函数，返回左子树中叶子节点个数加上右子树中叶子节点个数。
【算法描述】
1 int LeafNode(BiTree T) 2 {//统计二叉树T中叶子节点个数 3 if(T == NULL)//空数返回0 4 return 0; 5 else if(T->lchild == NULL && T->rchild == NULL)//叶子节点返回1 6 return 1; 7 else //递归 8 return LeafNode(T->lchild)+LeafNode(T->rchild); 9 }
判断两颗树是否相等。
【算法思想】
利用递归实现，递归结束条件有3个：一是两棵树均为空，返回相等；二是只有一棵树为空，返回不等；三是结点数据域不等，返回不等。其他情况下则递归判断相应的孩子节点是否相等。
【算法描述】
1 bool CmpTree(BiTree T1, BiTree T2) 2 {//判断两颗二叉树是否相等 3 if(T1 == NULL && T2 == NULL)//都为NULL，相等 4 return true; 5 else if(T1 == NULL || T2 == NULL)//只有一个为NULL,不等 6 return false; 7 else if(T1->data != T2->data)//跟结点不相等，直接返回不等否则递归结束 8 return false; 9 else return CmpTree(T1->lchild, T2->lchild)&&CmpTree(T1->rchild, T2->rchild); 10 11 }
交换二叉树每个节点的左孩子和右孩子
【算法思想】
如果某节点的左、右子树有一个为空，则返回，否则交换该结点的左、右孩子节点，然后递归交换左、右子树。
【算法描述】
1 void ChangeLR(BiTree &T) 2 {//交换二叉树每个节点的左孩子和右孩子 3 4 if(T->lchild == NULL || T->rchild == NULL)//左右孩子有一个为空返回 5 return; 6 else//交换左右孩子节点 7 { 8 9 //直接交换指针 10 BiTree temp = T->lchild; 11 T->lchild = T->rchild; 12 T->rchild = temp; 13 14 }//递归 15 ChangeLR(T->lchild); 16 ChangeLR(T->rchild); 17 18 }
这个是另一种交换方法（不满足题意）
1 void ChangeLR(BiTree &T) 2 {//交换二叉树每个节点的左孩子和右孩子 3 4 if(T->lchild == NULL || T->rchild == NULL)//左右孩子有一个为空返回 5 return; 6 else//交换左右孩子节点 7 { 8 9 10 //交换左右值 11 BiTree p, q; 12 ElemType temp; 13 p = T->lchild; 14 q = T->rchild; 15 temp = p->data; 16 p->data = q->data; 17 q->data = temp; 18 19 }//递归 20 ChangeLR(T->lchild); 21 ChangeLR(T->rchild); 22 23 }
设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。
【算法思想】
双序遍历与先序遍历相比，只是多了一次访问，即在递归遍历其左子树后再访问一次该结点。
因此，
步骤如下:
若二叉树为空，则空操作;否则：
(1)访问根结点;
(2)先序遍历左子树;
(3)访问根结点;
(4)先序遍历右子树。
【算法描述】
1 void DoubleTraverse(BiTree T) 2 {//双序遍历二叉树T的递归算法 3 if(T)//若二叉树非空 4 { 5 cout<<T->data<<ends;//访问根节点 6 DoubleTraverse(T->lchild);//双序遍历左子数 7 cout<<T->data<<ends;//访问根节点 8 DoubleTraverse(T->rchild);//双序遍历右子数 9 } 10 }
计算二叉树最大的宽度(二叉树的最大宽度是指二义树所有层中结点个数的最大值)。
【算法思想】
计算二叉树最大的宽度可采用层次遍历的方法，利用队列来实现。首先判断是否为空树，如果为空树则宽度为0;不为空则分别记录局部的宽度和当前的最大宽度，逐层遍历结点，如果结点有孩子结点，则将其孩子加人队尾;每层遍历完毕之后，若局部宽度大于当前的最大宽度，则修改最大宽度。
【算法描述】
1 int Width(BiTree T) 2 {//求二叉树T的最大宽度 3 if(T == NULL)//如果数为空宽度为零 4 return 0; 5 else 6 { 7 BiTree p; 8 BiTree Q[10000];//Q是队列，元素为二叉数结点指针，容量足够大 9 int front = 1;//队头指针 10 int rear = 1;//队尾指针 11 int last = 1;//同层最后结点的位置 12 int maxW = 0;//最大宽度 13 int temp = 0;//局部宽度 14 15 Q[rear] = T; 16 while(front <= last) 17 { 18 p = Q[front++]; 19 temp++; 20 21 if(p->lchild != NULL)//左子数入队 22 Q[++rear] = p->lchild; 23 if(p->rchild != NULL)//右子数入队 24 Q[++rear] = p->rchild;//一层结束 25 26 if(front > last) 27 { 28 last = rear; 29 if(temp > maxW) 30 maxW = temp; 31 temp = 0; 32 }//if 33 34 }//while 35 36 return maxW; 37 38 } 39 40 }
用按层次顺序遍历又树的方法， 统计树中度为I的结点数目。
【算法思想】
可以借助队列实现层次顺序遍历二叉树。从根结点开始，首先将结点进队，然后依次访问队列中的结点，访问之后将其出队。若该结点左子树为空、右子树非空或者右子树为空、左子树非空，则该结点为度为1的结点，计数加1,并将该结点的非空孩子结点人队，直到队列为空则统计结束。
【算法描述】
1 int Level(BiTree T) 2 {//层次遍历二叉树，并统计树中度为1的结点的个数 3 cout<<endl<<endl<<"用按层次遍历二叉树的方法，统计树中度为1的结点数目:"<<endl; 4 int count = 0;//count为树中度为1的结点数目 5 if(T) 6 { 7 queue<BiTree> s; 8 BiTree p; 9 BiTree q; 10 11 p = T; 12 s.push(p);//将根节点入队 13 while(!s.empty()) 14 { 15 p = s.front(); //p出队访问结点 16 s.pop(); 17 cout<<p->data<<ends;//访问出队的结点 18 19 if( (p->lchild && !p->rchild) || ( !p->lchild && p->rchild ) ) 20 count++; 21 22 if(p->lchild != NULL)//如果左节点不为空 左节点入队 23 { 24 q = p->lchild; 25 s.push(q); 26 27 } 28 if(p->rchild != NULL)//如果右节点不为空 左节点入队 29 { 30 q = p->rchild; 31 s.push(q); 32 33 } 34 35 36 } 37 38 } 39 return count; 40 41 }