【数据结构】二叉树相关概念与功能实现

1.树的概念及结构定义树是一种非线性数据结构由nn0个有限结点组成一个具有层次关系的集合。根节点没有前驱节点其余结点被分成M(M0)个互不相交的集合其中每一棵结构与树类似的子树。树是递归定义的。结点的度一个结点含有的子树的个数称为该结点的度 如上图A的度为6叶结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I...等结点为叶结点非终端结点或分支结点度不为0的结点 如上图D、E、F、G...等结点为分支结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点树的度一棵树中最大的结点的度称为树的度 如上图树的度为6结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为4堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树的集合称为森林2.二叉树概念及结构2.1概念二叉树的结点是个有限集合该集合1.或者为空2.由一个节点和两棵分别为左子树和右子树的二叉树组成​从上图可以看出1. 二叉树不存在度大于2的结点2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树注意对于任意的二叉树都是由以下几种情况复合而成的​2.2特殊的二叉树1.满二叉树二叉树每层的结点都达到最大值除叶子结点外的结点度都为22.完全二叉树是一种特殊的二叉树、1除最后一层叶子结点可以不填满其它层必须填满2最后一层的结点只能靠左挤不可以右边有中间空​2.3 二叉树的性质1. 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点2. 若规定根结点的层数为1则深度为h的二叉树的最大结点数是2^i-13. 对任何一棵二叉树,如果度为0其叶结点个数为n₀ , 度为2的分支结点个数为 n₂,则有n₀ n₂ 14. 若规定根结点的层数为1具有n个结点的满二叉树的深度hlog₂n15.完全二叉树有n个结点按从上至下从左至右的数组顺序对所有结点从0开始编号用下标表示父子关系1设父亲在数组中的下标为i左孩子在数组中下标为2*i1左孩子在数组中下标为2*i22设孩子在数组中下标为j父亲在数组中下标j-1/22.4二叉树的存储结构1顺序储存只适合完全二叉树用数组原因之一是没有空间浪费。2链式储存用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。注堆是顺序储存的一种3.二叉树相关功能实现3.1定义结点//定义结点 typedef int BTDataType; typedef struct BinaryTree { BTDataType data; struct BinaryTree* left; struct BinaryTree* right; }BTNode;为什么要用链表实现二叉树结点因为树是一个非线性的而数组存不了这种一对多的关系。并且树的结构是动态分叉的只有指针能灵活描述这种分叉关系。3.2 创建结点函数//创建结点的函数 BTNode* BuyNode(int x) { BTNode* node (BTNode*)malloc(sizeof(BTNode)); if (node NULL) { perror(malloc fail); return NULL; } node-data x; node-left NULL; node-right NULL; return node; }1BTNode*返回值类型a) malloc 在堆上申请了一块内存函数必须把这块内存的起始地址告诉调用者否则申请的内存就丢了内存泄漏。返回值 BTNode* 就是这个地址调用者拿到后才能操作这个结点.b)而且拷贝结构体数据多效率低返回地址轻便高效。2成员node的初始化node-data x;node-left NULL;node-right NULL;对node中每个成员进行初始化3return的注意搭配返回值类型进行返回3.3创建和销毁二叉树3.3.1 二叉树的创建//建二叉树的函数通过调用创建结点的函数 BTNode* CreateBinaryTree() { //创建结点 BTNode* node1 BuyNode(1); BTNode* node2 BuyNode(2); BTNode* node3 BuyNode(3); BTNode* node4 BuyNode(4); BTNode* node5 BuyNode(5); BTNode* node6 BuyNode(6); BTNode* node7 BuyNode(7); //将结点连接 node1-left node2; node1-right node4; node2-left node3; node4-left node5; node4-right node6; node6-left node7; return node1; }本代码建了一棵如图样子的二叉树⬆️3.3.2二叉树的销毁//二叉树销毁用的是后序 void TreeDestroy(BTNode* root) { if (root NULL) return; TreeDestroy(root-left); TreeDestroy(root-right); free(root); }为什么用我选择后序销毁也就是先销毁左子树右子树最后销毁根结点如果我先销毁根节点那我在销毁根节点之前就要保存一下根的左右子树的信息不然根销毁里就无法找到左右子树了而后序销毁就没这个顾虑。3.4 二叉树的遍历3.4.1前序遍历前序遍历的顺序根-左子树-右子树//前序遍历 void PreOrder(BTNode* root) { if (root NULL) { printf(N ); return; } printf(%d , root-data); PreOrder(root-left); PreOrder(root-right); }以下是前序遍历访问一个树的结点的示意图访问顺序1 2 3 NULL NULL NULL 4 5 NULL NULL 6 7 NULL NULL NULL代码实现的递归展开图如下3.4.2 中序遍历中序遍历的顺序左子树-根-右子树//中序遍历 void InOrder(BTNode* root) { if (root NULL) { printf(N ); return; } InOrder(root-left); printf(%d , root-data); InOrder(root-right); }3.4.3后序遍历后序遍历的顺序左子树-右子树-根//后序遍历 void PostOrder(BTNode* root) { if (root NULL) { printf(N ); return; } BehindOrder(root-left); BehindOrder(root-right); printf(%d , root-data); }3.4.4 层序遍历层序遍历是从根节点第1层开始向下层遍历每一层从左向右逐个遍历。层序遍历借助队列来完成。下面是队列实现层序遍历的流程图下面是代码实现//层序遍历 void TreelevelOrder(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); } QueueDestroy(q); }3.5二叉树其他功能的实现3.5.1二叉树的结点个数分析图如下一个二叉树可分为左子树右子树1个根节点代码如下//二叉树的结点个数 int TreeSize(BTNode* root) { return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1; }3.5.2二叉树叶子节点个数叶子结点就是二叉树的修后一层的结点。叶子节点特点叶子结点的左右子树为空代码如下//二叉树叶子结点个数 int TreeLeafSize(BTNode* root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return TreeLeafSize(root-left) TreeLeafSize(root-right); }root 0:根节点都没了左右子树更没了return 0.root-left NULL root-right NULL意思是左右子树都为空证明当前节点为叶子结点return 1是计数这是一个叶子结点。最后是如果左不为空右不为空证明不是叶子节点继续递归。3.5.3二叉树的高度一般情况将根节点定位第一层二叉树高度就是从根节点到最远叶子结点经过的结点个数可以说左子树、右子树中最大层树的加1这个1就是根节点层数。如下图左子树2层右子树3层所以是314从根节点到最远叶子结点1-4-5-7共4个结点。代码如下//二叉树高度 int TreeHeight(BTNode* root) { if (root NULL) return 0; int leftHeight TreeHeight(root-left); int rightHeight TreeHeight(root-right); return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; }3.5.4二叉树第k层结点个数如果是空树无论k为几都是0个节点。如果k1就是第一层结点个数即根节点只有一个。对第一层来说的第三层对第二层来说是第二层对第三层来说是第一层将第三层结点个数返回到第二层再返回到第一层。当我要求第k层的节点个数时可分为求左子树的k-1层加右子树k-1层结点数层层递归见下图代码如下//二叉树第k层结点个数 int TreeLevelKSize(BTNode* root,int k) { if (root NULL) return 0; if (k 1) return 1; return TreeLevelKSize(root-left , k-1) TreeLevelKSize(root-right , k-1); }3.5.5二叉树查找值为x的结点如果是空树肯定找不到返回NULL如果要找的值就是根节点的值那直接的返回根节点如果不是根节点那就递归遍历左子树和右子树如果整个二叉树没有目标值返回NULL。代码如下//二叉树查找值为x的结点本代码为前序遍历 BTNode* TreeFind(BTNode* root, BTDatatype x) { if (root NULL) return NULL; if (root-data x) return root; BTNode* ret1 TreeFind(root-left, x); if (ret1) return ret1; BTNode* ret2 TreeFind(root-right, x); if (ret2) return ret2; return NULL; }3.5.6判断是否为完全二叉树1.类似于层序遍历利用队列这时候将空也存到队列中然后取队头元素逐个遍历。2.当遇到第一个空结点后如果队列后面还有元素那么这个二叉树就不是完全二叉树。如果空后面没有元素那这个二叉树是完全二叉树。不可能出现遇到空时后面还有非空没进队列后面有非空这个非空一定是前面非空的孩子当层序出到空的时候前面非空都出完了那非空的孩子一定进队列了代码如下//判断是否为完全二叉树 bool BinaryTreeComplete(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, root-left); QueuePush(q, root-right); } while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); //如果有非空就不是完全二叉树 if (front) { QueueDestroy(q); return false; } } QueueDestroy(q); return true; }如有错误欢迎来指正哟~