精华内容
下载资源
问答
  • 数据结构全树是什么
    万次阅读 多人点赞
    2021-03-07 20:16:50

    在数据结构中,树是一对多的存在,如下图是一颗树。

    根结点为①的树
    结点拥有的子树个数称为结点的度,比如结点①的度为4,结点②的度为0,结点③的度为3。

    对于树而言,树的度为树内各结点最大的度,从图中可知,结点①的度是最大的,为4,所以这棵树的度为4。

    更多相关内容
  • 数据结构(Tree)【详解】

    万次阅读 多人点赞 2021-02-22 10:22:25
    的存储结构;森林与二叉树的转换;和森林的遍历 与二叉树的应用 二叉排序;平衡二叉树;哈夫曼和哈弗编码 三、的基本概念 1、的定义 是n(n>=0)个结点的有限集。当n = 0时,称为空。在...

    友情链接:数据结构专栏

    目录

    【知识框架】

    在这里插入图片描述

    一、树的基本概念

    1、树的定义

    树是n(n>=0)个结点的有限集。当n = 0时,称为空树。在任意一棵非空树中应满足:

    1. 有且仅有一个特定的称为根的结点。
    2. 当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树。

    显然,树的定义是递归的,即在树的定义中又用到了自身,树是一种递归的数据结构。树作为一种逻辑结构,同时也是一种分层结构,具有以下两个特点:

    1. 树的根结点没有前驱,除根结点外的所有结点有且只有一个前驱。
    2. 树中所有结点可以有零个或多个后继。

    因此n个结点的树中有n-1条边。

    2、基本术语

    下面结合图示来说明一下树的一些基本术语和概念。
    在这里插入图片描述

    1. 考虑结点K。根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。
    2. 树中一个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。
    3. 度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。
    4. 结点的深度、高度和层次。
      结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。
      结点的深度是从根结点开始自顶向下逐层累加的。
      结点的高度是从叶结点开始自底向上逐层累加的。
      树的高度(或深度)是树中结点的最大层数。图中树的高度为4。
    5. 有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图为有序树,若将子结点位置互换,则变成一棵不同的树。
    6. 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。
      注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。
    7. 森林。森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给m棵独立的树加上一个结点,并把这m棵树作为该结点的子树,则森林就变成了树。

    注意:上述概念无须刻意记忆, 根据实例理解即可。

    3、树的性质

    树具有如下最基本的性质:

    1. 树中的结点数等于所有结点的度数加1.
    2. 度为 m m m的树中第 i i i层上至多有 m i − 1 m^{i-1} mi1个结点( i > = 1 i>=1 i>=1
    3. 高度为 h h h m m m叉树至多有 ( m h − 1 ) / ( m − 1 ) (m^h-1)/(m-1) (mh1)/(m1)个结点。
    4. 具有 n n n个结点的 m m m叉树的最小高度为 [ l o g m ( n ( m − 1 ) + 1 ) ] [log_m(n(m-1)+1)] [logm(n(m1)+1)]

    二、树的存储结构

    在介绍以下三种存储结构的过程中,我们都以下面这个树为例子。
    在这里插入图片描述

    1、双亲表示法

    我们假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。也就是说,每个结点除了知道自已是谁以外,还知道它的双亲在哪里。
    在这里插入图片描述
    其中data是数据域,存储结点的数据信息。而parent是指针域,存储该结点的双亲在数组中的下标。
    以下是我们的双亲表示法的结点结构定义代码。

    /*树的双亲表示法结点结构定义*/
    #define MAX_TREE_SIZE 100
    typedef int TElemType;	//树结点的数据类型,目前暂定为整型
    /*结点结构*/
    typedef struct PTNode{
    	TElemType data;	//结点数据
    	int parent;	//双亲位置
    }PTNode;
    /*树结构*/
    typedef struct{
    	PTNode nodes[MAX_TREE_SIZE];	//结点数组
    	int r, n;	//根的位置和结点数
    }PTree;
    

    这样的存储结构,我们可以根据结点的parent 指针很容易找到它的双亲结点,所用的时间复杂度为0(1),直到parent为-1时,表示找到了树结点的根。可如果我们要知道结点的孩子是什么,对不起,请遍历整个结构才行。

    2、孩子表示法

    具体办法是,把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成-一个线性表,采用顺序存储结构,存放进一个一维数组中,如图所示。
    在这里插入图片描述
    为此,设计两种结点结构,一个是孩子链表的孩子结点。
    在这里插入图片描述
    其中child是数据域,用来存储某个结点在表头数组中的下标。next 是指针域,用来存储指向某结点的下一个孩子结点的指针。

    另一个是表头数组的表头结点。
    在这里插入图片描述
    其中data是数据域,存储某结点的数据信息。firstchild 是头指针域,存储该结点的孩子链表的头指针。

    以下是我们的孩子表示法的结构定义代码。

    /*树的孩子表示法结构定义*/
    #define MAX_TREE_SIZE 100
    /*孩子结点*/
    typedef struct CTNode{
    	int child;
    	struct CTNode *next;
    }*ChildPtr;
    /*表头结点*/
    typedef struct{
    	TElemType data;
    	ChildPtr firstchild;
    }CTBox;
    /*树结构*/
    typedef struct{
    	CTBox nodes[MAX_TREE_SIZE];	//结点数组
    	int r, n;	//根的位置和结点数
    }
    

    这样的结构对于我们要查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的,对头结点的数组循环即可。
    但是,这也存在着问题,我如何知道某个结点的双亲是谁呢?比较麻烦,需要整棵树遍历才行,难道就不可以把双亲表示法和孩子表示法综合一下吗? 当然是可以,这个读者可自己尝试结合一下,在次不做赘述。

    3、孩子兄弟表示法

    刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构,如果我们从树结点的兄弟的角度又会如何呢?当然,对于树这样的层级结构来说,只研究结点的兄弟是不行的,我们观察后发现,任意一棵树, 它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。 因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟
    结点的结构如下:
    在这里插入图片描述
    其中data是数据域,firstchild 为指针域,存储该结点的第一个孩子结点的存储地址,rightsib 是指针域,存储该结点的右兄弟结点的存储地址。
    这种表示法,给查找某个结点的某个孩子带来了方便。
    结构定义代码如下。

    /*树的孩子兄弟表示法结构定义*/
    typedef struct CSNode{
    	TElemtype data;
    	struct CSNode *firstchild, *rightsib;
    } CSNode, *CSTree;
    

    于是通过这种结构,我们就把原来的树变成了这个样子:
    在这里插入图片描述

    这不就是个二叉树么?
    没错,其实这个表示法的最大好处就是它把一棵复杂的树变成了一棵二叉树
    接下来,我们详细介绍二叉树。

    二叉树

    一、二叉树的概念

    1、二叉树的定义

    二叉树是另一种树形结构,其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒。
    与树相似,二叉树也以递归的形式定义。二叉树是n (n≥0) 个结点的有限集合:

    1. 或者为空二叉树,即n=0。
    2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

    二叉树是有序树,若将其左、右子树颠倒,则成为另一棵不同的二叉树。即使树中结点只有一棵子树,也要区分它是左子树还是右子树。二叉树的5种基本形态如图所示。
    在这里插入图片描述

    2、几个特殊的二叉树

    (1)斜树

    所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

    (2)满二叉树

    一棵高度为 h h h,且含有 2 h − 1 2^h-1 2h1个结点的二叉树称为满二叉树,即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层,并且除叶子结点之外的每个结点度数均为 2 2 2。可以对满二叉树按层序编号:约定编号从根结点(根结点编号为 1 1 1)起,自上而下,自左向右。这样,每个结点对应一个编号,对于编号为i的结点,若有双亲,则其双亲为 i / 2 i/2 i/2,若有左孩子,则左孩子为 2 i 2i 2i;若有右孩子,则右孩子为 2 i + 1 2i+1 2i+1
    在这里插入图片描述

    (3)完全二叉树

    高度为 h h h、有 n n n个结点的二叉树,当且仅当其每个结点都与高度为 h h h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树,如图所示。其特点如下:
    在这里插入图片描述

    1. i ≤ n / 2 i≤n/2 in/2, 则结点 i i i为分支结点,否则为叶子结点。
    2. 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点,都依次排列在该层最左边的位置上。
    3. 若有度为 1 1 1的结点,则只可能有一个,且该结点只有左孩子而无右孩子(重要特征)。
    4. 按层序编号后,一旦出现某结点(编号为 i i i)为叶子结点或只有左孩子,则编号大于 i i i的结点均为叶子结点。
    5. n n n为奇数,则每个分支结点都有左孩子和右孩子;若 n n n为偶数,则编号最大的分支结点(编号为 n / 2 n/2 n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有。

    (4)二叉排序树

    左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树。

    (5)平衡二叉树

    树上任一结点的左子树和右子树的深度之差不超过1。

    3、二叉树的性质

    1. 任意一棵树,若结点数量为 n n n,则边的数量为 n − 1 n-1 n1
    2. 非空二叉树上的叶子结点数等于度为 2 2 2的结点数加 1 1 1,即 n o = n 2 + 1 n_o=n_2+ 1 no=n2+1
    3. 非空二叉树上第 k k k层上至多有 2 k − 1 2^{k-1} 2k1个结点 ( k ≥ 1 ) (k≥1) (k1)
    4. 高度为 h h h的二叉树至多有 2 h − 1 2^h-1 2h1个结点 ( h ≥ 1 ) (h≥1) (h1)
    5. 对完全二叉树按从上到下、从左到右的顺序依次编号 1 , 2.. ∗ , n 1,2..*,n 1,2..,n,则有以下关系:
      • i > 1 i>1 i>1时,结点 i i i的双亲的编号为 i / 2 i/2 i/2,即当 i i i为偶数时, 它是双亲的左孩子;当i为奇数时,它是双亲的右孩子。
      • 2 i ≤ n 2i≤n 2in时,结点 i i i的左孩子编号为 2 i 2i 2i, 否则无左孩子。
      • 2 i + 1 ≤ n 2i+1≤n 2i+1n时,结点 i i i的右孩子编号为 2 i + 1 2i+1 2i+1,否则无右孩子。
      • 结点 i i i所在层次(深度)为 { l o g 2 i } + 1 \{log_2i\}+ 1 {log2i}+1
    6. 具有 n n n ( n > 0 ) (n>0) (n>0)结点的完全二叉树的高度为 { l o g 2 n } + 1 \{log_2n\}+1 {log2n}+1

    4、二叉树的存储结构

    (1)顺序存储结构

    二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为 i i i的结点元素存储在一维数组下标为 i − 1 i-1 i1的分量中。
    依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映结点之间的逻辑关系,这样既能最大可能地节省存储空间,又能利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。
    但对于一般的二叉树,为了让数组下标能反映二叉树中结点之间的逻辑关系,只能添加一些并不存在的空结点,让其每个结点与完全二叉树上的结点相对照,再存储到一维数组的相应分量中。然而,在最坏情况下,一个高度为 h h h且只有 h h h个结点的单支树却需要占据近 2 h − 1 2h-1 2h1个存储单元。二叉树的顺序存储结构如图所示,其中0表示并不存在的空结点。
    在这里插入图片描述

    (2)链式存储结构

    既然顺序存储适用性不强,我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域是比较自然的想法,我们称这样的链表叫做二叉链表
    在这里插入图片描述
    其中data是数据域,lchild 和rchild都是指针域,分别存放指向左孩子和右孩子的指针。
    以下是我们的二叉链表的结点结构定义代码。

    /*二叉树的二叉链表结点构造定义*/
    /*结点结构*/
    typedef struct BiTNode{
    	TElemType data;	//结点数据
    	struct BiTNode *lchild, *rchild;	//左右孩子指针
    } BiTNode, *BiTree;
    

    在这里插入图片描述
    容易验证,在含有 n n n个结点的二叉链表中,含有 n + 1 n + 1 n+1个空链域


    二、遍历二叉树

    二叉树的遍历( traversing binary tree )是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

    1、先序遍历

    先序遍历(PreOrder) 的操作过程如下:
    若二叉树为空,则什么也不做,否则,
    1)访问根结点;
    2)先序遍历左子树;
    3)先序遍历右子树。

    在这里插入图片描述
    对应的递归算法如下:

    void PreOrder(BiTree T){
    	if(T != NULL){
    		visit(T);	//访问根节点
    		PreOrder(T->lchild);	//递归遍历左子树
    		PreOrder(T->rchild);	//递归遍历右子树
    	}
    }
    

    2、中序遍历

    中序遍历( InOrder)的操作过程如下:
    若二叉树为空,则什么也不做,否则,
    1)中序遍历左子树;
    2)访问根结点;
    3)中序遍历右子树。

    在这里插入图片描述
    对应的递归算法如下:

    void InOrder(BiTree T){
    	if(T != NULL){
    		InOrder(T->lchild);	//递归遍历左子树
    		visit(T);	//访问根结点
    		InOrder(T->rchild);	//递归遍历右子树
    	}
    }
    

    3、后序遍历

    后序遍历(PostOrder) 的操作过程如下:
    若二叉树为空,则什么也不做,否则,
    1)后序遍历左子树;
    2)后序遍历右子树;
    3)访问根结点。

    在这里插入图片描述
    对应的递归算法如下:

    void PostOrder(BiTree T){
    	if(T != NULL){
    		PostOrder(T->lchild);	//递归遍历左子树
    		PostOrder(T->rchild);	//递归遍历右子树
    		visit(T);	//访问根结点
    	}
    }
    

    三种遍历算法中,递归遍历左、右子树的顺序都是固定的,只是访问根结点的顺序不同。不管采用哪种遍历算法,每个结点都访问一次且仅访问一次,故时间复杂度都是O(n)。在递归遍历中,递归工作栈的栈深恰好为树的深度,所以在最坏情况下,二叉树是有n个结点且深度为n的单支树,遍历算法的空间复杂度为O(n)。

    4、递归算法和非递归算法的转换

    我们以下图的树为例子。
    在这里插入图片描述

    (1)中序遍历的非递归算法

    借助栈,我们来分析中序遍历的访问过程:

    1. 沿着根的左孩子,依次入栈,直到左孩子为空,说明已找到可以输出的结点,此时栈内元素依次为ABD。
    2. 栈顶元素出栈并访问:若其右孩子为空,继续执行步骤2;若其右孩子不空,将右子树转执行步骤1。

    栈顶D出栈并访问,它是中序序列的第一个结点; D右孩子为空,栈顶B出栈并访问; B右孩子不空,将其右孩子E入栈,E左孩子为空,栈顶E出栈并访问; E右孩子为空,栈顶A出栈并访问; A右孩子不空,将其右孩子C入栈,C左孩子为空,栈顶C出栈并访问。由此得到中序序列DBEAC。
    根据分析可以写出中序遍历的非递归算法如下:

    void InOrder2(BiTree T){
    	InitStack(S);	//初始化栈S
    	BiTree p = T;	//p是遍历指针
    	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
    		if(p){
    			Push(S, p);	//当前节点入栈
    			p = p->lchild;	//左孩子不空,一直向左走
    		}else{
    			Pop(S, p);	//栈顶元素出栈
    			visit(p);	//访问出栈结点
    			p = p->rchild;	//向右子树走,p赋值为当前结点的右孩子
    		}
    	}
    }
    

    (2)先序遍历的非递归算法

    先序遍历和中序遍历的基本思想是类似的,只需把访问结点操作放在入栈操作的前面。先序遍历的非递归算法如下:

    void PreOrder2(BiTree T){
    	InitStack(S);	//初始化栈S
    	BiTree p = T;	//p是遍历指针
    	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
    		if(p){
    			visit(p);	//访问出栈结点
    			Push(S, p);	//当前节点入栈
    			p = p->lchild;	//左孩子不空,一直向左走
    		}else{
    			Pop(S, p);	//栈顶元素出栈
    			p = p->rchild;	//向右子树走,p赋值为当前结点的右孩子
    		}
    	}
    }
    

    (3)后序遍历的非递归算法

    后序遍历的非递归实现是三种遍历方法中最难的。因为在后序遍历中,要保证左孩了和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点,这就为流程的控制带来了难题。

    算法思想:后序非递归遍历二叉树是先访问左子树,再访问右子树,最后访问根结点。

    1. 沿着根的左孩子,依次入栈,直到左孩子为空。此时栈内元素依次为ABD。
    2. 读栈顶元素:若其右孩子不空且未被访问过,将右子树转执行①;否则,栈顶元素出栈并访问。

    栈顶D的右孩子为空,出栈并访问,它是后序序列的第一个结点;栈顶B的右孩子不空且未被访问过,E入栈,栈顶E的左右孩子均为空,出栈并访问;栈顶B的右孩子不空但已被访问,B出栈并访问;栈项A的右孩子不空且未被访问过,C入栈,栈项C的左右孩子均为空,出栈并访问;栈顶A的右孩子不空但已被访问,A出栈并访问。由此得到后序序列DEBCA。
    在上述思想的第②步中,必须分清返回时是从左子树返回的还是从右子树返回的,因此设定一个辅助指针r,指向最近访问过的结点。也可在结点中增加一个标志域,记录是否已被访问。

    后序遍历的非递归算法如下:

    void PostOrder2(BiTree T){
    	InitStack(S);
    	p = T;
    	r = NULL;
    	while(p || !IsEmpty(S)){
    		if(p){	//走到最左边
    			push(S, p);
    			p = p->lchild;
    		}else{	//向右
    			GetTop(S, p);	//读栈顶元素(非出栈)
    			//若右子树存在,且未被访问过
    			if(p->rchild && p->rchild != r){
    				p = p->rchild;	//转向右
    				push(S, p);	//压入栈
    				p = p->lchild;	//再走到最左
    			}else{	//否则,弹出结点并访问
    				pop(S, p);	//将结点弹出
    				visit(p->data);	//访问该结点
    				r = p;	//记录最近访问过的结点
    				p = NULL;
    			}
    		}
    	}
    }
    

    5、层次遍历

    下图为二叉树的层次遍历,即按照箭头所指方向,按照1,2,3, 4的层次顺序,对二叉树中的各个结点进行访问。
    在这里插入图片描述

    要进行层次遍历,需要借助一个队列。先将二叉树根结点入队,然后出队,访问出队结点,若它有左子树,则将左子树根结点入队;若它有右子树,则将右子树根结点入队。然后出队,访问出队结…如此反复,直至队列为空。
    二叉树的层次遍历算法如下:

    void LevelOrder(BiTree T){
    	InitQueue(Q);	//初始化辅助队列
    	BiTree p;
    	EnQueue(Q, T);	//将根节点入队
    	while(!IsEmpty(Q)){	//队列不空则循环
    		DeQueue(Q, p);	//队头结点出队
    		visit(p);	//访问出队结点
    		if(p->lchild != NULL){
    			EnQueue(Q, p->lchild);	//左子树不空,则左子树根节点入队
    		}
    		if(p->rchild != NULL){
    			EnQueue(Q, p->rchild);	//右子树不空,则右子树根节点入队
    		}
    	}
    }
    

    6、由遍历序列构造二叉树

    由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
    在先序遍历序列中,第一个结点一定是二叉树的根结点;而在中序遍历中,根结点必然将中序序列分割成两个子序列,前一个子序列是根结点的左子树的中序序列,后一个子序列是根结点的右子树的中序序列。根据这两个子序列,在先序序列中找到对应的左子序列和右子序列。在先序序列中,左子序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。
    如此递归地进行下去,便能唯一地确定这棵二叉树
    同理,由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
    因为后序序列的最后一个结点就如同先序序列的第一个结点,可以将中序序列分割成两个子序列,然后采用类似的方法递归地进行划分,进而得到一棵二叉树。
    由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。
    要注意的是,若只知道二叉树的先序序列和后序序列,则无法唯一确定一棵二叉树。
    例如,求先序序列( ABCDEFGH)和中序序列( BCAEDGHFI)所确定的二叉树
    首先,由先序序列可知A为二叉树的根结点。中序序列中A之前的BC为左子树的中序序列,EDGHFI为右子树的中序序列。然后由先序序列可知B是左子树的根结点,D是右子树的根结点。以此类推,就能将剩下的结点继续分解下去,最后得到的二叉树如图©所示。
    在这里插入图片描述

    三、线索二叉树

    1、线索二叉树原理

    遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列,从而得到几种遍历序列,使得该序列中的每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。
    传统的二叉链表存储仅能体现一种父子关系,不能直接得到结点在遍历中的前驱或后继。
    在这里插入图片描述
    首先我们要来看看这空指针有多少个呢?对于一个有n个结点的二叉链表,每个结点有指向左右孩子的两个指针域,所以一共是2n个指针域。而n个结点的二叉树一共有n-1 条分支线数,也就是说,其实是存在2n- (n-1) =n+1个空指针域。

    由此设想能否利用这些空指针来存放指向其前驱或后继的指针?这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。
    我们把这种指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树(Threaded Binary Tree)。

    其结点结构如下所示:
    在这里插入图片描述
    其中

    • ltag为0时指向该结点的左孩子,为1时指向该结点的前驱。
    • rtag为0时指向该结点的右孩子,为1时指向该结点的后继。

    因此对于上图的二叉链表图可以修改为下图的样子。
    在这里插入图片描述

    2、线索二叉树的结构实现

    二叉树的线索存储结构代码如下:

    typedef struct ThreadNode{
    	ElemType data;	//数据元素
    	struct ThreadNode *lchild, *rchild;	//左、右孩子指针
    	int ltag, rtag;	//左、右线索标志
    }ThreadNode, *ThreadTree;
    

    3、二叉树的线索化

    二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到,因此线索化的实质就是遍历一次二叉树,线索化的过程就是在遍历的过程中修改空指针的过程。

    (1)中序线索二叉树

    以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点,指针p指向正在访问的结点,即pre指向p的前驱。在中序遍历的过程中,检查p的左指针是否为空,若为空就将它指向pre;检查pre的右指针是否为空,若为空就将它指向p,如下图所示。
    在这里插入图片描述
    通过中序遍历对二叉树线索化的递归算法如下:

    void InThread(ThreadTree p, ThreadTree pre){
    	if(p != NULL){
    		InThread(p->lchild, pre);	//递归,线索化左子树
    		if(p->lchild == NULL){	//左子树为空,建立前驱线索
    			p->lchild = pre;
    			p->ltag = 1;
    		}
    		if(pre != NULL && pre->rchild == NULL){
    			pre->rchild = p;	//建立前驱结点的后继线索
    			pre->rtag = 1;
    		}
    		pre = p;	//标记当前结点成为刚刚访问过的结点
    		InThread(p->rchild, pre);	//递归,线索化右子树
    	}
    }
    

    你会发现,除了中间的代码,和二叉树中序遍历的递归代码几乎完全一样。只不过将本是访问结点的功能改成了线索化的功能。

    通过中序遍历建立中序线索二叉树的主过程算法如下:

    void CreateInThread(ThreadTree T){
    	ThreadTree pre = NULL;
    	if(T != NULL){
    		InThread(T, pre);	//线索化二叉树
    		pre->rchild = NULL;	//处理遍历的最后一个结点
    		pre->rtag = 1;
    	}
    }
    

    为了方便,可以在二叉树的线索链表上也添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点。这好比为二叉树建立了一个双向线索链表,方便从前往后或从后往前对线索二叉树进行遍历,如下图所示。
    在这里插入图片描述
    遍历的代码如下:

    /*T指向头结点,头结点左链lchild指向根结点,头结点右链rchild指向中序遍
    的最后一个结点。中序遍历二叉线索链表表示的二叉树T*/
    void InOrderTraverse_Thr(BiThrTree T){
    	BiThrTree p;
    	p = T->lchild;	//p指向根结点
    	//空树或遍历结束时,p==T(最后一个结点指向根结点)
    	while(p != T){	
    		//当ltag==0时循环到中序序列第一个结点
    		while(p->ltag == 0){	
    			p = p->lchild;	//p指向p的左子树
    		}
    		visit(p);	//访问该结点
    		//后继线索为1且不是指向头指针
    		while(p->rtag == 1 && p->rchild != T){	
    			p = p->rchild;	//p指向p的后继
    			visit(p);	//访问该节点
    		}
    		//p进至其右子树根,开始对右子树根进行遍历
    		p = p->rchild;	
    	}
    }
    

    从这段代码也可以看出,它等于是一个链表的扫描,所以时间复杂度为0(n)。
    由于它充分利用了空指针域的空间(这等于节省了空间),又保证了创建时的一次遍历就可以终生受用前驱后继的信息(这意味着节省了时间)。所以在实际问题中,如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构就是非常不错的选择。

    (2)先序和后序线索二叉树

    上面给出了建立中序线索二叉树的代码,建立先序线索二叉树和后序线索二叉树的代码类似,只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。
    以图(a)的二叉树为例,其先序序列为ABCDF,后序序列为CDBFA,可得出其先序和后序线索二叉树分别如图(b)和( c)所示:
    在这里插入图片描述
    如何在先序线索二叉树中找结点的后继?如果有左孩子,则左孩子就是其后继;如果无左孩子但有右孩子,则右孩子就是其后继;如果为叶结点,则右链域直接指示了结点的后继。
    在后序线索二叉树中找结点的后继较为复杂,可分3种情况:①若结点x是二叉树的根,则其后继为空;②若结点x是其双亲的右孩子,或是其双亲的左孩子且其双亲没有右子树,则其后继即为双亲;③若结点x是其双亲的左孩子,且其双亲有右子树,则其后继为双亲的右子树上按后序遍历列出的第一个结点。图( c)中找结点B的后继无法通过链域找到,可见在后序线索二叉树上找后继时需知道结点双亲,即需采用带标志域的三叉链表作为存储结构。

    四、树、森林与二叉树的转化

    在讲树的存储结构时,我们提到了树的孩子兄弟法可以将一棵树用二叉链表进行存储,所以借助二叉链表,树和二叉树可以相互进行转换。从物理结构来看,它们的二叉链表也是相同的,只是解释不太一样而已。 因此,只要我们设定一定的规则,用二叉树来表示树,甚至表示森林都是可以的,森林与二叉树也可以互相进行转换。

    1、树转换为二叉树

    树转换为二义树的规则:每个结点左指针指向它的第一个孩子,右指针指向它在树中的相邻右兄弟,这个规则又称“左孩子右兄弟”。由于根结点没有兄弟,所以对应的二叉树没有右子树。

    树转换成二叉树的画法:

    1. 在兄弟结点之间加一连线;
    2. 对每个结点,只保留它与第一个孩子的连线,而与其他孩子的连线全部抹掉;
    3. 以树根为轴心,顺时针旋转45°。
      在这里插入图片描述

    2、森林转化为二叉树

    森林是由若干棵树组成的,所以完全可以理解为,森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作。
    森林转换成二叉树的画法:

    1. 将森林中的每棵树转换成相应的二叉树;
    2. 每棵树的根也可视为兄弟关系,在每棵树的根之间加一根连线;
    3. 以第一棵树的根为轴心顺时针旋转45°。
      在这里插入图片描述

    至于二叉树转换为树或者二叉树转换为森林只不过是上面步骤的逆过程,在此不做赘述。

    五、树和森林的遍历

    1、树的遍历

    树的遍历是指用某种方式访问树中的每个结点,且仅访问一次。主要有两种方式:

    1. 先根遍历。若树非空,先访问根结点,再依次遍历根结点的每棵子树,遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。
    2. 后根遍历。若树非空,先依次遍历根结点的每棵子树,再访问根结点,遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

    下图的树的先根遍历序列为ABEFCDG,后根遍历序列为EFBCGDA。
    在这里插入图片描述
    另外,树也有层次遍历,与二叉树的层次遍历思想基本相同,即按层序依次访问各结点。

    2、森林的遍历

    按照森林和树相互递归的定义,可得到森林的两种遍历方法。

    1. 先序遍历森林。若森林为非空,则按如下规则进行遍历:
      ●访问森林中第一棵树的根结点。
      ●先序遍历第一棵树中根结点的子树森林。
      ●先序遍历除去第一棵树之后剩余的树构成的森林。
    2. 后序遍历森林。森林为非空时,按如下规则进行遍历:
      ●后序遍历森林中第一棵树的根结点的子树森林。
      ●访问第一棵树的根结点。
      ●后序遍历除去第一棵树之后剩余的树构成的森林。

    图5.17的森林的先序遍历序列为ABCDEFGHI,后序遍历序列为BCDAFEHIG。
    在这里插入图片描述
    当森林转换成二叉树时,其第一棵树的子树森林转换成左子树,剩余树的森林转换成右子树,可知森林的先序和后序遍历即为其对应二叉树的先序和中序遍历。

    树与二叉树的应用

    一、二叉排序树

    1、定义

    二叉排序树(也称二叉查找树)或者是一棵空树,或者是具有下列特性的二叉树:

    1. 若左子树非空,则左子树上所有结点的值均小于根结点的值。
    2. 若右子树非空,则右子树上所有结点的值均大于根结点的值。
    3. 左、右子树也分别是一棵二叉排序树。

    根据二叉排序树的定义,左子树结点值<根结点值<右子树结点值,所以对二叉排序树进行中序遍历,可以得到一个递增的有序序列。例如,下图所示二叉排序树的中序遍历序列为123468。
    在这里插入图片描述

    2、二叉排序树的常见操作

    构造一个二叉树的结构:

    /*二叉树的二叉链表结点结构定义*/
    typedef struct BiTNode
    {
    	int data;	//结点数据
    	struct BiTNode *lchild, *rchild;	//左右孩子指针
    } BiTNode, *BiTree;
    

    (1)查找操作

    /*
    递归查找二叉排序树T中是否存在key
    指针f指向T的双亲,其初始调用值为NULL
    若查找成功,则指针p指向该数据元素结点,并返回TRUE
    否则指针p指向查找路径上访问的最后一个结点并返回FALSE
    */
    bool SearchBST(BiTree T, int key, BiTree f, BiTree *p){
    	if(!T){
    		*p = f;
    		return FALSE;
    	}else if(key == T->data){
    		//查找成功
    		*p = T;
    		return TRUE;
    	}else if(key < T->data){
    		return SearchBST(T->lchild, key, T, p);	//在左子树继续查找
    	}else{
    		return SearchBST(T->rchild, key, T, p);	//在右子树继续查找
    	}
    }
    

    (2)插入操作

    有了二叉排序树的查找函数,那么所谓的二叉排序树的插入,其实也就是将关键字放到树中的合适位置而已。

    /*
    当二叉排序树T中不存在关键字等于key的数据元素时
    插入key并返回TRUE,否则返回FALSE
    */
    bool InsertBST(BiTree *T, int key){
    	BiTree p, s;
    	if(!SearchBST(*T, key, NULL, &p)){
    		//查找不成功
    		s = (BiTree)malloc(sizeof(BiTNode));
    		s->data = key;
    		s->lchild = s->rchild = NULL;
    		if(!p){
    			*T = s;	//插入s为新的根节点
    		}else if(key < p->data){
    			p->lchild = s;	//插入s为左孩子
    		}else{
    			p->rchild = s;	//插入s为右孩子
    		}
    		return TRUE;
    		}else{
    			return FALSE;	//树种已有关键字相同的结点,不再插入
    		}
    }
    

    有了二叉排序树的插入代码,我们要实现二叉排序树的构建就非常容易了,几个例子:

    int i;
    int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
    BiTree T = NULL;
    for(i = 0; i<10; i++){
    	InsertBST(&T, a[i]);
    }
    

    上面的代码就可以创建一棵下图这样的树。
    在这里插入图片描述

    (3)删除操作

    二叉排序树的查找和插入都很简单,但是删除操作就要复杂一些,此时要删除的结点有三种情况:

    1. 叶子结点;
    2. 仅有左或右子树的结点;
    3. 左右子树都有的结点;

    前两种情况都很简单,第一种只需删除该结点不需要做其他操作;第二种删除后需让被删除结点的直接后继接替它的位置;复杂就复杂在第三种,此时我们需要遍历得到被删除结点的直接前驱或者直接后继来接替它的位置,然后再删除
    第三种情况如下图所示:
    在这里插入图片描述

    代码如下:

    /*
    若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点,
    并返回TRUE;否则返回FALSE
    */
    bool DeleteBST(BiTree *T, int key){
    	if(!*T){
    		return FALSE; 
    	}else{
    		if(key == (*T)->data){
    			//找到关键字等于key的数据元素
    			return Delete(T);
    		}else if(key < (*T) -> data){
    			return DeleteBST((*T) -> lchild, key);
    		}else{
    			return DeleteBST((*T) -> rchild, key);
    		}
    	}
    }
    

    下面是Delete()方法:

    /*从二叉排序树中删除结点p,并重接它的左或右子树。*/
    bool Delete(BiTree *p){
    	BiTree q, s;
    	if(p->rchild == NULL){
    		//右子树为空则只需重接它的左子树
    		q = *p;
    		*p = (*p)->lchild;
    		free(q);
    	}else if((*p)->lchild == NULL){
    		//左子树为空则只需重接它的右子树
    		q = *p;
    		*p = (*p)->rchild;
    		free(q);
    	}else{
    		//左右子树均不空
    		q = *p;
    		s = (*p)->lchild;	//先转左
    		while(s->rchild){//然后向右到尽头,找待删结点的前驱
    			q = s;
    			s = s->rchild;
    		}
    		//此时s指向被删结点的直接前驱,p指向s的父母节点
    		p->data = s->data;	//被删除结点的值替换成它的直接前驱的值
    		if(q != *p){
    			q->rchild = s->lchild;	//重接q的右子树
    		}else{
    			q->lchild = s->lchild;	//重接q的左子树
    		}
    		pree(s);
    	}
    	return TRUE;
    }
    

    3、小结(引申出平衡二叉树)

    二叉排序树的优点明显,插入删除的时间性能比较好。而对于二叉排序树的查找,走的就是从根结点到要查找的结点的路径,其比较次数等于给定值的结点在二叉排序树的层数。极端情况,最少为1次,即根结点就是要找的结点,最多也不会超过树的深度。也就是说,二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于,二叉排序树的形状是不确定的。
    例如 { 62 , 88 , 58 , 47 , 35 , 73 , 51 , 99 , 37 , 93 } \{62,88,58,47,35,73,51,99,37,93\} {62,88,58,47,35,73,51,99,37,93}这样的数组,我们可以构建如下左图的二叉排序树。但如果数组元素的次序是从小到大有序,如{35,37,47,51,58,62,73,88,93,99},则二叉排序树就成了极端的右斜树,如下面右图的二叉排序树:
    在这里插入图片描述
    也就是说,我们希望二叉排序树是比较平衡的,即其深度与完全二叉树相同,那么查找的时间复杂也就为 O ( l o g n ) O(logn) O(logn),近似于折半查找。
    不平衡的最坏情况就是像上面右图的斜树,查找时间复杂度为 O ( n ) O(n) O(n),这等同于顺序查找。
    因此,如果我们希望对一个集合按二叉排序树查找,最好是把它构建成一棵平衡的二叉排序树


    二、平衡二叉树

    1、定义

    平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1。
    它是一种高度平衡的二叉排序树。它要么是一棵空树, 要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor) , 那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。
    在这里插入图片描述

    2、平衡二叉树的查找

    在平衡二叉树上进行查找的过程与二叉排序树的相同。因此,在查找过程中,与给定值进行比较的关键字个数不超过树的深度。假设以 n h n_h nh表示深度为 h h h的平衡树中含有的最少结点数。显然,有 n 0 = 0 , n 1 = 1 , n 2 = 2 n_0=0,n_1=1,n_2=2 n0=0,n1=1,n2=2,并且有 n h = n h − 1 + n h − 2 + 1 n_h=n_{h-1}+n_{h-2}+1 nh=nh1+nh2+1。可以证明,含有 n n n个结点的平衡二叉树的最大深度为 O ( l o g 2 n ) O(log2n) O(log2n),因此平衡二叉树的平均查找长度为 O ( l o g 2 n ) O(log2n) O(log2n) 如下图所示。
    在这里插入图片描述

    3、平衡二叉树的插入

    二叉排序树保证平衡的基本思想如下:每当在二叉排序树中插入(或删除)一个结点时,首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡,则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A,再对以A为根的子树,在保持二叉排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。
    注意:每次调整的对象都是最小不平衡子树,即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。下图中的虚线框内为最小不平衡子树。
    在这里插入图片描述
    平衡二叉树的插入过程的前半部分与二叉排序树相同,但在新结点插入后,若造成查找路径上的某个结点不再平衡,则需要做出相应的调整。可将调整的规律归纳为下列4种情况:

    1. LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点,而B的原右子树则作为A结点的左子树。
      如下图所示,结点旁的数值代表结点的平衡因子,而用方块表示相应结点的子树,下方数值代表该子树的高度。
      在这里插入图片描述
    2. RR平衡旋转(左单旋转)。由于在结点A的右孩子®的右子树®上插入了 新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点,将A结点向左下旋转成为B的左子树的根结点,而B的原左子树则作为A结点的右子树。
      在这里插入图片描述
    3. LR平衡旋转(先左后右双旋转)。由于在A的左孩子(L)的右子树®上插入新结点,A的平衡因子由1增至2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置(即进行一次RR平衡旋转(左单旋转)),然后再把该C结点向右上旋转提升到A结点的位置(即进行一次LL平衡旋转(右单旋转))。在这里插入图片描述
    4. RL平衡旋转(先右后左双旋转)。由于在A的右孩子®的左子树(L)上插入新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要进行两次旋转操作,先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置(即进行一次LL平衡旋转(右单旋转)),然后再把该C结点向左上旋转提升到A结点的位置(即进行一次RR平衡旋转(左单旋转))。在这里插入图片描述
      注意: LR和RL旋转时,新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程,而上图中是以插入C的左子树中为例。

    举个例子:
    假设关键字序列为 15 , 3 , 7 , 10 , 9 , 8 {15,3, 7, 10, 9, 8} 15,3,7,10,9,8,通过该序列生成平衡二叉树的过程如下图所示。
    在这里插入图片描述

    二叉排序树还有另外的平衡算法,如红黑树(Red Black Tree)等,与平衡二叉树(AVL树)相比各有优势。


    三、哈夫曼树和哈夫曼编码

    1、哈夫曼树的定义和原理

    在许多应用中,树中结点常常被赋予一个表示某种意义的数值,称为该结点的。从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度,记为 W P L = ∑ i = 1 n w i l i WPL = \displaystyle\sum_{i=1}^{n} w_il_i WPL=i=1nwili式中, w i w_i wi是第i个叶结点所带的权值, l i l_i li是该叶结点到根结点的路径长度。
    在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树。例如,下图中的3棵二叉树都有4个叶子结点a, b,c,d,分别带权7,5,2,4,它们的带权路径长度分别为
    在这里插入图片描述
    a. WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36。
    b. WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46。
    c. WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35。
    其中,图c树的WPL最小。可以验证,它恰好为哈夫曼树。

    2、哈夫曼树的构造

    步骤:

    1. 先把有权值的叶子结点按照从大到小(从小到大也可以)的顺序排列成一个有序序列。
    2. 取最后两个最小权值的结点作为一个新节点的两个子结点,注意相对较小的是左孩子。
    3. 用第2步构造的新结点替掉它的两个子节点,插入有序序列中,保持从大到小排列。
    4. 重复步骤2到步骤3,直到根节点出现。

    看图就清晰了,如下图所示:
    在这里插入图片描述

    3、哈夫曼编码

    赫夫曼当前研究这种最优树的目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。
    哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。
    比如我们有一段文字内容为“ BADCADFEED”要网络传输给别人,显然用二进制的数字(0和1)来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF,那么我们可以用相应的二进制数据表示,如下表所示:
    在这里插入图片描述
    这样按照固定长度编码编码后就是“001000011010000011101100100011”,对方接收时可以按照3位一分来译码。如果一篇文章很长,这样的二进制串也将非常的可怕。而且事实上,不管是英文、中文或是其他语言,字母或汉字的出现频率是不相同的。
    假设六个字母的频率为A 27,B 8,C 15,D 15,E 30,F 5,合起来正好是
    100%。那就意味着,我们完全可以重新按照赫夫曼树来规划它们。
    下图左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0,右分支改为1后的赫夫曼树。
    在这里插入图片描述
    这棵哈夫曼树的WPL为:
    W P L = 2 ∗ ( 15 + 27 + 30 ) + 3 ∗ 15 + 4 ∗ ( 5 + 8 ) = 241 WPL=2*(15+27+30) + 3*15 + 4*(5+8)=241 WPL=2(15+27+30)+315+4(5+8)=241
    此时,我们对这六个字母用其从树根到叶子所经过路径的0或1来编码,可以得到如下表所示这样的定义。
    在这里插入图片描述
    若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。
    我们将文字内容为“ BADCADFEED”再次编码,对比可以看到结果串变小了。

    • 原编码二进制串: 000011000011101100100011 (共 30个字符)
    • 新编码二进制串: 10100101010111100(共25个字符)

    也就是说,我们的数据被压缩了,节约了大约17%的存储或传输成本。

    注意:
    0和1究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的,所以构造出的哈夫曼树并不唯一,但各哈夫曼树的带权路径长度WPL相同且为最优。此外,如有若干权值相同的结点,则构造出的哈夫曼树更可能不同,但WPL必然相同且是最优的。


    附录

    上文链接

    数据结构:串

    下文链接

    数据结构:图

    专栏

    数据结构专栏

    参考资料

    1、严蔚敏、吴伟民:《数据结构(C语言版)》
    2、程杰:《大话数据结构》
    3、王道论坛:《数据结构考研复习指导》
    4、托马斯·科尔曼等人:《算法导论》

    展开全文
  • 数据结构学习:什么

    千次阅读 2019-07-30 14:38:59
    是一个非线性的数据结构,相比较而言,数组,链表,栈和队列等等就是线性的数据结构可以为空,不包含任何节点,或者可以称为由一个根节点和零个或者多个子树构成的。 判断是否是一颗的条件: 有且...

    概念

    A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

    树是一个非线性的数据结构,相比较而言,数组,链表,栈和队列等等就是线性的数据结构。树可以为空,不包含任何节点,或者树可以称为由一个根节点和零个或者多个子树构成的。

    判断是否是一颗树的条件:

    • 有且只有一个根节点;
    • 有若干个互不相交的子树;
    • 根节点(root)没有父节点;
    • 一个节点有且只有一个父节点(根节点除外);
    • 节点可以有多个子节点;
      在这里插入图片描述

    和树相关的一些术语,查阅了网上的一些资料,做了一下整理;

    Terminology(术语)Explaining(解释)
    Root(根)树中的顶级节点
    Child(子节点)Root的每一个子树的叫做Root的子节点(Child)
    Parent(父节点)Root是每一个子树的的父节点(Parent)
    Siblings(兄弟节点)一些具有相同父节点的节点称为兄弟节点
    Descendant(后代)对任意节点x,从根节点到节点x的所有节点都是x的祖先
    Ancestor(祖先)对任意节点x,从节点x到叶子节点的所有节点都是x的后代
    Leaf(叶子节点)没有子节点的节点
    Degree(度)子节点的个数(最大子节点的度称为树的度)
    Edge(边)父节点和子节点相连的一个路径
    Depth(深度)节点的深度定义为:当前节点和根之间的边数。
    Height of node(节点的高)节点的高度是该节点与后代节点之间最长路径上的边数,所以叶子节点高度为0
    Height of tree(树的高)树的高度是其根节点的高度
    Forest (森林)多颗互不相交的树组成的集合

    树的分类

    按照个人的理解进行分类;

    • 一般树:任意一个节点的子节点的个数都不受限制;
    • 二叉树:任意一个节点的子节点的个数最多只有两个;
      • 一般二叉树
      • 满二叉树:在不增加树的层数的前提下,无法再多添加一个节点的二叉树
      • 完全二叉树:如果只是删除了满二叉树的最底层最右边的连续若干个节点,则这样形成的二叉树叫完全二叉树;
    • 森林:n个互不相交的树的集合;

    树的数据结构

    typedef struct TreeNode *PtreNode; //前向声明
    
    struct TreeNode {
        ElementType element;
        PtreNode	FirstChild;
        PtreNode	NextSibling;
    }
    

    总结

    大部分的知识点主要参考了wiki上的解释,这里对于二叉树的分类都是点到即止,其实需要自己结合实践写代码实现一下,深入了解知识点和应用场景,以加深理解,如有错误的地方,希望指正。

    参考

    Tree_(data_structure)
    树的遍历

    展开全文
  • 数据结构结构详解

    千次阅读 2021-04-22 15:46:44
    是一种很特别的数据结构这种数据结构叫做“”就是因为它长得像一棵。但是这棵画成的图长得却是一棵倒着的,根在上,叶在下。 是图的一种,和图的区别就在于:是没有环的,而图是可以有环的。 ...

    树的定义

    树是一种很特别的数据结构,树这种数据结构叫做“树”就是因为它长得像一棵树。但是这棵树画成的图长得却是一棵倒着的树,根在上,叶在下。

    树是图的一种,树和图的区别就在于:树是没有环的,而图是可以有环的。

    树的百度定义如下:

    树状图是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

    结合图来看,可能会更好理解

    这就是一棵典型的二叉树

    而这里,2,3共有子节点5,那么上图就不是树了。

    和树有关的术语

    节点的度:一个节点含有的子树的个数称为该节点的度;

    叶节点:度为0的节点称为叶节点;

    分支节点:度不为0的节点;

    父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

    子节点:一个节点含有的子树的根节点称为该节点的子节点;

    兄弟节点:具有相同父节点的节点互称为兄弟节点;

    树的度:一棵树中,最大的节点的度称为树的度;

    节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

    树的高度或深度:树中节点的最大层次;

    堂兄弟节点:双亲在同一层的节点互为堂兄弟;

    节点的祖先:从根到该节点所经分支上的所有节点;

    子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

    森林:由m(m>=0)棵互不相交的树的集合称为森林;

    我们以图为样例来看:

    树的表现方法

    树一共有三种表现方法,分别是图像表现法、符号表现法和遍历表现法

    图像表现法

    图像表现法是所有的树的表现方法中最常见,也最简单的一种,由于上文已经详细介绍过,这里不做太多解释。

    符号表现法

    符号表现法没有其它两种方法那么常见,但是更为实用,特别是在比赛中输入时不能输入图片,那么可以用到符号表现法

    同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。如上文中的图就可以表现为;

    (1(2(6,7(14),8(15(19))),3(9(16)),4(10,11(17(20)),12),5(13(18(21)))))

    遍历表现法

    遍历表现法是二叉树特有的一种遍历,下面将会详细介绍:

    二叉树简介

    在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

    一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2(n+1)。深度为k的完全二叉树,至少有2k-1个节点,至多有2k-1个节点。

    ——百度百科

    特殊的二叉树

    上图为一棵普通的二叉树,既然这种二叉树是“普通”的,那么就有“特殊”的二叉树

    完全二叉树

    如果一个二叉树与满二叉树前m个节点的结构相同,这样的二叉树被称为完全二叉树

    下图就是一棵完全二叉树

    满二叉树

    满二叉树是“特殊中的特殊”,它属于完全二叉树中的一种,既然叫满二叉树,它就是满的二叉树,为什么这么讲呢?它的定义如下:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

    下图为一棵满二叉树

    二叉树的遍历

    回到二叉树的前序、中序、后序遍历。

    在正式开始讲之前,读者可以先记住下面一句话,然后在阅读的过程中比较这三种遍历的区别,就会理解得更加深刻了:

    前序遍历是中左右,中序遍历是左中右,后序遍历是左右中,所以这三种遍历的区别就是父亲节点什么时候访问

    前序遍历

    首先访问根,再先序遍历左子树,最后先序遍历右子树

    这句话凭空想象很难懂,我们可以借助图来理解。

    例如上图,我们按照前序遍历的方法,先遍历根节点,输出根节点的编号

    然后遍历根节点的左子树,输出左子树编号,然后重复此循环,直到遇到了叶节点

    这时候我们发现没有左子树了!怎么办呢?遇到叶子节点,我们就返回到它的父亲的循环,然后对它父亲的右子树进行访问

    结果发现它的父亲没有右子树!

    那么我们继续返回,因为叶子节点7的父亲6也是节点4的左孩子,所以我们继续返回,直到遇到了右子树为止

    我们访问到了第二个节点,终于遇到了有右子树的了,这是我们对右子树进行访问,并重复以上步骤,直到访问过所有的点为止。

    什么?你觉得这个访问步骤有些熟悉?没错,这和DFS(深度优先搜索)的访问步骤非常相似!

    现在读者应该明白了“前序遍历是中左右”的意思了,先访问中间的节点,即根节点(一般来说,在一个用图来表现的树中,将根节点放置与左右节点的中间的上方,所以形象地称为中节点,当然,读者也可以称为“根左右”),再访问左右子树。那么类似的,读者也应该明白了中序遍历和后序遍历了。

    中序遍历

    首先中序遍历左子树,再访问根,最后中序遍历右子树

    由于读者们看完前序遍历之后,应该懂得中序遍历是怎样的了,这里就不做和前序遍历一样详细的步骤了:

    首先,遍历根节点1的左子树2,发现2有左子树,那么就遍历2的左子树4,直到遇到了没有左子树的节点7,这时输出7

    遍历7的根节点6,输出。

    发现6没有右子树,那么我们遍历6的根节点4,输出

    节点4的根节点2有右子树,遍历节点2的右子树。

    重复以上循环直到所有点被访问完为止。

    特别提醒:在8和9的访问顺序中,读者可能有一些疑问:8没有左子树怎么办?8没有左子树,那么我们就到下一步,访问根节点,所以这时我们应该先访问8再访问9.

    后序遍历

    实际上,明白了前两种遍历后,读者应该可以自己遍历出后序遍历了,所以这里只给出树和后序遍历,供读者参考

    代码

    这里给出前序遍历、中序遍历和后序遍历的代码,比较容易理解,就不多解释

    先设置一个结构体来保存tree节点

    structTree

    {

    intdata; //节点值

    Tree *lchild ,*rchild; //分别为左孩子有孩子

    };

    前序遍历:

    voidpreorder_traversal(tree root)

    {

    if(root.data== NULL)

    return;

    printf( "%d", root.data);

    preorder_traversal(root.lchild);

    preorder_traversal(root.rchild);

    }

    中序遍历:

    voidinorder_traversal(tree root)

    {

    if(root.data== NULL)

    return;

    inorder_traversal(root.lchild);

    printf( "%d", root.data);

    inorder_traversal(root.rchild);

    }

    后序遍历:

    voidpostorder_traversal(tree root)

    {

    if(root.data== NULL)

    return;

    postorder_traversal(root.lchild);

    postorder_traversal(root.rchild);

    printf( "%d", root.data);

    }

    展开全文
  • 数据结构

    万次阅读 多人点赞 2018-11-20 01:25:14
    在计算器科学中,(英语:tree)是一种抽象数据类型或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“”是因为它...
  • 数据结构哈夫曼实验报告

    千次阅读 2021-12-05 23:11:53
    进一步理解哈夫曼的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力 要求:(1).假设文档内容从键盘输入; (2).设计哈夫曼算法的存储结构; (3).设计哈夫曼编码和解码算法; (4).分析使劲按...
  • mysql索引的数据结构什么

    千次阅读 2021-01-21 10:36:53
    一、简介mysql索引的数据结构,常用的存储引擎innodb采用的是B+Tree。这里对B+Tree及其相关的查找进行简要介绍。二、各种查找1、二叉排序(也称为二叉查找)二叉排序是最简单的查找,特点:a)是一棵...
  • 是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的称为空(null或empty)。一棵非空的包括一个根结点,还(很可能)有多个附加结点,所有结点构成一个多级分层结构。 文章...
  • 数据结构树(Tree)详解

    千次阅读 2021-03-30 13:29:23
    (tree)(Tree)的基本...是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的称为空(null或empty)。一棵非空的包括一个根结点,还(很可能)有多个附加结点,所有结点构成
  • 数据结构树高度_树数据结构的高度

    千次阅读 2020-07-11 04:34:52
    数据结构树高度In this tutorial, we’ll be discussing Binary Trees. We’ll see how to calculate the height of a tree data structure recursively as well as iteratively. 在本教程中,我们将讨论二叉树。 ...
  • 数据结构形结构

    千次阅读 2018-09-25 23:15:33
    的概念  由N(N&gt;=0)个节点组成的集合。对N &gt;...= m)又是一棵结构类似 的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继 因此,是递归定义的。 结...
  • 什么数据结构

    千次阅读 2019-06-19 20:25:39
    什么数据结构数据结构什么数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据...
  • 数据结构的深度/高度

    千次阅读 2020-09-16 16:21:48
    的深度/高度:从根结点开始往下数,叶子结点所在的最大层数称为的深度/高度。 的深度/高度涉及到结点的层数,有的教材规定根结点在第0层,有的则规定根结点在第1层。原理都是一样的,因教材而异。 / 根...
  • 数据结构--哈夫曼

    千次阅读 多人点赞 2022-03-03 21:32:43
    哈夫曼及其应用 1、哈夫曼的基本概念 路径:从中一个结点到另一个结点之间的分支构成这两个结点间的路径 结点的路径长度:两结点间路径上的分支数。 的路径长度:从树根到每一个结点的路径...
  • 数据结构——和森林

    千次阅读 多人点赞 2020-10-04 08:49:59
    是一种逻辑结构 是n个结点的有限集合,n=0时,称为空,任意的非空满足一下要求: 1)有且仅有一个特定的称为根的结点。 2)当n>1时,其余结点可分为m个互不相交的有限集合,其中每个集合本身又是一棵,...
  • 其实结构是平日里我们常见的一种数据结构,例如家族族谱、公司管理层级结构图等,这样的数据结构的存在一定有一定的道理。因此,在计算机领域中,结构也是会被广泛用到的,例如数据库系统中就有用到。那么本文就...
  • 数据结构图和的区别_和图数据结构之间的区别

    千次阅读 多人点赞 2020-09-14 04:43:21
    数据结构图和的区别In this tutorial you will learn about the difference between tree and graph. 在本教程中,您将了解和图之间的区别。 Both trees and graphs are two well known mostly used data ...
  • 数据结构 - 的分类

    千次阅读 2019-09-20 16:36:32
    根据分支的数量限制,可以将树结构分为两类: 二叉树:二叉树也就是一个节点只有两个子节点的树结构,比较有代表的如 红黑 多叉:多叉一个节点最少有两个子节点,根据不同的要求可以有多个子节点,典型...
  • 根据王道讲解和网上资料,总结的红黑相关知识点和考点。 可能考:红黑的性质、插入、删除(选择题,代码可能不考,略复杂) 二、红黑 (一)定义 1. 红黑是实质上是一棵自平衡的二叉查找,有时形态...
  • 数据结构的相关术语

    千次阅读 2021-01-01 19:26:15
    定义注释:从定义③可知,的定义蛮有趣的,中有中还是,所以可知的定义是一个递归定义,从下图可以看出,如果你仔细分析过带简单循环体的递归程序,那么会知道程序的整个运行路径其实...
  • c++数据结构

    千次阅读 2021-09-22 09:46:02
    的定义
  • 数据结构树和森林

    万次阅读 多人点赞 2018-09-25 17:37:54
    结构和主要概念,各种二叉树的结构及其特点; 二叉树的三种遍历方法的实现原理和性质,能将二叉树的遍历方法应用于求解二叉树的叶子结点个数、二叉树计数等问题,遍历的非递归实现方法; 线索化二叉树的结构和...
  • 什么数据结构什么是算法

    万次阅读 多人点赞 2018-05-04 00:35:22
    什么数据结构什么是算法? 呃呃呃呃 哎….不会。 多次参加了MOOC姥姥的数据结构,都没有坚持下来,希望这次可以坚持下来。 引用姥姥的例子:如果给你一堆书你会怎么放? 想怎么放就怎么放,哈哈。 如果书...
  • java 处理结构数据

    千次阅读 多人点赞 2022-07-31 10:40:19
    java 处理结构数据
  • 什么数据结构?对数据结构的理解

    千次阅读 多人点赞 2020-03-28 12:51:18
    数据结构 大学已逐渐进入尾声,想回顾一下自己专业所学的内容,看到数据结构这些概念,也总是记不住,理解也不是很深刻。想借助写下这些来加深一些印象吧。以下一些相关的内容,来自王道的数据结构讲解。 基本概念 ...
  • 【图解数据结构和二叉树全面总结(上)

    千次阅读 多人点赞 2022-01-01 14:21:39
    一、前言 学习目标: 重点: 难点: 二、的概念和定义 ...=0)个结点的有限集合,n=0,空 结点:表示中的元素... 的高度:中所有结点层次的最大值 森林:m(m>=0)棵互不相交的集合 例题: 求出..
  • MySQL中的索引的数据结构是 B+ 。 B+使用所有叶子结点作为数据页,它是一个双向链表,所有数据记录节点都是按照键值的大小存放在这里;使用非叶子结点作为索引页,记录着每页数据页的页号和该数据页中最小的主键...
  • 数据结构】:有序和无序

    千次阅读 2021-03-20 09:45:15
    其实有序和无序的概念很简单,我们来康康: 有序的定义:若将中每个结点的各子树看成是从左到右有次序的(即不能互换),则称该为有序(Ordered Tree) 无序的定义:若将中每个结点的各子树从左到右是...
  • 什么要学数据结构

    万次阅读 多人点赞 2019-11-19 09:45:23
    一、前言 在可视化化程序设计的今天,借助于...1) 能够熟练地选择和设计各种数据结构和算法 2) 至少要能够熟练地掌握一门程序设计语言 3) 熟知所涉及的相关应用领域的知识 其中,后两个条件比较容易实现,而第一个...
  • 数据结构之通用结构的实现

    千次阅读 2018-02-17 14:54:38
    大家都知道是非线性数据结构,显然我们无法用数组来表示的逻辑结构。那我们应该怎么办呢?通过什么来表示呢?其实可以设计结构体数组对结点间的关系进行表述。如下图所示:从上图发现,将根结点的双亲定义为-1,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 891,808
精华内容 356,723
热门标签
关键字:

数据结构全树是什么

数据结构 订阅