网站建设如何创建框架页面陕西省城乡建设网站

网站建设如何创建框架页面,陕西省城乡建设网站,中小企业网站建设论文,全国十大网络公司二叉树基本概念及遍历 1、基本概念 二叉树是一种特殊的树形数据结构#xff0c;其中每个节点最多有两个子节点#xff0c;通常称为左子节点和右子节点。它是非线性数据结构中最基础、最重要的一种。 2、核心特征 2.1. 结构特性 每个节点最多有两个子节点#xff08;0个、1个…二叉树基本概念及遍历1、基本概念二叉树是一种特殊的树形数据结构其中每个节点最多有两个子节点通常称为左子节点和右子节点。它是非线性数据结构中最基础、最重要的一种。2、核心特征2.1.结构特性每个节点最多有两个子节点0个、1个或2个子节点有明确顺序左子节点和右子节点顺序不可互换第 i 层最多有2^(i-1)个节点高度为 h 的二叉树最多有2^h - 1个节点2.2.基本性质设 n 为节点总数n₀ 为叶子节点数n₁ 为度为1的节点数n₂ 为度为2的节点数度即是分支数量n n₀ n₁ n₂n₀ n₂ 1推导从节点到子节点的边数 0*n₀ 1*n₁ 2*n₂ n₁ 2n₂ 从子节点到父节点的边数 n - 1因为根节点没有父节点 n₁ 2n₂ n - 1 得n₀ n₂ 13、相关名词3.1.节点相关根节点没有父节点的节点树的起点内部节点至少有一个子节点的节点叶子节点没有子节点的节点度为0父节点直接上级节点子节点直接下级节点3.2.遍历相关前序遍历根 → 左 → 右中序遍历左 → 根 → 右后序遍历左 → 右 → 根层序遍历按层次从上到下、从左到右4、二叉树的基础类型4.1.满二叉树定义每个节点都有0个或2个子节点特征没有度为1的节点叶子节点数 内部节点数 11 / \ 2 3 / \ 4 54.2.完全二叉树定义除最后一层外其他层都完全填满最后一层从左到右填充不能间断特点可以用数组高效存储第 i 个节点的左子节点2i右子节点2i1父节点⌊i/2⌋编号一般从1开始如果从0开始公式相应改变1 / \ 2 3 / \ / 4 5 64.3.完美二叉树定义所有叶子节点都在同一层每个内部节点都有两个子节点属于特殊的满二叉树1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \/ \ / \ 8 9 10111213 144.4.平衡二叉树定义任意节点的左右子树高度差不超过1高度的定义从该节点到最远叶子节点的最长路径的边数1 / \ 2 3 / \ 错误示范“1”节点左右子数高度差超过1 4 5 \ 64.5.二叉搜索树性质对于任意节点左子树所有节点值 当前节点值右子树所有节点值 当前节点值中序遍历得到有序序列8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 135.普通二叉树的实现链表实现5.1.结构定义typedefstructTreeNode{intdata;// 节点数据structTreeNode*left;// 左子树指针structTreeNode*right;// 右子树指针}TreeNode;typedefstructBinaryTree{TreeNode*root;// 根节点指针intsize;// 节点总数}BinaryTree;5.2.基本操作创建树的节点树的结构TreeNode*createNode(intdata){//节点TreeNode*newNode(TreeNode*)malloc(sizeof(TreeNode));if(newNodeNULL){printf(内存分配失败);exit(1);}newNode-datadata;newNode-leftNULL;newNode-rightNULL;returnnewNode;}BinaryTree*createBinaryTree(){BinaryTree*tree(BinaryTree*)malloc(sizeof(BinaryTree));if(treeNULL){printf(内存分配失败);exit(1);}tree-rootNULL;tree-size0;returntree;}插入与删除节点对于普通二叉树一般只是先提前构建好二叉树之后进行只读操作。大多不进行删除插入。但如果要插入删除的话和链表也差不多根据相应的编号或位置遍历然后进行相关的链表操作。//先遍历找到对应节点n1,n2遍历后面说TreeNode*newcreatNode(0);//在n1与n2间插入节点P0n1-leftnew;new-leftn2;//删除节点Pn1-leftn2;free(P);遍历1.递归深度优先1 / \ 2 3 / \ / \ 4 5 6 7二叉树的前序中序后序遍历前序根 - 左 - 右即1245367.中序左 - 根 - 右即4251637.后序左 - 右 - 根即4526731.voidpreorderTraversal(TreeNode*root){// 前序遍历根 - 左 - 右if(rootNULL){return;}printf(%d ,root-data);// 访问根节点preorderTraversal(root-left);// 遍历左子树preorderTraversal(root-right);// 遍历右子树}voidinorderTraversal(TreeNode*root){// 中序遍历左 - 根 - 右if(rootNULL){return;}inorderTraversal(root-left);printf(%d ,root-data);inorderTraversal(root-right);}voidpostorderTraversal(TreeNode*root){// 后序遍历左 - 右 - 根if(rootNULL){return;}postorderTraversal(root-left);postorderTraversal(root-right);printf(%d ,root-data);}例题力扣144. 二叉树的前序遍历给你二叉树的根节点 root 返回它节点值的 前序 遍历。示例输入root [1,2,3,4,5,null,8,null,null,6,7,9]输出[1,2,4,5,6,7,3,8,9]思路先计算总节点方便之后分配数组再通过前序遍历将节点按固定顺序放入数组中。代码intgetNodeCount(structTreeNode*root){if(rootNULL)return0;return1getNodeCount(root-left)getNodeCount(root-right);}voidpreorder(structTreeNode*root,int*result,int*index){if(rootNULL)return;result[(*index)]root-val;preorder(root-left,result,index);preorder(root-right,result,index);}int*preorderTraversal(structTreeNode*root,int*returnSize){*returnSizegetNodeCount(root);int*result(int*)malloc(sizeof(int)*(*returnSize));if(resultNULL){*returnSize0;returnNULL;}intindex0;preorder(root,result,index);returnresult;}2.使用队列广度优先1 / \ 2 3 / \ / \ 4 5 6 7遍历得到1234567.思路第1步根节点1入队队列[1]第2步队首1出队访问1把1的子节点2和3入队访问1 队列[2, 3]第3步队首2出队访问2把2的子节点4和5入队访问1 2 队列[3, 4, 5]第4步队首3出队访问3把3的子节点6和7入队访问1 2 3 队列[4, 5, 6, 7]第5步队首4出队访问44没有子节点访问1 2 3 4 队列[5, 6, 7]第6步队首5出队访问55没有子节点访问1 2 3 4 5 队列[6, 7]第7步队首6出队访问66没有子节点访问1 2 3 4 5 6 队列[7]第8步队首7出队访问77没有子节点访问1 2 3 4 5 6 7 队列[空]队列相关实现typedefstructQueue{// 定义队列结构TreeNode**array;intfront;intrear;intcapacity;}Queue;Queue*createQueue(intcapacity){//创建队列Queue*queue(Queue*)malloc(sizeof(Queue));queue-array(TreeNode**)malloc(sizeof(TreeNode*)*capacity);queue-front0;queue-rear0;queue-capacitycapacity;returnqueue;}voidenqueue(Queue*queue,TreeNode*node){//将二叉树节点放入队列if((queue-rear1)%queue-capacityqueue-front){return;}queue-array[queue-rear]node;queue-rear(queue-rear1)%queue-capacity;}TreeNode*dequeue(Queue*queue){//出队列if(queue-frontqueue-rear){returnNULL;}TreeNode*nodequeue-array[queue-front];queue-front(queue-front1)%queue-capacity;returnnode;}intisQueueEmpty(Queue*queue){//判断为空returnqueue-frontqueue-rear;}开始遍历voidlevelOrderTraversal(TreeNode*root){if(rootNULL){return;}Queue*queuecreateQueue(100);enqueue(queue,root);while(!isQueueEmpty(queue)){TreeNode*nodedequeue(queue);printf(%d ,node-data);if(node-left)enqueue(queue,node-left);if(node-right)enqueue(queue,node-right);}printf(\n);free(queue-array);free(queue);}二叉树优点层次清晰天然适合递归算法平衡二叉树搜索效率高因为使用链表所以内存运用效率高操作多样前中后序遍历广度优先遍历