最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

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

互联网 admin 3浏览 0评论

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

二叉树的操作

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

一、二叉树的复制

已经创建好的二叉树,首先我们对它进行判空操作,再创建新的根结点 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;
}

发布评论

评论列表 (0)

  1. 暂无评论