美工做任务网站,浙江政务服务网登录入口,什么是响应式网站设计,旅游景点推广策划方案1.树
树#xff08;Tree#xff09;非线性数据结构#xff0c;它是n#xff08;n≥0#xff09;个节点的有限集合#xff0c;它满足两个条件 #xff1a;
有且仅有一个特定的称为根#xff08;Root#xff09;的节点#xff1b;
其余的节点可以分为m#xff08;m…1.树
树Tree非线性数据结构它是nn≥0个节点的有限集合它满足两个条件
有且仅有一个特定的称为根Root的节点
其余的节点可以分为mm≥0个互不相交的有限集合T1、T2、……、Tm其中每一个集合又是一棵树并称为其根的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继 因此树是递归定义的。
树的表示方法 树形表示法、目录表示法。 一个节点的子树的个数称为该节点的度数。一棵树的度数是指该树中节点的最大度数。度数为零的节点称为树叶或终端节点。度数不为零的节点称为分支节点。除根节点外的分支节点称为内部节点。
森林
若树中每个节点的各个子树的排列为从左到右不能交换即兄弟之间是有序的则该树称为有序树。mm≥0棵互不相交的树的集合称为森林。树去掉根节点就成为森林森林加上一个新的根节点就成为树。 2.树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式 如双亲表示法孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子 兄弟表示法。
2.1兄弟表示法 typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
}; 2.2双亲表示法 3.二叉树
一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子 树和右子树的二叉树组成。
二叉树特点
每个结点最多有两棵子树即二叉树不存在度大于2的结点。二叉树的子树有左右之分其子树的次序不能颠倒。
3.1特殊的二叉树
3.1.1满二叉树 一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是(2^k) -1 则它就是满二叉树。
3.1.2完全二叉树 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。最后一层是连续的前面的k-1层为满的。 满二叉树是一种特殊的完全二叉树。完全二叉树度为1 的最多有一个。
3.2二叉树的性质
若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h- 1.(等比数列求和122^2...2^h)对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0n21.若规定根节点的层数为1具有n个结点的满二叉树的深度hLogN.
3.3二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
3.3.1顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树 会有空间的浪费。而现实中使用中只有堆才会使用数组来存储二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 在数组中: 父亲下标为i,左孩子下标为2*i1,右孩子下标为2*i2. 孩子下标为i,父亲下标为(i-1)/2.(不论是左还是右下标都为整数) 3.3.2链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的 方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩 子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链。 // 二叉链
struct BinaryTreeNode
{struct BinTreeNode* pLeft; // 指向当前节点左孩子struct BinTreeNode* pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode比特就业课
{struct BinTreeNode* pParent; // 指向当前节点的双亲struct BinTreeNode* pLeft; // 指向当前节点左孩子struct BinTreeNode* pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}
4.二叉树链式结构的实现
所谓遍历(Traversal)是指沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问。访 问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一是二叉树上进行 其它运算之基础。
4.1二叉树链式结构的遍历
前序/中序/后序的递归结构遍历是根据访问结点操作发生位置命名为深度优先。 NLR前序遍历(Preorder Traversal 亦称先序遍历)——根-左子树-右子树。 LNR中序遍历(Inorder Traversal)——左子树-根-右子树。LRN后序遍历(Postorder Traversal)——左子树-右子树-根。
由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
层序遍历设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。为广度优先。
typedef int BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
}BTNode;BTNode* BuyBTNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){printf(malloc fail\n);exit(-1);}node-data x;node-left node-right NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 BuyBTNode(1);BTNode* node2 BuyBTNode(2);BTNode* node3 BuyBTNode(3);BTNode* node4 BuyBTNode(4);BTNode* node5 BuyBTNode(5);BTNode* node6 BuyBTNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}
上述代码创建一个二叉树如下图所示 4.1.1前序遍历(A-B-D-NULL-C-F-G)
void PrevOrder(BTNode* root) {if (root NULL) {printf(NULL );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}
4.1.2中序遍历D-B-NULL-A-F-C-G
void InOrder(BTNode* root) {if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
4.1.3后序遍历 (D-NULL-B-F-G-C-A)
void PosOrder(BTNode* root) {if (root NULL){printf(NULL );return;}PosOrder(root-left);PosOrder(root-right);printf(%d , root-data);
}
4.1.4二叉树的结点个数
int BTreeSize(BTNode* root) {return root NULL ? 0 :BTreeSize(root-left) BTreeSize(root-right) 1;
}
4.1.5第k层的节点的个数k 1
int BTreeKLevelSize(BTNode* root, int k)
{assert(k 1);if (root NULL)return 0;if (k 1)return 1;return BTreeKLevelSize(root-left, k - 1) BTreeKLevelSize(root-right, k - 1);
}
4.1.6求二叉树的深度
int BTreeDepth(BTNode* root)
{if (root NULL)return 0;int leftDepth BTreeDepth(root-left);int rightDepth BTreeDepth(root-right);return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}
4.1.7二叉树查找值为x的结点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 BTreeFind(root-left, x);if (ret1)return ret1;//return BTreeFind(root-right, x);BTNode* ret2 BTreeFind(root-right, x);if (ret2)return ret2;return NULL;
}
4.1.8二叉树销毁
void BTreeDestory(BTNode* root)
{if (root NULL){return;}BTreeDestory(root-left);BTreeDestory(root-right);free(root);
}
4.1.9层序遍历(需要队列进行入队和出队)
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}printf(\n);QueueDestory(q);
}
4.1.10判断二叉树是否是完全二叉树
// 判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL)break;QueuePush(q, front-left);QueuePush(q, front-right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 空后面出到非空那么说明不是完全二叉树if (front){QueueDestory(q);return false;}}QueueDestory(q);return true;
}
