【初阶数据结构】 左右逢源的分支诗律 二叉树1

点击展开/收起 文章目录文章目录树的概念***树的基础概念***森林树和森林的存储二叉树二叉树的性质二叉树的遍历二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力树的概念在讲解二叉树之前,我们先提一嘴树的概念,不同于我们之前学到的栈与队列,链表顺序表,树是一种非线性结构,下面我具体讲讲树的概念.首先树的子树与子树之间不可相连,子树与其他树的孩子也不可相连树的基础概念如下图就是一颗树:1.节点的度是指,如上图A节点他连了三个子树,它的度就为3,节点的度就是该节点子树个数2.树的度 : 树的度就是一棵树中,度最大的节点的度 eg:在上图中树的度为三3.叶节点: (又称为终端节点),也就是度为零的节点4.父节点: ,含有子节点的节点成为它的父节点的子节点,eg:子节点B C D的父节点就是A5.兄弟节点: ,就是在同一行,具有相同父节点的节点6.结点的层次: ,从根节点定义为第一层,往下层数相加7.树的高度,: 总层数就是树的高度8.堂兄弟节点: 双亲在同一层的互为堂兄弟节点9.根节点: 就是最顶上的节点 也就是AtypedefintDataType;structNode{structNode*firstChild1;// 第一个孩子结点structNode*pNextBrother;// 指向其下一个兄弟结点DataType data;// 结点中的数据域}森林在树的基础概念之上 ,我们引出了森林;如图所示:在森林中没有共同的根节点,是一群树的集合树和森林的存储通常,我们是把树和森林,以二叉树地形式来存储typedef int DataType;structNode{structNode*firstChild1;// 第一个孩子结点structNode*pNextBrother;// 指向其下一个兄弟结点DataType data;// 结点中的数据域}如果是森林的话,去掉A节点就好了二叉树存储森林和树区别:树变二叉树没有右孩子,森林变二叉树有右孩子下面我们来观察一下树的后续遍历与他变成的二叉树的中序遍历树的后序遍历:DHIEFBGCA树变的二叉树的中序遍历:DHIEBGCA我们会发现树的后序遍历与他对映的二叉树中序遍历一致森林的遍历方式是把这里为例子,森林后序遍历,就是从左到右,每颗小树的后续遍历按照从左到右顺序拼起来同理也得:我们会发现森林的后序遍历与他对映的二叉树中序遍历一致在这里我们常常会见到有些说法,例如,树,森林的前根遍历,中根遍历,后根遍历,其实就是他转换成对应的二叉树后的前序遍历,中序遍历,后序遍历二叉树根据树的定义二叉树就是一种特殊的树,它的度不大于2,意思是他一个节点最多有两个孩子满二叉树与完全二叉树如图所见,满二叉树就是每层全满的二叉树完全二叉树就是倒数第二层全满,最后一层靠左一侧的二叉树为什么要单独提这两种二叉树呢?因为这两种二叉树,是满的空间利用率高可以像堆一样,顺序存储,由图可以看出:满二叉树与完全二叉树空间利用率很高,适合顺序存储,非完全二叉树空间利用率很低会有大量的位置空缺,浪费空间,因此我们会采用链式存储二叉树的性质1. 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(h-1) 个结点.2. 若规定根结点的层数为1则深度为h的二叉树的最大结点数是 2^h - 1.3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 n21二叉树的遍历在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入为了降低大家学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。自己手搓一棵二叉树typedefintBTDataType;typedefstructBinaryTreeNode{BTDataType _data;structBinaryTreeNode*_left;structBinaryTreeNode*_right;}BTNode;BTNode*CreatBinaryTree(){BTNode*node1BuyNode(1);BTNode*node2BuyNode(2);BTNode*node3BuyNode(3);BTNode*node4BuyNode(4);BTNode*node5BuyNode(5);BTNode*node6BuyNode(6);node1-_leftnode2;node1-_rightnode4;node2-_leftnode3;node4-_leftnode5;node4-_rightnode6;returnnode1;}大家在学习二叉树的遍历时我建议初期还是把空节点也写上举个例子这样对遍历就了解的很清楚下面我们展示代码实现当然这里只是打印,没有存储他的顺序,再下一次博客,我会具体实现二叉树的前序遍历voidprevorder(BTNode*root){if(rootNULL){printf(N );return;}printf(%d ,root-data);prevorder(root-left);prevorder(root-right);}二叉树的中序遍历voidInorder(BTNode*root){if(rootNULL){printf(N );return;}Inorder(root-left);printf(%d ,root-data);Inorder(root-right);}二叉树的后序遍历voidBackorder(BTNode*root){if(rootNULL){printf(N );return;}Backorder(root-left);Backorder(root-right);printf(%d ,root-data);}希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力