数据结构树与二叉树详细解析

1、1.树二叉树遍历的概念引出了二叉树和森林哈夫曼树。第四章树和二叉树。2.树形结构是一种广泛使用的非线性结构。例如：管理组织、磁盘目录、家谱等。3。磁盘目录，4。树木和森林的概念。树的定义树是由n (n 0)个节点组成的有限集合。如果n=0，它被称为空树。如果n为0，则有一个特定的节点称为根，它只有直接后继，但没有直接前驱；除了根之外的其他节点被分成m(m 0)个不相交的有限集合t0，t1，TM-1，并且每个集合是一棵树，这被称为根的子树。5、树特征，每个子树的根节点都有一个且只有一个直接的前置节点，但可以有0个或更多的直接后续节点。，A，C，G，B，D，E，F，K，L，H，M，I，J，6，例5

2、.1: Tree=(D，R) D=Book，C1，C2，C3，C3，Tree是一个层次结构。7.基本术语：主要来自家谱和树木。父母，孩子：如果R，据说A是B and B的父母，是A的孩子；节点度：节点拥有的子节点数；叶：0度的节点；分支节点：度数大于0的节点；树的度：树的最大节点度；8，节点所在的层：根在第一层，其他节点所在的层是它的父层，加1；深度或高度：节点所在层的最大层数；兄弟：父母相同的节点称为兄弟；表亲：父母双方在同一个层面上称对方为非兄弟节点上的表亲；9，祖先：节点是其所有子树中节点的祖先，这些节点是其后代；路径：它是节点序列n1、N2、n3、NK，前一个节点是后一个节点的父节点；

3、它的长度是k-1；有序树：每个节点的子节点从左到右依次排列；否则它就是一棵乱树；10，节点A、b和c的度数分别是3、2和1，叶是k、l、F、G、m、I和j，节点A的子节点是b、c和d，节点b的子节点是e和F，节点I的父节点是d，节点l的父节点是e，节点b、c和e。节点A是节点F、G、11的祖先，是33，360m(m 0)不相交树的集合。12、二叉树、五种不同形式的二叉树、13和属性1。如果二叉树的级别从1开始，那么二叉树的I级最多有2i -1。(1)通过数学归纳法证明了深度为k的二叉树最多有2k-1个节点。(h 1)证明对于任何二叉树，如果有n0个叶节点和n2个非叶节点的度为2，那么就有n0n

4、21来证明如果有n1个节点的度为1，汇总点数为n，边的总数为e，根据二叉树的定义，n=n0n 1n 2e=2n n1=n-1。因此，有2n2n 1=n0n 1 N2-1n 2=n0-1n 0=n21，15。定义1个完整二叉树和2个完整二叉树。如果二叉树的高度是h，则有h 1层。除了h层，其他层(0 h-1)的节点数都达到最大，h层从右到左连续缺少几个节点，是一个完整的二叉树。(功能)，16，叶节点只出现在两个最大的级别。对于任何节点，如果它的右子树的高度是L，那么它的左子树的高度是L或1，17，并且在属性4中具有n (n 0)个节点的完整二叉树的高度是log2(n 1) -1。证明了完全二叉树

5、的高度为H，则2h-1 n 2h 1-1是变形的2h n 1 2h 1取log2 (n 1) h 1有log2(n 1)=h 1 h=log2(n 1) -1，并且H层上层的节点数，包括H层的最大节点数，18，性质5，如把一个完全二叉树从上到下放n个节点， 如果在同一层中节点从左到右连续编号为0、1、2和n-1，则存在以下关系：如果i=0，则我没有父母，则我的父母是(i -1)/2，如果2*i 1 n，则我的左孩子是2*i 1，如果2*i 2 n，则我的右孩子是2 * i2if=0，则它的左兄弟是i -1，如果我是奇数，则我！=n-1，那么它的右兄弟是i 1。节点I的级别是log2(i 1)，

6、19，这是一个二叉树的抽象数据类型。数据是一组有限的节点。当D不为空时，有一个节点T，其他节点被分成T的左子树和右子树。操作构造器进程：建立一个空的二叉树。删除进程：删除二叉树，20，空进程：判断二叉树是否为空。如果二叉树为空，输出：返回真。否则，返回false Size进程：计算二叉树的节点数大小输出：大小高度进程：计算二叉树的高度高度输出：高度根进程：取二叉树的根节点值x Output333。60个根节点x，21，Parent Input:节点的值是二叉树中的一个节点。进程：找到节点的父p。如果节点是根，P为空，输出：p创建二进制树输入：一个定义进程：根据这个定义构造一个二叉树，生成树输入

