一、树
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<<"请输入节点信息:"<<endl; cin>>T->data; cout<<"是否添加"<<T->data<<"的左孩子? (Y/N)"<<endl;//询问是否创建T的左子树 cin>>check; if(check=='Y'){ createtree(T->lchild); } else{ T->lchild = NULL; } cout<<"是否添加"<<T->data<<"的右孩子? (Y/N)"<<endl;//询问是否创建T的左子树 cin>>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<iostream> #include<queue> using 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<<T->data<<" "; preorder(T->lchild); preorder(T->rchild); } } void inorder(Btree T){//中序遍历 if(T){ preorder(T->lchild); cout<<T->data<<" "; preorder(T->rchild); } } void posorder(Btree T){//后序遍历 if(T){ posorder(T->lchild); preorder(T->rchild); cout<<T->data<<" "; } } bool Leveltraverse(Btree T){ Btree p; if(!T){//如果是空树则结束 return false; } queue<Btree> Q; Q.push(T); while(!Q.empty()){ p=Q.front(); Q.pop(); cout<<p->data<<" "; if(p->lchild){ Q.push(p->lchild); } if(p->rchild){ Q.push(p->rchild); } } return true; } int main() { Btree mytree; cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl; Createtree(mytree);//创建二叉树 cout<<endl; cout<<"二叉树的先序遍历结果："<<endl; preorder(mytree);//先序遍历二叉树 cout<<endl; cout<<"二叉树的中序遍历结果："<<endl; inorder(mytree);//中序遍历二叉树 cout<<endl; cout<<"二叉树的后序遍历结果："<<endl; posorder(mytree);//后序遍历二叉树 cout<<endl; cout<<"二叉树的层次遍历结果："<<endl; Leveltraverse(mytree);//层次遍历二叉树 return 0; }
运行结果:
四、树的应用
1.前序/后序和中序还原建立二叉树.
#include <iostream> 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<<T->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<<T->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<<"请输入结点的个数:"<<endl; cin>>n; cout<<"请输入前序序列:"<<endl; for(int i=0;i<n;i++) cin>>pre[i]; cout<<"请输入中序序列:"<<endl; for(int i=0;i<n;i++) cin>>mid[i]; T=pre_mid_createBiTree(pre,mid,n); cout<<endl; cout<<"二叉树还原成功，输出其后序序列:"<<endl; pro_order(T); cout<<endl<<endl; break; case 2://后序中序还原二叉树 cout<<"请输入结点的个数:"<<endl; cin>>n; cout<<"请输入后序序列:"<<endl; for(int i=0 ;i<n;i++) cin>>last[i]; cout<<"请输入中序序列:"<<endl; for(int i=0 ;i<n;i++) cin>>mid[i]; T=pro_mid_createBiTree(last,mid,n); cout<<endl; cout<<"二叉树还原成功，输出其先序序列:"<<endl; pre_order(T); cout<<endl<<endl; break; } } return 0; }
运行结果
2.求叶子数和节点数
#include <iostream> 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<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl; //ABD##E##CF#G### Createtree(mytree);//创建二叉树 cout<<endl; cout<<"二叉树的结点数为："<<NodeCount(mytree)<<endl; cout<<"二叉树的叶子数为："<<LeafCount(mytree)<<endl; return 0; }
3.求二叉树的深度
#include <iostream> 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<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl; //ABD##E##CF#G### Createtree(mytree);//创建二叉树 cout<<endl; cout<<"二叉树的深度为："<<Depth(mytree)<<endl; return 0; }
