树

2023-12-26 19:09:15

树

基本概念

逻辑结构

基本概念

树是n个结点的有限集合，n=0时，称为空树。

树是一种递归定义的数据结构。

非空树满足的条件：

有且仅有一个根节点
n>1时，其余结点可分为m(m>0)个互不相交的有限集合T1, T2 ,…, Tm,其中每个集合本身又是一棵树，并且称为根结点的子树。
叶子结点(终端结点)：没有后继的结点。
分支结点(非终端结点)：有后继的结点。
n个结点的树中有n-1条边

基本术语

结点的深度：结点的层次，从上往下数。看是从0开始还是从1开始。
结点的高度：结点的高度，从下往上数。
树的高度(深度)：总共多少层。
结点的度：有几个孩子(分支)。叶子结点的度=0，非叶子结点的度>零。
树的度：各结点的度的最大值。
有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换。
无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换。
森林：m棵互不相交的树的集合。eg.全中国所有人的家谱

常考性质

结点数=总度数+1；结点的度--结点有几个孩子(分支)

度为m的树	m叉树
各结点的度的最大值	每个结点最多只能有m个孩子的树
任意结点的度<=m(最多m个孩子)	任意结点的度<=m(最多m个孩子)
至少有一个结点度=m(有m个孩子)	允许所有结点的度都<m
一定是非空树，至少有m+1个结点	可以是空树

度为m的树第i层至多有m^(i-1)个结点(i>=1)

m叉树第i层至多有m^(i-1)个结点(i>=1)

高度为h的m叉树至多有(m^h-1)/(m-1)个结点。

等比数列求和公式

高度为h的m叉树至少有h个结点。

高度为h，度为m的树至少有h+m-1个结点

具有n个结点的m叉树最小高度为

二叉树

基本概念

二叉树是n个结点的有限集合。(n>=0)

特点

1. 每个结点至多只有两棵子树
2. 左右子树不能颠倒(二叉树是有序树)
3. 区别：度为2的有序树

分类

分类	满二叉树	`完全二叉树`	二叉排序树	平衡二叉树
概念	高度为h，且含有2^h -1个结点的二叉树。	当且仅当每一个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。		树上任一结点的左子树和右子树的深度之差不超过1。
特点	①只有最后一层有叶子结点。	①只有最后两层可能有叶子结点	①左子树上所有结点的关键字均小于根结点的关键字。	①有更高的搜索效率
	②不存在度为1的结点。	②最多只有一个度为1的结点	②右子树上所有结点的关键字均小于根结点的关键字。
	③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父结点为[i/2]	同左③	③左右子树各是一棵二叉排序树。
		④i<=[n/2]为分支结点，i>[n/2]为叶子结点.(向下取整)

性质

