《数据结构》—— 二叉树的复制、查深度与算结点操作

二叉树的操作

• • 一、二叉树的复制
  • 二、计算二叉树的深度
  • 三、计算二叉树的结点

一、二叉树的复制

已经创建好的二叉树，首先我们对它进行判空操作，再创建新的根结点 NewT，把根结点T 赋给 NewT，递归复制左(右)子树。

// 一、复制二叉树
void Copy(BiTree T, BiTree &NewT)
{if(T==NULL ){   //如果是空树，递归结束NewT=NULL;return;}else{NewT = new BiTNode;NewT->data = T->data;			//复制根结点Copy(T->lchild, NewT->lchild);  //递归复制左子树Copy(T->rchild, NewT->rchild);  //递归复制右子树}
}

二、计算二叉树的深度

【分析】：1、树为空则深度为0；2、否则递归计算左(右)子树的深度；3、取子树最大的深度，再加1。

// 二、计算二叉树的深度
int Depth(BiTree T){int m,n;if(T== NULL)return 0;  //如果是空树，深度为0，递归结束else {m=Depth(T->lchild);	  //递归计算左子树的深度记为mn=Depth(T->rchild);	  //递归计算右子树的深度记为nif(m>n)return(m+1);  //二叉树的深度为m 与n的较大者加1elsereturn (n+1);}
}

三、计算二叉树的结点

开始也是判空，否则结点个数为左子树的结点个数+右子树的结点个数+1。

// 三、计算二叉树的结点
int NodeCount(BiTree T){if(T==NULL) return 0;  			// 如果是空树，则结点个数为0，递归结束else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;//否则结点个数为左子树的结点个数+右子树的结点个数+1
}

完整代码如下：

#include<iostream>
using namespace std;// 二叉树的二叉链表存储表示
typedef struct BiNode{char data;						//结点数据域struct BiNode *lchild, *rchild;	//左右孩子指针
}BiTNode, *BiTree;// 先序建立二叉链表
void CreateBiTree(BiTree &T){// 按先序次序输入二叉树中结点的值(一个字符)，创建二叉链表表示的二叉树Tchar ch;cin >> ch;      //输入先序序列if(ch=='#')T=NULL;		//递归结束，建空树else{T=new BiTNode;CreateBiTree(T->lchild);	//递归创建左子树T->data=ch;					//生成根结点CreateBiTree(T->rchild);	//递归创建右子树}
}/*
T->data=ch;					//生成根结点
CreateBiTree(T->lchild);	//递归创建左子树
CreateBiTree(T->rchild);	//递归创建右子树可以把根左右顺序换成，中序：左根右；后序：左右根，来输入
*/								//CreateBiTree// 一、复制二叉树
void Copy(BiTree T, BiTree &NewT)
{if(T==NULL ){   //如果是空树，递归结束NewT=NULL;return;}else{NewT = new BiTNode;NewT->data = T->data;			//复制根结点Copy(T->lchild, NewT->lchild);  //递归复制左子树Copy(T->rchild, NewT->rchild);  //递归复制右子树}
}// 二、计算二叉树的深度
int Depth(BiTree T){int m,n;if(T== NULL)return 0;  //如果是空树，深度为0，递归结束else {m=Depth(T->lchild);	  //递归计算左子树的深度记为mn=Depth(T->rchild);	  //递归计算右子树的深度记为nif(m>n)return(m+1);  //二叉树的深度为m 与n的较大者加1elsereturn (n+1);}
}// 三、计算二叉树的结点
int NodeCount(BiTree T){if(T==NULL) return 0;  			// 如果是空树，则结点个数为0，递归结束else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;//否则结点个数为左子树的结点个数+右子树的结点个数+1
}// 中序遍历的递归算法
void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);cout << T->data;InOrderTraverse(T->rchild);}
}int main()
{BiTree tree,new_tree;cout<<"二叉链表的序列(先序输入) 例如：ABD##E##CF###：\n";CreateBiTree(tree);Copy(tree,new_tree);cout<<"复制得到的新树的中序序列：";InOrderTraverse(new_tree);cout<<endl;cout<<"二叉树的深度为："<<Depth(tree)<<endl;cout<<"二叉树的结点数为："<<NodeCount(tree)<<endl;
}

