《数据结构》—— 二叉树的复制、查深度与算结点操作
二叉树的操作
- 一、二叉树的复制
- 二、计算二叉树的深度
- 三、计算二叉树的结点
一、二叉树的复制
已经创建好的二叉树,首先我们对它进行判空操作,再创建新的根结点 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;
}