1`非空二叉树中度为0、1和2的结点个数分别为n0,n1,n2,则n0=n2+1;(叶子结点比度为2的结点多一个)。

树中结点总数为n，②-①=>n0=n2+1;

①n=n0+n1+n2

②n=n1+2n2+1(树的结点数=总度数+1)

存储结构

顺序存储

 //按照从上至下，从左至右的顺序依次存储完全二叉树中的各个结点。
//可以让第一个位置空缺，保证数组下标和结点编号完全一致。
#define MaxSize 100
struct TreeNode{
    ELemType value;
    bool isEmpty;
};
TreeNode t[MaxSize];
for(int i=0;i<MaxSize; i++){
    t[i].isEmpty = true;
}
//i的左孩子    ---2i
//i的右孩子    ---2i+1
//i的父节点    ---[i/2]
//i所在的层次  ---[log2(n+1)]或[log2n]+1

链式存储

typedef struct BitNode{
    ElemType data;
    struct BitNode *lchild,*rchild;
}BiTNode,*BiTree;
//每个结点两个指针域
//n个结点的二叉链表共有n+1个空链域
//2n个指针
//n-1个结点上连有指针

//定义一棵空树
BiTree root = NULL;
//插入结点
root = (BiTree) malloc(sizeof(BiTree));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;
//插入新结点
BiTNode *p=(BiTNode*)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;


///为了查找父结点方便，加入父指针变为三叉链表

遍历

遍历：按某条路径访问树中的每个结点，使得每个结点均被访问一次，且仅被访问一次。序是指根结点被访问的次序。

递归工作栈的栈深即为树的深度，最坏情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的空间复杂度为O(n).

一个前/中/后/层序遍历序列中的一种，可能对应多种二叉树形态。中序序列和其他任意一种遍历序列，可以唯一确定二叉树。

前序+中序，可以确定根结点的位置

前序遍历（深度优先遍历（DFS））

根左右(NLR)

每个结点路过三次，根结点第一次被访问。

//递归
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
   } 
}
//非递归，栈
class Solution{
    List list = new ArrayList();
    public List<Integer>
}

中序遍历

左根右(LNR)

中缀表达式需要加界限符(左右括号和表达式结束符)。

每个结点都会被通过三次，根结点只有第三次是被访问。

不能从一个指定结点开始中序遍历，必须从根结点出发。

不能从指定结点找到中序遍历的前驱。

后序遍历

左右根(LRN)

路过三次，根结点只有第三次是被访问。

层序遍历（广度优先遍历（BFS）

栈和队列均可实现

void LevelOrder(BiTree T){
    //设置辅助队列
    LinkQueue Q;	//链队列
    InitQueue(Q);	//初始化
    BiTree p;
    EnQueue(Q,T);	//入队
    while(!IsEmpty(Q)){	//判断队空，队非空则false
        DeQueue(Q,p);	//出队
        visit(p);	//访问出队结点
        //左孩子非空，左孩子入队
        if(p->lchild!=NULL)	
            EnQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);
    }
    
    typedef struct BiTNode{
        char data;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    typedef struct LinkNode{
        BiTNode *data;
        struct LinkNode *next;
    }LinkNode;
    
    typedef struct{
        LinkNode *front,*rear;
    }LinkQueue;
    
    
}

线索二叉树

n个结点的二叉树，有n+1个空链域，可用来记录前驱后继的信息，以便访问结点。

线索：指向前驱后继的指针为线索

前驱线索：左孩子指针

后继线索：右孩子指针

核心：用一个指针pre记录当前访问结点的前驱结点。

存储结构

*lchild	ltag	data	rtag	*rchild
左孩子	0指向左孩子		0指向右孩子	右孩子
前驱线索	1指针是线索		1指针是线索	后继线索

//线索二叉树的结点(链式存储)
typedef struct ThreadNode{
    ElemType data;
    struct  ThreadNode *lchild,*rchild;
    //线索标志
    int ltag,rtag;
}ThreadNode,*ThreadTree;

先序线索二叉树

 //全局变量pre指向当前访问结点的前驱
ThreadNode *pre=NULL；
//先序线索化二叉树T
void CreatePreThread(ThreadTree T){
    pre=NULL;
      //非空二叉树才能线索化
    if(T!=NULL){
      //先序线索化二叉树
        PreThread(T);
        //处理最后一个结点
        if(pre->rchid==NULL);
           pre->rtag=1;
    }
}
//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
    if(T!=NULL){
        //先处理根结点
        visit(T);
        /*PreThread(T->lchild);
        可能导致死循环,只有先序会有问题
        */
        if(T->ltag==0)
            //lchild不是前驱线索
            PreThread(T->lchild);
        PreThread(T->rchild);
    }
}
void visit(ThreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        //建立前驱结点的后继线索
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q；
}

找先序后继

若p有左孩子，则先序后继为左孩子。

若p没有左孩子，则先序后继为右孩子。

找先序前驱

先序遍历中，左右子树中的结点只可能是根的后继不可能是前驱。

如果能找到p的父结点，且p是左孩子，p的父结点即为其前驱。

如果能找到p的父结点，且p是右孩子，其左兄弟为空，p的父结点即为其前驱。

如果能找到p的父结点，且p是右孩子，其左兄弟非空，p的前去为做兄弟子树中最后一个被先序遍历的节点。

中序线索二叉树

//全局变量pre指向当前访问结点的前驱
ThreadNode *pre=NULL;

void InThread(ThreadTree T){
    if(T!=NULL){
        //中序遍历左子树
        InThread(T->lchild);
        //访问根结点
        visit(T);
        //中序遍历右子树
        InThread(T->rchild);
    }
}
void visit(ThreadNode *q){
    //左子树为空，建立前驱线索
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        //建立前驱结点的后继线索
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}
//中序线索化二叉树
void CreatenInThread(ThreadTree T){
    //pre初始值
    pre=NULL;
    //非空二叉树才能线索化
    if(T!=NULL){
        InThread(T);
        //中序线索化二叉树
        if(pre->rchild==NULL)
            //处理遍历的最后一个结点
            pre->rtag=1;
    }
}

找中序后继

若有右节点，最右子树最左下节点

若无右节点，找前驱

//找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
    //循环找到最左下结点(不一定是叶结点)
    while(p->ltag==0) p=p->lchild;
    return p; 
}
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag==0)
        return Firstnode(p->rchild);
    //rtag==1，直接返回后继线索
    else return p->rchild;
}
//对线索二叉树进行遍历（非递归）
void Inorder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
        visit(p);
}

//找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p){
    //找最右下结点
    while(p->rtag==0)
        p=p->rchild;
    return p;
}
//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreaNode *p){
    if(p->ltag==0)
        return Lastnode(p->lchild);
    //ltag==1直接返回前驱线索
    else return p->lchild;
}

后序线索二叉树

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//后续线索化二叉树T
void CreatePostThread(ThreadTree T){
    //初始化pre
    pre=NULL;
    //非空二叉树
    if(T!=NULL){
        //后序线索化
        PostThread(T);
        if(pre->rchild==NULL)
            //处理遍历的最后一个结点
            pre->rtag=1;
    }
}
//一边遍历一边线索化
void PostThread(ThreadTree T){
    if(T!=NULL){
        PostThread(T->lchild);
        PostThread(T->rchild)
            visit(T);
    }
}
void visit(ThreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1
    }
    pre=q;
}

找后序前驱

若p有右孩子，则后序前驱为右孩子

若p没有右孩子，则后序前驱为左孩子、

找后序后继

后序遍历中，左右子树中的结点只可能是根的前驱不可能是后继。

如果能找到p的父结点，且p是右孩子，p的父结点即为其后继。

如果能找到p的父结点，且p是左孩子，其右兄弟为空。p的父结点即为其后继。

如果能找到p的父结点，且p是左孩子，其右兄弟非空，p的后继为右兄弟子树中第一个被后序遍历的结点。

如果p是根结点，p没有后续后继。

	中序线索二叉树	先序线索二叉树	后序线索二叉树
找前驱	√	×	√
找后继	√	√	三叉链表

码农公寓

树

基本概念

逻辑结构

基本概念

基本术语

常考性质

二叉树

基本概念

特点

分类

性质

存储结构

顺序存储

链式存储

遍历

前序遍历（深度优先遍历（DFS））

中序遍历

后序遍历

层序遍历（广度优先遍历（BFS）

线索二叉树

存储结构

先序线索二叉树

找先序后继

找先序前驱

中序线索二叉树

找中序后继

后序线索二叉树

找后序前驱

找后序后继

相关文章