7、：数据是根节点值，左是左子树，右是右子树进程：创建的二叉树，数据是根节点值，左是其左子树，右是其右子树，22，BreakTree进程3360拆分二叉树，数据是根节点数据，左右是右子树输出：数据，左、右是前序输入：访问()是节点访问函数Process:它调用Visit()一次，根据Visit()对二叉树中的每个节点只调用一次。 按照前序遍历序列得到的结果是，节点访问函数Process:调用visit()一次，根据Visit()对二叉树中的每个节点只调用一次，按照中间顺序遍历序列得到的结果是23。Postorderinput3360Visit()是节点访问函数Process:调用Visit()一次

8、，根据visit()对二叉树中的每个节点只调用一次。遍历序列得到结果等级顺序输入：访问()是节点访问函数进程：根据访问()对二叉树中的每个节点调用一次访问()并且只调用一次，然后遍历序列得到结果。/二叉树，24，一个完整的二叉树通常由二叉树的序列来表示。25.在极端情况下：只有正确的单个二叉树，26。二叉树链表，27。二叉树链表，28。二叉树链表的例子。二叉树的二进制链表。二进制链表中的节点定义如下：二进制绿色节点*左子节点，*右子节点；/左指针，右指针public:二叉树节点(datatype/二叉树节点，二叉树的链表实现，30，类二叉树二叉树二叉树节点*根；/根节点指针public:二叉树

9、()根=null/创建一个空的二叉树bool IsEmpty()；/如果二叉树为空，返回真；否则，返回false bool Root(DataType /通过扩展二叉树的遍历序列来创建二叉树。二进制链表的定义如下：31，空生成树(DataType /逐层遍历，/其中访问是遍历的过程参数，负责访问节点。，32，void delete(二叉树节点*，33，boolroot(datatype/创建一个新的二叉树，34，遍历二叉树，遍历二叉树是以一定的顺序访问树中的节点，要求每个节点只访问一次。假设访问根节点表示为V，遍历根的左子树表示为L，遍历根的右子树表示为R，35，可能的遍历顺序，前序VLR镜像

10、LVR镜像RVL后序LRV镜像RLV，36，以及前序遍历：如果BT不为空，则为：1。访问根；2.遍历序言中的左子树；3.按照前面的顺序遍历右子树；中间顺序遍历：如果BT不为空，则为：1。左子树的中间顺序遍历；2.访问根3。以中间顺序遍历右子树；后序遍历：如果BT不是空的，那么：1。左子树的后序遍历；2.依次遍历右子树；3.访问根，遍历算法，37。遍历结果的遍历顺序：a b * c-d-e/f前言：-a * b-c d/e f后置：a b c d-* e f/-，38，练习3360，给出二叉树的前序、中序和后序的遍历顺序。前言遍历序列：ABDGCEFH中序遍历序列：DGBAECHF逆序遍历序列：

11、GDBEHFCA，39，二叉树递归算法的前缀遍历空二叉树：3360的前序(二叉树节点*，40，二叉树递归空二叉树：的中序遍历算法的顺序(二叉树节点*，41)，后序遍历算法的空二叉树33603360的后序(二叉树节点*，42)，计算二叉树的节点数int Size (BinaryTreeNode *，二叉树遍历的一个例子，43)，int Depth (BinaryTreeNode *，通过使用二叉树的顺序遍历计算二叉树的高度，44，并递归地构建二叉树。 递归退出：当遇到时，它是空的。建立一个根节点。建立左子树和右子树。二叉树用根字符序列和左右子树的字符序列表示，而空树用空格(或某个字符)表示。例如

12、，“或“-1”用于表示字符序列或正整数序列的空节点。二叉树是通过二叉树的预序遍历建立的，45。如图所示，二叉树的前序遍历序列是A B C D E G F序列，它是扩展二叉树的前序遍历序列。是一个扩展的叶节点，它表示一个空指针。，46，建立二叉树的算法(二进制链表):无效创建二进制树(二进制树节点*创建二进制树，47，遍历二叉树的非递归算法，让我们首先观察三种路径预遍历。，否则：将顶部元素堆叠成p；拜访p。p指的是正确的孩子；4.结束，52。思考：非递归序遍历算法？中序遍历二叉树算法思想：建立栈；p指向根；当p不为空或堆栈不为空时重复：如果p不为空，则p被放入堆栈；p指向左边的孩子；否则：将顶部

13、元素堆叠成p；拜访p。p指的是正确的孩子；4.最后，序言中遍历二叉树的非递归算法思想：建立栈；p指向根；当p不为空或堆栈不为空时，重复执行：如果p不为空，访问p并将其放在堆栈上；p指向左边的孩子；否则：将顶部元素堆叠成p；p指的是正确的孩子；结束，53，例如，堆栈堆栈；/在(p |！堆栈。IsEmpty()而(p)堆栈。推动(p)。coutp-数据；p=p-LeftChild；/向左走，否则p=stack。pop()；p=p-right child；/向右/当/InOrder，76时，算法思想是非递归的，然后遍历。1.建立栈栈；2.p指向根；3.当P不为空或堆栈不为空时重复：如果P不为空：(P，L)堆栈；向左走一步；否则：将顶部元素堆叠成p和标记；如果标签=R :访问p