树和二叉树

树和二叉树

一、树

1.概述

树（Tree）是n（n≥0）个结点的有限集合，当n=0时，为空树；n>0时，为非空树。任意一棵非空树，满足：

1)有且仅有一个称之为根的结点；

2)除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1, T2, …, Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

2.树的相关术语

● 节点——节点包含数据元素及若干指向子树的分支信息。 ● 节点的度——节点拥有的子树个数。 ● 树的度——树中节点的最大度数。 ● 终端节点——度为0的节点，又称为叶子 ● 分支节点——度大于0的节点。除了叶子都是分支节点。 ● 内部节点——除了树根和叶子都是内部节点。 ● 节点的层次——从根到该节点的层数（根节点为第1层）。 ● 树的深度（或高度）——指所有节点中最大的层数。 ● 路径——树中两个节点之间所经过的节点序列。 ● 路径长度——两节点之间路径上经过的边数。 ● 双亲、孩子——节点的子树的根称为该节点的孩子，反之，该节点为其孩子的双亲。 ● 兄弟——双亲相同的节点互称兄弟。 ● 堂兄弟——双亲是兄弟的节点互称堂兄弟。 ● 祖先——从该节点到树根经过的所有节点称为该节点的祖先。 ● 子孙——节点的子树中的所有节点都称为该节点的子孙。 ● 森林——由m（m≥0）棵不相交的树组成的集合。

3.树的存储结构

顺序存储

分为双亲表示法、孩子表示法和双亲孩子表示法。

3种表示法的优缺点如下。

双亲表示法只记录了每个节点的双亲，无法直接得到该节点的孩子；孩子表示法可以得到该节点的孩子，但是无法直接得到该节点的双亲，而且由于不知道每个节点到底有多少个孩子，因此只能按照树的度（树中节点的最大度）分配孩子空间，这样做可能会浪费很多空间。双亲孩子表示法是在孩子表示法的基础上，增加了一个双亲域，可以快速得到节点的双亲和孩子，其缺点和孩子表示法一样，可能浪费很多空间。

链式存储

(1)孩子链表表示法

类似于邻接表，表头包含数据元素并指向第一个孩子指针，将所有孩子放入一个单链表中。在表头中，data存储数据元素，first为指向第1个孩子的指针。单链表中的节点记录该节点的下标和下一个节点的地址。仍以图6-10为例，其孩子链表表示法如图6-12所示。

（2）孩子兄弟表示法

节点除了存储数据元素之外，还有两个指针域lchild和rchild，被称为二叉链表。lchild存储第一个孩子地址，rchild存储右兄弟地址。其节点的数据结构如图6-13所示。

树如图所示:

4.树、森林与二叉树的转换

(1)．树和二叉树的转换

秘诀：长子当作左孩子，兄弟关系向右

还原时逆操作即可.

(2)．森林和二叉树的转换

可以把森林中的每棵树的树根看作兄弟关系，因此3棵树的树根B、C和D是兄弟，兄弟关系在右斜线上，其他的转换和树转二叉树一样，长子当作左孩子，兄弟关系向右斜。或者把森林中的每一棵树转换成二叉树，然后把每棵树的根节点连接在右斜线上即可

以上大部分内容来自陈小玉老师的《趣学数据结构》

二、二叉树

1.概述

二叉树（binary tree）是n（n≥0）个节点构成的集合， 它或为空树（n=0），或满足以下两个条件： 1）有且仅有一个称为根的节点； 2）除根节点以外，其余节点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身都是二叉树。

二叉树是一种特殊的树，它最多有两个子树，分别为左子树和右子树，二者是有序的，不可以互换。也就是说，二叉树中不存在度大于2的节点。

两种特殊的二叉树: ●满二叉树：一棵深度为k且有2k-1个节点的二叉树。满二叉树每一层都“充满”了节点，达到最大节点数，如图6-24所示。 ●完全二叉树：除了最后一层外，每一层都是满的（达到最大节点数），最后一层节点是从左向右出现的

2.性质

性质1：在二叉树的第i层上至多有 2(i-1) 个节点。 性质2：深度为k的二叉树至多有 2^k-1个节点。 性质3：对于任何一棵二叉树，若叶子数为n0，度为2的节点数为n2，则n0=n2+1。 性质4：具有n个节点的完全二叉树的深度必为 ​​​log2n​​​+1。 性质5：对于完全二叉树，若从上至下、从左至右编号，则编号为i的节点，其左孩子编号必为2i，其右孩子编号必为2i +1，其双亲的编号必为i/2。

3. 二叉树的存储结构

1．顺序存储(可以使用树存储的三种方法,也可使用两个数组,一个记录左孩子,一个记录右孩子,节点和索引相对应) 2. 链式存储:二叉链表(最常用的那个,一个存放数据,还有两个指针),三叉链表

4.二叉树的创建

1.询问法

void createtree(Btree &T){ char check; T = new Bnode; cout<<"请输入节点信息:"<>T->data; cout<<"是否添加"<data<<"的左孩子? (Y/N)"<>check; if(check=='Y'){ createtree(T->lchild); } else{ T->lchild = NULL; } cout<<"是否添加"<data<<"的右孩子? (Y/N)"<>check; if(check=='Y'){ createtree(T->rchild); } else{ T->rchild = NULL; } }

2.补空法(更常用)

void Createtree(Btree &T) { /*创建二叉树函数*/ char ch; cin>>ch; if(ch=='#'){ T = NULL; } else{ T = new Bnode; T->data = ch; Createtree(T->lchild); Createtree(T->rchild); }}

三、二叉树的遍历

直接上代码

