企业网站 响应式,网站建设价格在哪济南兴田德润优惠吗,公司宣传册怎么制作,硬件开发文章目录 一、链式二叉树1.1 链式二叉树的创建1.2 根、左子树、右子树1.3 二叉树的前中后序遍历1.3.1前(先)序遍历1.3.2中序遍历1.3.3后序遍历 1.4 二叉树的节点个数1.5 二叉树的叶子结点个数1.6 第K层节点个数1.7 二叉树的高度1.8 查找指定的值(val)1.9 二叉树的销毁 二、层序… 文章目录 一、链式二叉树1.1 链式二叉树的创建1.2 根、左子树、右子树1.3 二叉树的前中后序遍历1.3.1前(先)序遍历1.3.2中序遍历1.3.3后序遍历 1.4 二叉树的节点个数1.5 二叉树的叶子结点个数1.6 第K层节点个数1.7 二叉树的高度1.8 查找指定的值(val)1.9 二叉树的销毁 二、层序遍历2.1 二叉树的层序遍历2.2 层序遍历判断二叉树是否是完全二叉树 三、二叉树的性质(补充)3.1选择题 一、链式二叉树
因为二叉树的度是确定的所以可以用链表来表示一棵二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成: 数据域和左右指针域。左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址其结构如下:
typedef int BTDataType;
//二叉链
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left; //指向当前结点的左孩子struct BinaryTreeNode* right; //指向当前结点的右孩子BTDataType val; //当前结点的值域
}BTNode;1.1 链式二叉树的创建
二叉树的创建方式比较复杂, 为了更好的步入到二叉树的内容中我们先手动创建一棵链式二叉树。 比如我们要创建如下一个二叉树 //创建节点
BTNode* BuyBTNode(int val)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-val val;newnode-left NULL;newnode-right NULL;return newnode;
}
//创建链式二叉树
BTNode* CreateBTree()
{BTNode* node1 BuyBTNode(1);BTNode* node2 BuyBTNode(2);BTNode* node3 BuyBTNode(3);BTNode* node4 BuyBTNode(4);BTNode* node5 BuyBTNode(5);BTNode* node6 BuyBTNode(6);BTNode* node7 BuyBTNode(7);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;node5-left node7;return node1;
}1.2 根、左子树、右子树
由于这里是链式二叉树所以后面我们看到一个二叉树就要把树分成三个部分根、左子树、右子树。回顾二叉树的概念二叉树分为空树和非空二叉树非空二叉树由根结点、根结点的左子树、根结点的右子树组成的。 根结点的左子树和右子树分别又是由子树的根结点、子树结点的左子树、子树结点的右子树组成的。因此二叉树的定义是递归式的, 后序链式二叉树的操作中基本都是按照该概念实现的。
1.3 二叉树的前中后序遍历
二叉树的操作离不开树的遍历那二叉树的遍历有哪些方式呢比如我们要遍历下面这个二叉树 二叉树的遍历分为三种前/中/后序遍历。下面我们分别讲解三种遍历。
1.3.1前(先)序遍历
▲ 前序遍历(Preorder Traversal(DLR)亦称先序遍历): 访问根结点的操作发生在遍历其左右子树之前 访问顺序为: 根结点、左子树、右子树 void PreOrder(BTNode* root)
{if (root NULL){printf(# );return;}printf(%c ,root-val);PreOrder(root-left);PreOrder(root-right);
}先看运行结果 打印的结果为什么是上面的样子呢这里涉及到函数的递归所以要先理解前序遍历的顺序是根、左子树、右子树。也就是从根节点开始遍历根遍历完了就到左子树那左子树又可以分为根、左子树、右子树又会按照根左右的顺序遍历要等到左子树完完全全遍历完了才会遍历到右子树。这里的难点就是: 理解递归递推的终止条件和每一层函数调用完毕后会返回上一层调用它的函数处继续往后执行(回归)。
前序遍历的递归过程如下
1.3.2中序遍历
◆中序遍历(lnorder Traversal(LDR)): 访问根结点的操作发生在遍历其左右子树之中(间) 访问顺序为: 左子树、根结点、右子树 void InOrder(BTNode* root)
{if (root NULL){printf(# );return;}InOrder(root-left);printf(%c , root-val);InOrder(root-right);
}打印结果如下 中序遍历就是从左子树开始遍历左子树遍历完了就遍历根最后再遍历右子树。而其中的子树又可以分为左子树、根、右子树又会按照左根右的顺序遍历。
1.3.3后序遍历
▼后序遍历(Postorder Traversal(LRD)): 访问根结点的操作发生在遍历其左右子树之后 访问顺序为: 左子树、右子树、根结点 void PostOrder(BTNode* root)
{if (root NULL){printf(# );return;}PostOrder(root-left);PostOrder(root-right);printf(%c , root-val);
}打印结果如下 后序遍历就是根要在左右子树之后访问。前\中\后续遍在历代码中的递归调用虽然只是换了个位置但是递归调用的过程是不相同的如不理解函数的逐层调用过程就需要画图层层递进地来深刻剖析递归。
1.4 二叉树的节点个数
通过递归计算二叉树的节点个数
int BTreeSize(BTNode* root)
{if (root NULL)return 0;return BTreeSize(root-left) BTreeSize(root-right) 1;
}这里要理解递归的过程是什么样, 以下图的举例来理解这里的递归 这里递推的结束条件是子树为空才会回归上一层; 而空树就没有节点嘛所以return 0。在返回上一层的时候可以看到是左右子树都递归完毕而且还要加一个1之后才返回上一层加的1其实就是加上根节点的数量。
1.5 二叉树的叶子结点个数
通过递归计算二叉树的叶子节点个数
int BTreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return BTreeLeafSize(root-left) BTreeLeafSize(root-right);
}没有孩子节点的节点就是叶子节点所以递推结束的条件就是该节点的左右子树为空就返回1即把该叶子节点的数量计上。而一开始的判空其实针对对根节点而言的。如果树都为空那就没有叶子节点啦。举例递归过程
1.6 第K层节点个数
二叉树的第K层节点个数
int BTreeLevelKSize(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return BTreeLevelKSize(root-left, k - 1) BTreeLevelKSize(root-right, k - 1);
}计算二叉树第K层的节点这里需要加入一个参数k才能实现因为我们不知道递归什么时候会到达第k层所以传一个参数k让它每递推一次就递减1若根节点为第一层则k递减到1就到达第k层了(递推终止条件)。当然还有一个递推终止条件就是还没到达第k层就已经出现了空节点所以还没到达第k层时就遇到了空就返回。
1.7 二叉树的高度
通过递归计算二叉树的高度/深度
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;
}计算二叉树的高度也就是计算该二叉树有多少层那就是我们要找到一个沿着其祖先路径最长的那个节点。所以左右子树之间需要通过比较返回较长的那个节点才行。每返回一层要加个1因为每个节点相较于其孩子节点都是一个根只要不为空就要算一节长度。 注意如果上面的代码简化写成下面的样子
return BTreeDepth(root-left) BTreeDepth(root-right)? BTreeDepth(root-left)1 : BTreeDepth(root-right)1;这样写时间效率上会非常差。试想如果二叉树的节点数量庞大即层数很多时左右子树相比较就要进行两个函数的递归调用递归调用又是三目表达式那时间消耗就会很大而等比较出了大小以后才决定三目表达式的返回值而返回值又是一个函数的递归调用递推进入下一层以后还是面临同样的三目表达式同样的事情一遍又一遍地重复就会消耗非常非常多的时间。所以这里不建议这么写最好的方式就是将函数的返回值记录下来这样回归的时候将记录下来的值返回去就不会造成上面的情况。
1.8 查找指定的值(val)
在二叉树中查找指定的值x, 如果找到则返回该节点的地址, 否则返回NULL。
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-val x)return root;BTNode* ret1 BTreeFind(root-left, x);if (ret1 ! NULL)return ret1;return BTreeFind(root-right, x);
}举如下一个例子比如我们要找x 3的节点则函数的递归过程如下 递归的难点就是返回值不是一下子返回到最上面(最外面)的函数而是返回上一层调用它的函数处。
1.9 二叉树的销毁
销毁二叉树的销毁就比较简单了, 递归的过程采用后续遍历释放节点
void BTreeDestroy(BTNode* root)
{if (root NULL)return;BTreeDestroy(root-left);BTreeDestroy(root-right);free(root);
}链式二叉树适合于数据的存储但并不适用于数据的增删查改。所以这里只是了解链式二叉树的性质以及怎样通过递归去求二叉树的节点、叶子结点、高度等。 二、层序遍历
2.1 二叉树的层序遍历
除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 实现层序遍历最好的方法是借助数据结构: 队列 可以看到上图通过队列就可以实现二叉树的层序遍历每出队一个元素就让该元素的左右孩子入队。代码实现如下(队列的性质是先进先出)
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root ! NULL)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* top QueueFront(q);printf(%c , top-val);QueuePop(q);if (top-left ! NULL){QueuePush(q, top-left);}if (top-right ! NULL){QueuePush(q, top-right);}}QueueDestroy(q);
}注意这里队列中每个节点存放的值(data)是二叉树节点的地址。所以队列出队只是将队列的头结点释放掉了而并没有把节点里存放的二叉树节点指针删掉。上面的代码中可以看到已经提前将队头节点的值(二叉树节点的指针)存放在top里面了。
2.2 层序遍历判断二叉树是否是完全二叉树
有了层序遍历这种方法我们其实就可以用此方法判断一个二叉树是否是完全二叉树
bool IsCompleteBTree(BTNode* root)
{Queue q;QueueInit(q);if (root ! NULL)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 ! NULL){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}三、二叉树的性质(补充)
1.若规定根结点所在层数为1, 则一棵非空二叉树的第i层上最多有2i-1个结点. 2.若规定根结点所在层数为1则深度(层数)为h的二叉树的最大结点数是2h-1 3.对任何一棵二叉树, 如果度为0的叶结点个数为n0, 度为2的分支结点个数为n2, 则有: n0n21 解释一下第三个性质 3.1选择题 (1) 某完全二叉树按层次输出(同一层从左到右)的列为ABCDEFGH该完全二叉树的前序序列为 (A) A ABDHECFG B ABCDEFGH C HDBEAFCG D HDEBFGCA (2) 某二叉树的先序遍历和中序遍历如下: 先序遍历: EFHIGJK; 中序遍历: HFIEJKG. 则二叉树根节点为 (A) A E B F C G D H (3) 一棵二叉树的中序遍历序列为: badce后序遍历序列为: bdeca则该二叉树的前序历列为 (D) A adbce 8 decab C debac D abcde 记住前序序列能确定根节点在最左边后续遍历能确定根节点在最右边再结合中序遍历就能分割出整体的左、根、右。将该二叉树画出来。 (4) 某二叉树的后序遍历序列与中序遍历序列相同均为ABCDEF则按层次输出(同一层从左到右)为 (A) A FEDCBA B CBAFED C DEFCBA D ABCDEF (5) 某二叉树共有399个结点其中有199个度为2的结点则该二又树中的叶子结点数为 (B) A 不存在这样的二叉柯 B 200 C 198 D 199 通过二叉树性质可知该二叉树的叶子节点个数为1991 200 (6) 下列数据结构中不适合采用顺序存储结构的是 (AC) A 非完全二叉树 B 堆 C 队列 D 栈 (7) 在具有2n个结点的完全二叉树中中叶子结点个数为(A) A n B n1 C n-1 D n/2 (8) 一棵完全二又树的结点个数为531个那么这棵树的高度为 (B) A 11 B 10 C 8 D 12
