3. 树和二叉树
3.1 树的基本概念
树的定义
树的基本术语
3.2 二叉树
3.2.1 二叉树的定义及其主要特征
二叉树的定义
二叉树的5个性质
3.2.2 二叉树的顺序存储结构和链式存储结构
3.2.3 二叉树的遍历
3.3 树、森林
3.3.1 树的存储结构
3.3.2 森林与二叉树的转换
3.3.3 树和森林的遍历
3.4 树与二叉树的应用
3.4.1 哈夫曼(Huffman)树和哈夫曼编码
3.4.2 并查集及其应用
1. 树的定义
树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：
- 有且仅有一个特定的称为根的结点。
- 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。
二叉树
1. 二叉树的定义
二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树是n (n≥0) 个结点的有限集合:
- 或者为空二叉树，即n=0。
- 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树的5种基本形态
- 空二叉树
- 只有根节点
- 只有左子树
- 只有右子树
- 左右子树都有
二叉树的层次建树
- 引用头文件
typedef char BiElemType; // 定义节点类型
typedef struct BiTNode{ // 二叉树节点
BiElemType data; // 数据
struct BiTNode *lchild; // 左子树
struct BiTNode *rchild; // 右子树
}BiTNode,*BiTree;
typedef struct tag{
BiTree p; //树的某一个结点的地址值
struct tag *pnext;
}tag_t,*ptag_t;
//栈的相关数据结构
#define MaxSize 50
typedef BiTree ElemType;
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack &S); // 初始化栈
bool StackEmpty(SqStack &S); // 判断栈是否为空
bool Push(SqStack &S,ElemType x); // 入栈
bool Pop(SqStack &S,ElemType &x); // 出栈
bool GetTop(SqStack &S,ElemType &x); // 获取栈顶元素
//队列的相关数据结构
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
void InitQueue(LinkQueue &Q); // 初始化队列
bool IsEmpty(LinkQueue Q); // 判断队列是否为空
void EnQueue(LinkQueue &Q,ElemType x); // 入队
bool DeQueue(LinkQueue &Q,ElemType &x); // 出队
- 层次建树
// 核心代码
BiTree pnew;
int i,j,pos;
char c;
BiTree tree=NULL;//树根
ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;//phead就是队列头，ptail就是队列尾
//abcdefghij
while(scanf("%c",&c)!=EOF)
{
if(c=='\n')
{
break;
}
pnew=(BiTree)calloc(1,sizeof(BiTNode));//calloc申请空间并对空间进行初始化，赋值为0
pnew->c=c;//数据放进去
listpnew=(ptag_t)calloc(1,sizeof(tag_t));//给队列结点申请空间
listpnew->p=pnew;
if(NULL==tree)
{
tree=pnew;//树的根
phead=listpnew;//队列头
ptail=listpnew;//队列尾
pcur=listpnew;
continue;
}else{
ptail->pnext=listpnew;//新结点放入链表，通过尾插法
ptail=listpnew;//ptail指向队列尾部
}//pcur始终指向要插入的结点的位置
if(NULL==pcur->p->lchild)//如何把新结点放入树
{
pcur->p->lchild=pnew;//把新结点放到要插入结点的左边
}else if(NULL==pcur->p->rchild)
{
pcur->p->rchild=pnew;//把新结点放到要插入结点的右边
pcur=pcur->pnext;//左右都放了结点后，pcur指向队列的下一个
}
}
- 前序遍历
void preOrder(BiTree p)
{
if(p!=NULL)
{
putchar(p->c);//等价于visit函数
preOrder(p->lchild);
preOrder(p->rchild);
}
}
- 中序遍历
void InOrder(BiTree p)
{
if(p!=NULL)
{
InOrder(p->lchild);
putchar(p->c);
InOrder(p->rchild);
}
}
- 后序遍历
void PostOrder(BiTree p)
{
if(p!=NULL)
{
PostOrder(p->lchild);
PostOrder(p->rchild);
putchar(p->c);
}
}
- 中序遍历非递归，非递归执行效率更高。
void InOrder2(BiTree T)
{
SqStack S;
InitStack(S);BiTree p=T;
while(p||!StackEmpty(S))//逻辑或||
{
if(p)
{//当一个结点不为空，压栈，并取左孩子
Push(S,p);
p=p->lchild;
}else{//弹出栈中元素并打印，获取打印元素的右结点
Pop(S,p);putchar(p->c);
p=p->rchild;
}
}
}
- 层次遍历,层序遍历，广度优先遍历
void LevelOrder(BiTree T)
{
LinkQueue Q;//辅助队列
InitQueue(Q);//初始化队列
BiTree p;
EnQueue(Q,T);//树根入队
while(!IsEmpty(Q))
{
DeQueue(Q,p);//出队当前结点并打印
putchar(p->c);
if(p->lchild!=NULL) //入队左孩子
EnQueue(Q,p->lchild);
if(p->rchild!=NULL) //入队右孩子
EnQueue(Q,p->rchild);
}
}
二叉排序树
- 如何设计？
typedef int KeyType;
typedef struct BSTNode{
KeyType key;
struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;
- 如何插入？
int BST_Insert(BiTree &T,KeyType k)
{
if(NULL==T)
{ //为新节点申请空间
T=(BiTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1;//代表插入成功
}
else if(k==T->key)
return 0;//发现相同元素，就不插入
else if(k<T->key)
return BST_Insert(T->lchild,k);
else
return BST_Insert(T->rchild,k);
}
- 如何查找？
BSTNode *BST_Search(BiTree T,KeyType key,BiTree &p)
{
p=NULL;
while(T!=NULL&&key!=T->key)
{
p=T;
if(key<T->key) T=T->lchild;//比当前节点小，就左边找
else T=T->rchild;//比当前节点大，右边去
}
return T;
}
- 如何删除？
void DeleteNode(BiTree &root,KeyType x){
if(root == NULL){
return;
}
if(root->key>x){
DeleteNode(root->lchild,x);
}else if(root->key<x){
DeleteNode(root->rchild,x);
}else{ //查找到了删除节点
if(root->lchild == NULL){ //左子树为空
BiTree tempNode = root;
root = root->rchild;
free(tempNode);
}else if(root->rchild == NULL){ //右子树为空
BiTree tempNode = root;//临时指针
root = root->lchild;
free(tempNode);
}else{ //左右子树都不为空
//一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替要删除的节点(这里采用查找左子树最大数据来代替)
BiTree tempNode = root->lchild;
if(tempNode->rchild!=NULL){
tempNode = tempNode->rchild;
}
root->key = tempNode->key;
DeleteNode(root->lchild,tempNode->key);
}
}
}
- 中序遍历
void InOrder(BiTree T)
{
if(T!=NULL)
{
InOrder(T->lchild);
printf("%3d",T->key);
InOrder(T->rchild);
}
}
评论区