#include#includeusing namespace std;typedef struct Bnode { char data; Bnode *lchild,*rchild; } Bnode,*Btree;//Btree指代二叉树 void Createtree(Btree &T) { /*创建二叉树函数*/ char ch; cin>>ch; if(ch=='#'){ T = NULL; } else{ T = new Bnode; T->data = ch; Createtree(T->lchild); Createtree(T->rchild); }}void preorder(Btree T){//先序遍历 if(T){ cout<data<<" "; preorder(T->lchild); preorder(T->rchild); }}void inorder(Btree T){//中序遍历 if(T){ preorder(T->lchild); cout<data<<" "; preorder(T->rchild); }} void posorder(Btree T){//后序遍历 if(T){ posorder(T->lchild); preorder(T->rchild); cout<data<<" "; } } bool Leveltraverse(Btree T){ Btree p; if(!T){//如果是空树则结束 return false; } queue Q; Q.push(T); while(!Q.empty()){ p=Q.front(); Q.pop(); cout<data<<" "; if(p->lchild){ Q.push(p->lchild); } if(p->rchild){ Q.push(p->rchild); } } return true;}int main() { Btree mytree; cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<

运行结果:

测试的二叉树:

四、树的应用

1.前序/后序和中序还原建立二叉树.

#include using namespace std;typedef struct node{ char data; struct node *lchild,*rchild;}BiTNode,*BiTree;BiTree pre_mid_createBiTree(char *pre,char *mid,int len) //前序中序还原建立二叉树{ if(len==0) return NULL; char ch=pre[0]; //找到先序中的第一个结点 int index=0; while(mid[index]!=ch)//在中序中找到的根结点的左边为该结点的左子树，右边为右子树 { index++; } BiTree T=new BiTNode;//创建根结点 T->data=ch; T->lchild=pre_mid_createBiTree(pre+1,mid,index);//建立左子树 T->rchild=pre_mid_createBiTree(pre+index+1,mid+index+1,len-index-1);//建立右子树 return T;}BiTree pro_mid_createBiTree(char *last,char *mid,int len)//后序中序还原建立二叉树{ if(len==0) return NULL; char ch=last[len-1]; //取得后序遍历顺序中最后一个结点 int index=0;//在中序序列中找根结点，并用index记录长度 while(mid[index]!=ch)//在中序中找到根结点，左边为该结点的左子树，右边为右子树 index++; BiTree T=new BiTNode;//创建根结点 T->data=ch; T->lchild=pro_mid_createBiTree(last,mid,index);//建立左子树 T->rchild=pro_mid_createBiTree(last+index,mid+index+1,len-index-1);//建立右子树 return T;}void pre_order(BiTree T)//前序递归遍历二叉树{ if(T) { cout<data; pre_order(T->lchild); pre_order(T->rchild); }}void pro_order(BiTree T)//后序递归遍历二叉树{ if(T) { pro_order(T->lchild); pro_order(T->rchild); cout<data; }}int main(){ BiTree T; int n; char pre[100],mid[100],last[100]; cout<<"1. 前序中序还原二叉树\n"; cout<<"2. 后序中序还原二叉树\n"; cout<<"0. 退出\n"; int choose=-1; while(choose!=0) { cout<<"请选择:"; cin>>choose; switch (choose) { case 1://前序中序还原二叉树 cout<<"请输入结点的个数:"<>n; cout<<"请输入前序序列:"<>pre[i]; cout<<"请输入中序序列:"<>mid[i]; T=pre_mid_createBiTree(pre,mid,n); cout<>n; cout<<"请输入后序序列:"<>last[i]; cout<<"请输入中序序列:"<>mid[i]; T=pro_mid_createBiTree(last,mid,n); cout<

运行结果

2.求叶子数和节点数

#include using namespace std;typedef struct Bnode /*定义二叉树存储结构*/{ char data; struct Bnode *lchild,*rchild;}Bnode,*Btree;void Createtree(Btree &T) /*创建二叉树函数*/{ //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T char ch; cin >> ch; if(ch=='#') T=NULL; //递归结束，建空树 else{ T=new Bnode; T->data=ch; //生成根结点 Createtree(T->lchild); //递归创建左子树 Createtree(T->rchild); //递归创建右子树 }}int LeafCount(Btree T)//求二叉树的叶子数{ if(T==NULL)//如果为空树，深度为0 return 0; else if(T->lchild==NULL&&T->rchild==NULL)//左右子树均为空，则叶子数为1 return 1; else return LeafCount(T->lchild)+LeafCount(T->rchild);//递归计算左子树和右子树的叶子数之和}int NodeCount(Btree T)//求二叉树的结点数{ if(T==NULL)//如果为空树，深度为0 return 0; else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;//递归计算左子树和右子树的结点数之和加1}int main(){ Btree mytree; cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<

3.求二叉树的深度

#include using namespace std;typedef struct Bnode /*定义二叉树存储结构*/{ char data; struct Bnode *lchild,*rchild;}Bnode,*Btree;void Createtree(Btree &T) /*创建二叉树函数*/{ //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T char ch; cin >> ch; if(ch=='#') T=NULL; //递归结束，建空树 else{ T=new Bnode; T->data=ch; //生成根结点 Createtree(T->lchild); //递归创建左子树 Createtree(T->rchild); //递归创建右子树 }}int Depth(Btree T)//求二叉树的深度{ int m,n; if(T==NULL)//如果为空树，深度为0 return 0; else { m=Depth(T->lchild);//递归计算左子树深度 n=Depth(T->rchild);//递归计算左子树深度 if(m>n) return m+1;//返回左右子树最大值加1 else return n+1; }}int main(){ Btree mytree; cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。