五、树
树的定义
树的逻辑表示：树形表示法、文氏图表示法、凹入表示法、括号表示法。
结点：表示树中的元素，包括数据项及若干指向其子树的分支。
结点的度：结点拥有的子树树；树的度：一棵树中最大的结点度数
叶子结点：度为0的结点；分支结点：度不为0的结点；孩子：结点子树的根称为该结点的孩子；双亲：孩子结点的上层结点叫该结点的双亲；兄弟：同一双亲的孩子。
深度：树中结点的最大层次数。
有序树：树中各结点的子树从左至右是有次序的，不能互换。否则称为无序树。
树的性质
树中的结点数等于所有结点的度数加1。
度为m的树中第i层上至多有mi-1 个结点（i>=1）。
二叉树的概念
满二叉树：定义——一棵深度为k且具有2k-1个结点的二叉树。特点——每一层上的结点数都是最大结点数。
完全二叉树：定义——深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。
二叉树的性质
二叉树的第i层上至多有2i-1(i>=1)个结点。
深度为K的二叉树至多有2k-1个结点。
对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1。
一个有n个结点的完全二叉树，编号最大的分支结点的编号是
一个有n个结点的完全二叉树，n0的个数是不小于n/2的最小整数。
二叉树的存储结构
用一组连续的存储单元存储二叉树的数据元素。在存储之前对二叉树的所有结点安排一个适当的序列，使得结点在这个序列中的相互位置能反应出结点之间的逻辑关系。
特点：结点间关系蕴含在其存储位置中；浪费空间，适于存满二叉树和完全二叉树。
二叉树的链式存储结构
用一个链表来存储一棵二叉树，二叉树中每一个结点用链表中的一个链结点来存储。 
遍历二叉树
遍历方法：
利用遍历结果确定二叉树：
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef char ElemType;
//二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子）
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树
void CreateBiTree(BiTree *T)
{
ElemType ch;
cin >> ch;
if (ch == '#')
*T = NULL; //保证是叶结点
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
//if (!*T)
//exit(OVERFLOW); //内存分配失败则退出。
(*T)->data = ch;//生成结点
CreateBiTree(&(*T)->lchild);//构造左子树
CreateBiTree(&(*T)->rchild);//构造右子树
}
}
//表示对遍历到的结点数据进行的处理操作,此处操作是将树结点前序遍历输出
void operation1(ElemType ch)
{
cout << ch << " ";
}
//此处在输出的基础上，并输出层数
void operation2(ElemType ch, int level)
{
cout << ch << "在第" << level << "层" << endl;
}
//递归方式前序遍历二叉树
void PreOrderTraverse(BiTree T, int level)
{
if (T == NULL)
return;
/*此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据*/
//operation1(T->data);
operation2(T->data, level); //输出了层数
PreOrderTraverse(T->lchild, level + 1);
PreOrderTraverse(T->rchild, level + 1);
}
//递归方式中序遍历二叉树
void InOrderTraverse(BiTree T,int level)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild,level+1);
//operation1(T->data);
operation2(T->data, level); //输出了层数
InOrderTraverse(T->rchild,level+1);
}
//递归方式后序遍历二叉树
void PostOrderTraverse(BiTree T,int level)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild,level+1);
PostOrderTraverse(T->rchild,level+1);
//operation1(T->data);
operation2(T->data, level); //输出了层数
}
int main()
{
int level = 1; //表示层数
BiTree T = NULL;
cout << "请以前序遍历的方式输入扩展二叉树："; //类似输入AB#D##C##
CreateBiTree(&T);// 建立二叉树，没有树，怎么遍历
cout << "递归前序遍历输出为：" << endl;
PreOrderTraverse(T, level);//进行前序遍历，其中operation1()和operation2()函数表示对遍历的结点数据进行的处理操作
cout << endl;
cout << "递归中序遍历输出为：" << endl;
InOrderTraverse(T, level);
cout << endl;
cout << "递归后序遍历输出为：" << endl;
PostOrderTraverse(T, level);
cout << endl;
return 0;
}
注意：
- 建立二叉树时，这里是以前序遍历的方式，输入的是扩展二叉树，也就是要告诉计算机什么是叶结点，否则将一直递归，当输入“#”时，指针指向NULL，说明是叶结点。
operation1( )函数只是对各个结点的输出；operation2( )函数不仅输出了各个结点，同时输出了结点所在的层数。
- 非递归方式的遍历如下：
- 我们可以借助栈，实现3种遍历的非递归算法
- 除此之外，还给出了二叉树的层次遍历算法，所谓层次遍历，就是自顶向下、自左至右的遍历二叉树中的元素，可以借助队列实现。
#include<iostream>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
typedef char ElemType;
//二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子）
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树
void CreateBiTree(BiTree *T)
{
ElemType ch;
cin >> ch;
if (ch == '#')
*T = NULL; //保证是叶结点
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
//if (!*T)
//exit(OVERFLOW); //内存分配失败则退出。
(*T)->data = ch;//生成结点
CreateBiTree(&(*T)->lchild);//构造左子树
CreateBiTree(&(*T)->rchild);//构造右子树
}
}
//表示对遍历到的结点数据进行的处理操作,此处操作是将树结点前序遍历输出
void operation1(ElemType ch)
{
cout << ch << " ";
}
//此处在输出的基础上，并输出层数
void operation2(ElemType ch, int level)
{
cout << ch << "在第" << level << "层" << " ";
}
//递归方式前序遍历二叉树
void PreOrderTraverse(BiTree T, int level)
{
if (T == NULL)
return;
/*此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据*/
operation1(T->data);
//operation2(T->data, level); //输出了层数
PreOrderTraverse(T->lchild, level + 1);
PreOrderTraverse(T->rchild, level + 1);
}
//递归方式中序遍历二叉树
void InOrderTraverse(BiTree T,int level)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild,level+1);
operation1(T->data);
//operation2(T->data, level); //输出了层数
InOrderTraverse(T->rchild,level+1);
}
//递归方式后序遍历二叉树
void PostOrderTraverse(BiTree T,int level)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild,level+1);
PostOrderTraverse(T->rchild,level+1);
operation1(T->data);
//operation2(T->data, level); //输出了层数
}
//非递归方式前序遍历
/* 思路：将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。*/
void PreOrder(BiTree T){
stack<BiTree> stack;
//p是遍历指针
BiTree p = T;
//p不为空或者栈不空时循环
while (p || !stack.empty())
{
if (p != NULL)
{
//存入栈中
stack.push(p);
//对树中的结点进行操作
operation1(p->data);
//遍历左子树
p = p->lchild;
}
else
{
//退栈
p = stack.top();
stack.pop();
//访问右子树
p = p->rchild;
}
}
}
//非递归中序遍历
void InOrder(BiTree T)
{
stack<BiTree> stack;
//p是遍历指针
BiTree p = T;
//p不为空或者栈不空时循环
while (p || !stack.empty())
{
if (p != NULL)
{
//存入栈中
stack.push(p);
//遍历左子树
p = p->lchild;
}
else
{
//退栈
p = stack.top();
operation1(p->data); //对树中的结点进行操作
stack.pop();
//访问右子树
p = p->rchild;
}
}
}
//非递归后序遍历
typedef struct BiTNodePost{
BiTree biTree;
char tag;
}BiTNodePost, *BiTreePost;
void PostOrder(BiTree T)
{
stack<BiTreePost> stack;
//p是遍历指针
BiTree p = T;
BiTreePost BT;
//栈不空或者p不空时循环
while (p != NULL || !stack.empty())
{
//遍历左子树
while (p != NULL)
{
BT = (BiTreePost)malloc(sizeof(BiTNodePost));
BT->biTree = p;
//访问过左子树
BT->tag = 'L';
stack.push(BT);
p = p->lchild;
}
//左右子树访问完毕访问根节点
while (!stack.empty() && (stack.top())->tag == 'R')
{
BT = stack.top();
//退栈
stack.pop();
p=BT->biTree;
cout<<BT->biTree->data<<" ";
}
//遍历右子树
if (!stack.empty())
{
BT = stack.top();
//访问过右子树
BT->tag = 'R';
p = BT->biTree;
p = p->rchild;
}
}
}
//层次遍历
void LevelOrder(BiTree T)
{
BiTree p = T;
queue<BiTree> queue;
//根节点入队
queue.push(p);
//队列不空循环
while (!queue.empty())
{
//对头元素出队
p = queue.front();
//访问p指向的结点
operation1(p->data);
//退出队列
queue.pop();
//左孩子不为空，将左孩子入队
if (p->lchild != NULL)
{
queue.push(p->lchild);
}
//右孩子不空，将右孩子入队
if (p->rchild != NULL)
{
queue.push(p->rchild);
}
}
}
int main()
{
int level = 1; //表层数
BiTree T = NULL;
cout << "请以前序遍历的方式输入扩展二叉树："; //类似输入AB#D##C##
CreateBiTree(&T);// 建立二叉树，没有树，怎么遍历
cout << "递归前序遍历输出为：" << endl;
PreOrderTraverse(T, level);//进行前序遍历，其中operation1()和operation2()函数表示对遍历的结点数据进行的处理操作
cout << endl;
cout << "递归中序遍历输出为：" << endl;
InOrderTraverse(T, level);
cout << endl;
cout << "递归后序遍历输出为：" << endl;
PostOrderTraverse(T, level);
cout << endl;
cout<<"非递归前序遍历输出为："<<endl;
PreOrder(T);
cout<<endl;
cout<<"非递归前序遍历输出为："<<endl;
InOrder(T);
cout<<endl;
cout<<"非递归前序遍历输出为："<<endl;
PostOrder(T);
cout<<endl;
cout<<"层序遍历输出为："<<endl;
LevelOrder(T);
cout<<endl;
return 0;
}
线索二叉树
利用二叉链表的空指针域，建立指向该结点的前驱/后继结点的指针，方便二叉树的线性化使用。
对二叉链表以某种次序遍历使其变为线索二叉树的过程叫做线索化。有先序线索二叉树、中序线索二叉树（更实用）和后序线索二叉树三种。
建立中序线索二叉树
树的存储结构
双亲表示法：用一组连续空间存储树的结点，每个节点包含两个域——数据域用来存放结点本身信息，双亲域用来指示本结点的双亲结点在数组中位置。
孩子表示法：采用孩子链表，每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。
带双亲的孩子链表
孩子兄弟表示法：用二叉链表作为树的存储结构。链表中结点的两个链域分为指向该结点的第一个孩子结点和下一个兄弟结点。
森林与二叉树的转换
将树转换为二叉树
将二叉树转换为树：
森林转换成二叉树：
二叉树转换成森林
哈夫曼树
结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根节点到该结点之间的路径长度与该结点的权的乘积。
在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称哈夫曼树。
全部评论