《数据结构》—— 二叉树的复制、查深度与算结点操作

二叉树的操作

• • 一、二叉树的复制
  • 二、计算二叉树的深度
  • 三、计算二叉树的结点

一、二叉树的复制

已经创建好的二叉树，首先我们对它进行判空操作，再创建新的根结点 NewT，把根结点T 赋给 NewT，递归复制左(右)子树。

// 一、复制二叉树
void Copy(BiTree T, BiTree &NewT)
{if(T==NULL ){   //如果是空树，递归结束NewT=NULL;return;}else{NewT = new BiTNode;NewT->data = T->data;			//复制根结点Copy(T->lchild, NewT->lchild);  //递归复制左子树Copy(T->rchild, NewT->rchild);  //递归复制右子树}
}

二、计算二叉树的深度

【分析】：1、树为空则深度为0；2、否则递归计算左(右)子树的深度；3、取子树最大的深度，再加1。

// 二、计算二叉树的深度
int Depth(BiTree T){int m,n;if(T== NULL)return 0;  //如果是空树，深度为0，递归结束else {m=Depth(T->lchild);	  //递归计算左子树的深度记为mn=Depth(T->rchild);	  //递归计算右子树的深度记为nif(m>n)return(m+1);  //二叉树的深度为m 与n的较大者加1elsereturn (n+1);}
}

三、计算二叉树的结点

开始也是判空，否则结点个数为左子树的结点个数+右子树的结点个数+1。

// 三、计算二叉树的结点
int NodeCount(BiTree T){if(T==NULL) return 0;  			// 如果是空树，则结点个数为0，递归结束else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;//否则结点个数为左子树的结点个数+右子树的结点个数+1
}

完整代码如下：

#include<iostream>
using namespace std;// 二叉树的二叉链表存储表示
typedef struct BiNode{char data;						//结点数据域struct BiNode *lchild, *rchild;	//左右孩子指针
}BiTNode, *BiTree;// 先序建立二叉链表
void CreateBiTree(BiTree &T){// 按先序次序输入二叉树中结点的值(一个字符)，创建二叉链表表示的二叉树Tchar ch;cin >> ch;      //输入先序序列if(ch=='#')T=NULL;		//递归结束，建空树else{T=new BiTNode;CreateBiTree(T->lchild);	//递归创建左子树T->data=ch;					//生成根结点CreateBiTree(T->rchild);	//递归创建右子树}
}/*
T->data=ch;					//生成根结点
CreateBiTree(T->lchild);	//递归创建左子树
CreateBiTree(T->rchild);	//递归创建右子树可以把根左右顺序换成，中序：左根右；后序：左右根，来输入
*/								//CreateBiTree// 一、复制二叉树
void Copy(BiTree T, BiTree &NewT)
{if(T==NULL ){   //如果是空树，递归结束NewT=NULL;return;}else{NewT = new BiTNode;NewT->data = T->data;			//复制根结点Copy(T->lchild, NewT->lchild);  //递归复制左子树Copy(T->rchild, NewT->rchild);  //递归复制右子树}
}// 二、计算二叉树的深度
int Depth(BiTree T){int m,n;if(T== NULL)return 0;  //如果是空树，深度为0，递归结束else {m=Depth(T->lchild);	  //递归计算左子树的深度记为mn=Depth(T->rchild);	  //递归计算右子树的深度记为nif(m>n)return(m+1);  //二叉树的深度为m 与n的较大者加1elsereturn (n+1);}
}// 三、计算二叉树的结点
int NodeCount(BiTree T){if(T==NULL) return 0;  			// 如果是空树，则结点个数为0，递归结束else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;//否则结点个数为左子树的结点个数+右子树的结点个数+1
}// 中序遍历的递归算法
void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);cout << T->data;InOrderTraverse(T->rchild);}
}int main()
{BiTree tree,new_tree;cout<<"二叉链表的序列(先序输入) 例如：ABD##E##CF###：\n";CreateBiTree(tree);Copy(tree,new_tree);cout<<"复制得到的新树的中序序列：";InOrderTraverse(new_tree);cout<<endl;cout<<"二叉树的深度为："<<Depth(tree)<<endl;cout<<"二叉树的结点数为："<<NodeCount(tree)<<endl;
}