关于二叉树的题
复制二叉树
【算法步骤】
如果是空树，递归结束，否则执行以下操作：
●申请一个新结点空间，复制根结点。
●递归复制左子数。
●递归复制右子数。
【算法描述】
- 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 }