精华内容
下载资源
问答
  • 在计算机科学中,二叉树是每个结点最多两个子树树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树用于实现二叉查找树和二叉堆。 ![在这里插入图片描述]...

    一、二叉树

    1.定义(百度):

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

    在这里插入图片描述

    2.二叉树的特点

    二叉的分类很多,特性也不少。这里不准备细说。
    1)二叉树只有一个根节点
    2)二叉树的每个节点会有两个孩子。分为左孩子、右孩子。两个还是不一定必须拥有。

    二、二叉树的生成

    1.二叉树数据结构实现

    二叉树可以看成每个节点的组成,那么这个节点要有存储数据的地方,要有指向左右孩子的指针。
    所以可以这样生成:

    typedef struct B_TREE {
    	USER_TYPE data;//用户自定义数据类型
    	struct B_TREE *left;//指向左孩子
    	struct B_TREE *right;//指向右孩子
    }B_TREE;
    

    2.二叉树数据的表示

    1. 给每个节点标上序号,但是需要完全二叉树才能将每个节点位置表示清楚。所以容易造成空间浪费。

    在这里插入图片描述
    2. 父节点(左孩子,右孩子)模式
    上面的二叉可以这样表述为: A(B, O(M( ,C))
    这种方式比较节省空间,但是也让处理该二叉树麻烦起来。因为我们加入了左右括号和逗号,使得识别难度增加了。
    该模式有 “字符”,‘’左括号‘,“右括号”,“逗号”’
    接下来分析一下该模式的各个状态:
    加粗样式
    最后我们生成一个自动状态变迁图
    在这里插入图片描述
    依照这个图我们开始编码:

    #define B_TREE_STATUS_START			1    //开始状态
    #define B_TREE_STATUS_ROOT			2    //根状态
    #define B_TREE_STATUS_LEFTBRACKET	3    //左括号状态
    #define B_TREE_STATUS_RIGHTBRACKET	4    //右括号状态
    #define B_TREE_STATUS_ALPHA			5    //字母状态
    #define B_TREE_STATUS_COMMA			6    //逗号状态
    #define B_TREE_STATUS_END			7    //结束状态
    

    状态的判定:

    	while (arg.ok && !arg.finished) {
    		arg.index += skipBlank(str + arg.index);//跳过空格
    		switch (arg.status) {
    			case B_TREE_STATUS_START:
    				dealBTreeStart(&arg, str[arg.index]);
    			break;
    			case B_TREE_STATUS_ROOT:
    				dealBTreeRoot(&arg, str[arg.index]);
    			break;
    			case B_TREE_STATUS_LEFTBRACKET:
    				dealBTreeLeftbracket(&arg, str[arg.index]);
    			break;
    			case B_TREE_STATUS_RIGHTBRACKET:
    				dealBTreeRightbracket(&arg, str[arg.index]);
    			break;
    			case B_TREE_STATUS_ALPHA:
    				dealBTreeAlpha(&arg, str[arg.index]);
    			break;
    			case B_TREE_STATUS_COMMA:
    				dealBTreeComma(&arg, str[arg.index]);
    			break;
    			case B_TREE_STATUS_END:
    				if (arg.bracketMatch != 0) {
    					errMess = "括号不匹配!";
    					arg.ok = FALSE;
    					break;	// 这个break;用来跳出switch
    					// 这个break;不是用来结束循环的!
    				}
    				
    				*root = arg.root;
    				arg.finished = TRUE;
    			break;
    			default:
    			break;
    		}
    	}
    

    状态的转换:

    //开始状态
    static void dealBTreeStart(B_TREE_ARG *arg, int ch) {
    	if (isalpha(ch)) {
    		dealRoot(arg, ch);//进入根状态
    	} else {
    		errMess = "不能是空树!";
    		arg->ok = FALSE;//错误
    	}
    }
    
    //解决根状态
    static void dealRoot(B_TREE_ARG *arg, int ch) {
    	arg->node = arg->root = createNode(ch);
    
    	arg->status = B_TREE_STATUS_ROOT;//转换到根状态,记录下来。
    	arg->index++;//为判断下个字符检测
    }
    

    基本思路: 原状态(已知) --> 判断字符类型 – > 处理该字符 --> 转换原状态 --> 进入下一个字符
    其它各状态略!

    3.二叉树生成

    从上面的自动转态变迁图,我们知道了如何处理用户给予的二叉树数据表达形式。那么我们怎么生成二叉树呢?
    二叉树难的地方就是,怎么将各个节点连接起来?谁是左孩子?谁是右孩子?

    A(B(D(F, G), J(, L(K, ))), C(E(H,I)))
    

    观察这个你发现了啥?
    1.区别左右孩子的标志是“逗号”。逗号后面的数据一定是右孩子。
    2.字符后面的有左括号,那么该字符一定有孩子。

    那么怎么确认每个节点的父节点呢?
    我们这里采用堆栈空间存储每个父节点。
    A,是父节点,入栈,B是父节点,入栈,D是父节点,入栈;当前栈内: 底,ABD,顶
    G是右孩子,且后面是右括号,父节点D出栈;当前栈内: 底,AB,顶
    J是父节点,入栈,L是父节点,入栈;当前栈内: 底,ABJL,顶
    L孩子遍历结束,出栈,J孩子遍历结束,出栈,B孩子遍历结束,出栈;当前栈内: 底,A,顶

    就这样,实现父节点的寻找。尤其我们创造过一种堆栈工具。正好可以使用。数据结构与算法 & 堆栈工具

    再结合上述发现,就能很好生成一个二叉树了。

    static B_TREE *createNode(int ch) {
    	B_TREE *node = NULL;
    
    	node = (B_TREE *) calloc(sizeof(B_TREE), 1);
    	// 为了节省时间,这里不处理申请空间失败的问题。
    	node->data = ch;
    	node->left = node->right = NULL;
    
    	return node;
    }
    
    static void dealNode(B_TREE_ARG *arg, int ch) {
    	B_TREE *parent;
    
    	arg->node = createNode(ch);
    	// 找到其父节点,将node置位父的左、右孩子
    	parent = (B_TREE *) readTop(arg->stack);
    	if (LEFT_CHILD == arg->whichChild) {
    		parent->left = arg->node;
    	} else {
    		if (NULL != parent->right) {
    			free(arg->node);
    			errMess = "二叉树不存在第三个子节点!";
    			arg->ok = FALSE;
    			return;
    		}
    		parent->right = arg->node;
    	}
    
    	arg->status = B_TREE_STATUS_ALPHA;
    	arg->index++;
    }
    

    注意: 这里有一个堆栈空间的容量申请问题。
    可以简单处理为用户输入数据长度;也可以遍历字符,找到括号匹配数目,确定容量。

    三、二叉树遍历与获得树高

    1.二叉树遍历

    1. 先根序遍历 :根,左孩子,右孩子
    2. 中根序遍历:左孩子, 根,右孩子
    3. 后根序遍历 :左孩子,右孩子, 根

    简单来说,就是将二叉树看成一个多个左右子二叉树组合。
    实现思路:就是递归了。

    简单介绍先根序,代码如下:

    //先根遍历
    void firstRootVisit(const B_TREE *root) {
    	if (NULL == root) {
    		return;
    	}
    	printf("%c ", root->data);
    	firstRootVisit(root->left);
    	firstRootVisit(root->right);
    }
    

    在这里插入图片描述
    F1,输出A,向左孩子走;调用F2,输出B,向左孩子走;调用F3,输出D,向左孩子走;调用F4,输出F,向左孩子走;
    调用F5,root 为0,(黑线),退回到F4,向右孩子走;调用F6,root 为0,(黑线),退回到F3,
    向右孩子走;调用F7,输出G,等等

    //中根遍历
    void middleRootVisit(const B_TREE *root) {
    	if (NULL == root) {
    		return;
    	}
    	middleRootVisit(root->left);
    	printf("%c ", root->data);
    	middleRootVisit(root->right);
    }
    //后跟遍历
    void lastRootVisit(const B_TREE *root) {
    	if (NULL == root) {
    		return;
    	}
    	lastRootVisit(root->left);
    	lastRootVisit(root->right);
    	printf("%c ", root->data);
    }
    

    2.二叉树获得树高

    基本思路:
    1.遍历
    2.记录当前递归深度。
    3.比较每次最深深度
    4.返回最深深度
    我们知道,递归调用时,每调用一次,是深入一层,返回时仍是当初深度。但是如何比较每次深入的最大深度呢?
    使用静态存储变量。

    //树深
    static int treeDeep(const B_TREE *root, int level) {
    	static int maxLevel = 0;//保存最大深度
    
    	if (root == NULL) {
    		return maxLevel;//结束
    	}
    	maxLevel = maxLevel < level ? level : maxLevel;//当前深度和最大深度比较
    	treeDeep(root->left, level + 1);//向左孩子方向,进入下一深度
    	treeDeep(root->right, level + 1);//向右孩子方向,进入下一深度
    
    	return maxLevel;
    }
    //最大数深
    int getTreeDeep(const B_TREE *root) {
    	return treeDeep(root, 1);
    }
    

    四、总结

    1.编程需要考虑长远性。工具终会使用。
    2.递归很巧妙。一定要多分析,从而掌握。
    3.灵活多变,不拘泥·。


    笔者水平有限,目前只能描述以上问题,如果有其他情况,可以留言,有错误,请指教,有继续优化的,请分享,谢谢!
    本篇文章是否有所收获?阅读是否舒服?又什么改进建议?希望可以给我留言或私信,您的的分享,就是我的进步。谢谢。


    完整代码有点长,准备弄个文档。或链接。

    2020年03.18 家

    展开全文
  • 2.1 算法的概念 21 2.2 简单算法举例 21 2.3 算法的特性 24 2.4 怎样表示一个算法 24 2.4.1 用自然语言表示算法 24 2.4.2 用流程图表示算法 24 2.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 ...
  • A.RSA 算法可用于某种数字签名方案 B.RSA 算法的运算速度比 DES 慢 C.RSA 算法是一种对称加密算法 D.RSA 的安全性主要基于素因子分解的难度 分组密码多个工作模式,它们也对保密安全性影响很大,其中,只能...
  • 它还提供了高效通用算法库,这些算法用于STL容器,也可用于常规数组。模板类 valarray为数值数组提供了支持。 第17章:输入、输出和文件 本章复习C++ I/O,并讨论如何格式化输出。读者将要学习如何使用类...
  • 它还提供了高效通用算法库,这些算法用于STL容器,也可用于常规数组。模板类 valarray为数值数组提供了支持。 第17章:输入、输出和文件 本章复习C++ I/O,并讨论如何格式化输出。读者将要学习如何使用类...
  • 它还提供了高效通用算法库,这些算法用于STL容器,也可用于常规数组。模板类 valarray为数值数组提供了支持。 第17章:输入、输出和文件 本章复习C++ I/O,并讨论如何格式化输出。读者将要学习如何使用类...
  • A) 作为需求分析阶段用户与开发者之间交流信息的工具 B) 对系统的数据结构进行描述 C) 对目标系统的层次结构进行描述 D) 作为分析和设计的工具 8. 数据字典是数据流图中所有元素的定义的集合,一般由以下四类...
  • 操作系统(内存管理)

    热门讨论 2009-09-20 12:55:25
    以下是该算法的略述: 清单 5. 主分配程序的伪代码 1. If our allocator has not been initialized, initialize it. 2. Add sizeof(struct mem_control_block) to the size requested. 3. start at managed_...
  • 算法这部分内容非常重要,如果你不知道如何学习算法的话,可以看下我写的: 算法学习书籍+资源推荐 。 如何刷Leetcode? 常见算法问题总结: 几道常见的字符串算法题总结 几道常见的链表算法题总结 剑指 offer ...
  • 算法这部分内容非常重要,如果你不知道如何学习算法的话,可以看下我写的: 算法学习书籍+资源推荐 。 如何刷Leetcode? 常见算法问题总结: 几道常见的字符串算法题总结 几道常见的链表算法题总结 剑指 offer ...
  • 算法这部分内容非常重要,如果你不知道如何学习算法的话,可以看下我写的: 算法学习书籍+资源推荐 。 如何刷Leetcode? 常见算法问题总结: 几道常见的字符串算法题总结 几道常见的链表算法题总结 剑指 offer ...
  • 本版本是高清版,是第1版第18次印刷,是书签最全最好版本。 基本信息 原书名: The C++ Programming ...16.2.2 基类容器 388 16.2.3 stl容器 391 16.3 向量 392 16.3.1 类型 393 16.3.2 迭代器 394 16.3.3...
  • 提供是本书课后习题源代码,也就是《C++程序设计语言(特别版)题解》源代码。非书中源代码。 本版本是高清版,是第1版第18次印刷,是书签最全最好版本。 基本信息 原书名: The C++ ...16.2.2 基类...
  • 其自古以来 一直是作为 理性探讨真理性和严谨性的一种范型,并作为 其他科学(特别是物理学)的工具,甚至是基础。在19世纪中,数学的 趋于更高抽象的 许多开发,带来了新的挑战和悖论,迫切需要对数学真理的本性和准则...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    31 习题9 排序------------------------------------------------------------------------------------34 第1部分 C++基本知识 各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学...
  • C++程序设计语言(特别版)--源代码

    热门讨论 2012-04-23 07:33:51
    提供是书中源代码,非课后练习源代码。 本版本是高清版,是第1版第18次印刷,是书签最全最好版本。 基本信息 原书名: The C++ Programming ...16.2.2 基类容器 388 16.2.3 stl容器 391 16.3 向量 392...
  • c语言编写单片机技巧

    2009-04-19 12:15:17
    答:对于复杂而开发时间紧项目时,可以采用C语言,但前提是要求对该MCU系统C语言和C编译器非常熟悉,特别要注意该C编译系统所能支持数据类型和算法。虽然C语言是最普遍一种高级语言,但不同MCU厂家其...
  • 如前所述,被映射内存边界(最后一个有效地址)被称为系统中断点或者当前中断点。在很多 UNIX? 系统中,为了指出当前系统中断点,必须使用 sbrk(0) 函数。sbrk 根据参数中给出字节数移动当前系统中断点,...
  • 声明方法存在而不去实现它类被叫做抽象类(abstract class),它用于要创建一个体现某些基本行为类,并为该类声明方法,但不能在该类中实现该类情况。不能创建abstract 类实例。然而可以创建一个变量,其...
  • 八、 常用的工具  Sql Plus  Sql Developer  Oracle Enterprise Manager   第二章 用户和权限 一、 用户介绍 ORACLE用户是学习ORACLE数据库中的基础知识,下面就介绍下类系统常用的默认ORACLE用户: 1. ...

空空如也

空空如也

1 2
收藏数 21
精华内容 8
关键字:

常用于描述算法的工具有