数据结构学习之二叉树

今天我要分享的是数据结构中二叉树的知识下面我将从二叉树的概念二叉树的存储结构二叉树的遍历算法等方面来讲述。一、二叉树的基本概念定义每个节点最多有两个子节点的树结构基本术语根节点叶子节点父节点子节点深度高度特殊类型满二叉树完全二叉树平衡二叉树满二叉树一个二叉树如果每一个层的结点数都达到最⼤值则这个二叉树就是满⼆叉树。也就是说如果一 个二叉树的层数为 K 且结点总数是2^k-1 则它就是满二叉树。如图所示则为满二叉树完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为 K 的有 n 个 结点的⼆叉树当且仅当其每⼀个结点都与深度为K的满二叉树中编号从 1 至n 的结点一一对应时称 之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。补充二叉树性质1.若规定根结点的层数为 1 则⼀棵⾮空⼆叉树的第i层上最多有2^(i-1) 个结点2.若规定根结点的层数为 1 则深度为 h 的⼆叉树的最大结点数是2^h-1二、二叉树的存储结构二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。2.1顺序结构顺序结构存储就是使用数组进行存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有 空间的浪费完全二叉树更适合使用顺序结构存储。现实中我们通常把堆一种二叉树使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。2.2链式结构二叉树的链式存储结构是指用链表来表示一颗二叉树即用链指示元素的逻辑关系通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。三、实现链式结构二叉树用链表来表示一颗二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址其结构如下typedef int BTDataType; typedef struct BinaryTreeNode { struct BinTreeNode*left; struct BinTreeNode*right; BDT data; }BTNode;创建一颗二叉树BTNode*BuyBTNode(int val) { BTNode*newnode(BTNode*)malloc(sizeof(BTNode)); if(newnodeNULL) { perror(malloc fail); return NULL; } newnode-valval; newnode-leftNULL; newnode-rightNULL; return newnode; } BTNode*CreateTree() { BTNode*n1BuyBTNode(1); BTNode*n2BuyBTNode(2); BTNode*n3BuyBTNode(3); BTNode*n4BuyBTNode(4); BTNode*n5BuyBTNode(5); BTNode*n6BuyBTNode(6); BTNode*n7BuyBTNode(7); n1-leftn2; n1-rightn4; n2-leftn3; n4-leftn5; n4-rightn6; n5-leftn7; return node1; } }四、二叉树的遍历二叉树的操作离不开树的遍历我们先来看看二叉树的遍历有哪些方式二叉树的遍历方式可分为三种前序遍历中序遍历后序遍历1.前序遍历(Preorder Traversal 亦称先序遍历)访问根结点的操作发生在遍历其左右子树之前。遍历顺序为根左右2.中序遍历(Inorder Traversal)访问根结点的操作发⽣在遍历其左右⼦树之中。遍历顺序为左根右3.后序遍历(Postorder Traversal)访问根结点的操作发⽣在遍历其左右⼦树之后。遍历顺序为左右根以下面这颗二叉树为例它的前序遍历为A B DNULLNULL NULLC ENULL NULLFNULL NULL它的中序遍历为NULLDNULLBNULLANULLENULLCNULLFNULL它的后序遍历为NULL NULLDNULLBNULL NULLENULL NULLF C A代码实现前序遍历void PreOreder(BTNode*root) { if(rootNULL) { printf(NULL); return; } printf(%c ,root-val); PreOrder(root-left); PreOrder(root-right); }中序遍历void InOrder(BTNode*root) { if(rootNULL) { printf(NULL); return; } InOrder(root-left); printf(%c ,root-val); InOrder(root-right); }后序遍历void PostOrder(BTNode*root) { if(rootNULL) { printf(NULL); return; } PostOrder(root-left); PostOrder(root-right); printf(%c ,root-val);结点个数以及高度二叉树的结点个数结点个数根结点个数左子树结点个数右子树结点个数int BinaryTreeSize(BTNode*root) { if(rootNULL) { return 0; } return 1BinaryTreeSize(root-left)BinaryTreeSize(root-right); }二叉树叶子结点个数叶子结点个数左子树结点个数右子树结点个数int BinaryTreeLeafSize(BTNode*root) { if(rootNULL) { return 0; } if(root-leftNULLroot-rightNULL) { return 1; } return BinaryTreeLeafSize(root-left)BinaryTreeSize(root-right); }二叉树的深度深度根节点max(左子树右子树int BinaryTreeDepth(BTNode* root) { if(rootNULL) { return 0; } int leftdepBinaryTreeDepth(root-left); int rightdepBinaryTreeDepth(root-right); return 1(leftdep rightdep ? leftdep : rightdep); }二叉树的查找BTNode* BinaryTreeFind(BTNode* root, BTDataType x); { if(rootNULL) { return NULL; } if(root-datax) { return root; } BinaryTreeFind*leftFindBinaryTreeFind(root-leftx); if(leftFind) { return leftFind; } BinaryTreeFind*rightFindBinaryTreeFind(root-right,x); if(rightFind) { return rightFind; }二叉树的销毁void BinaryTreeDestory(BTNode** root) { if(*rootNULL) { return 0; } BinaryTreeDestory(((*root)-left)); BinaryTreeDestory(((*root)-right)); free(*root); *rootNULL; }层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历设二叉树的根结点所在层数 为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2 层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。要实现层序遍历需要借助队列来实现代码实现如下void LevelOrder(BTNode*root){ Queue q; QueueInit(q); QueuePush(q,root); while(!QueueEmpty(q)) { BTNode*topQueueFront(q); printf(%c ,top-data); QueuePop(q); if(top-left) { QueuePush(q,top-left); } if(top-right) { QueuePush(q,top-right); } } QueueDestroy(q); }