做网站没有创意,长宁网站建设制作,品牌策划方案模板,外贸网建站推广前言 该篇是在二叉树介绍及堆-CSDN博客的基础上的。该篇会有点抽象大家要自己多画画图自己感受一下。现在我们开始吧#xff01; 在学习二叉树基本操作时#xff0c;我们需要先有一个现成的二叉树。来方便我们练习。因为现在我们对二叉树的理解也并不是很深入。在这里创建一个…前言 该篇是在二叉树介绍及堆-CSDN博客的基础上的。该篇会有点抽象大家要自己多画画图自己感受一下。现在我们开始吧 在学习二叉树基本操作时我们需要先有一个现成的二叉树。来方便我们练习。因为现在我们对二叉树的理解也并不是很深入。在这里创建一个树是方便让我们理解。等我们学的差不多的时候我们来真正的创建二叉树。 下图是我创建二叉树的结构。 typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType date;struct BinaryTreeNode* leftchild;struct BinaryTreeNode* rightchild;
}BTNode;BTNode* CreateNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc);exit(-1);}node-date x;node-leftchild node-rightchild NULL;return node;
}
//手搓二叉树
BTNode* HandRub()
{BTNode* node1 CreateNode(1);BTNode* node2 CreateNode(2);BTNode* node3 CreateNode(3);BTNode* node4 CreateNode(4);BTNode* node5 CreateNode(5);BTNode* node6 CreateNode(6);node1-leftchild node2;node2-leftchild node3;node1-rightchild node4;node4-leftchild node5;node4-rightchild node6;return node1;
} 在二叉树的介绍及堆这篇文章中的二叉树概念可以发现二叉树定义是递归式的因此下面操作中基本都是按照该概念实现的。
遍历 二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个结点只操作一次。 二叉树的遍历有三种。 前序遍历先访问根节点在遍历左子树后遍历右子树。中序遍历先遍历左子树在访问根节点后遍历右子树。后序遍历先遍历左子树在遍历右子树后访问根节点。 在遍历中假设遇到空指针则打印N。
前序遍历 根据前面提到的前序遍历可以知道会先访问1节点然后在遍历1节点的左孩子也就是2节点。走到2节点时要重新进行前序遍历所以会先访问2节点然后在遍历2节点的左孩子节点也就是3节点。然后在访问3节点然后遍历3节点的左孩子但3节点没有左孩子。根据前序遍历它会遍历3节点的右孩子但3节点没有右孩子。这时它会返回到2节点遍历2节点的右孩子(2节点本身和左孩子都已经访问过了根据前序遍历规则它会遍历2节点的右孩子)。2节点没有右孩子它会返回到1节点的右孩子然后在次遍历。右边与左边同理。 不要看的它很复杂实际上思想还是挺简单的。 上面遍历完之后的结果应该是1 2 3 N N N 4 5 N N 6 N N。 上面说的就很符合递归的特点把一个大问题拆成与原问题相似但规模较小的子问题。
//前序遍历
void preOrder(BTNode* ret)
{if (ret NULL)//判断传入节点是否为空指针{printf(N );return;}printf(%d , ret-date);preOrder(ret-leftchild);preOrder(ret-rightchild);
} 这里的ret NULL 有两个作用在下面提供的代码中类似这段的都有该功能 判断传过来的树是不是空树。当左子树或右子树遍历完之后开始回归。 验证一下我们上面自己写出的结果。 可以发现我们自己写的和运行出来的结果没区别。这么复杂的过程用递归实现竟然这么简短这就是递归的魅力 中序遍历 中序遍历和前序遍历原理是一样的差别只是访问的次序不同体现在代码上就上顺序的差异。
//中序遍历
void InOrder(BTNode* ret)
{if (ret NULL){printf(N );return;}InOrder(ret-leftchild);printf(%d , ret-date);InOrder(ret-rightchild);
} 后序遍历 同样的后序遍历和前序遍历原理是一样的差别只是访问的次序不同体现在代码上就上顺序的差异。
//后序遍历
void PostOrder(BTNode* ret)
{if (ret NULL){printf(N );return;}PostOrder(ret-leftchild);PostOrder(ret-rightchild);printf(%d , ret-date);
}
用遍历结果推树的结构 已知1 2 3 4 5 7 6是前序遍历结果3 2 1 5 7 4 6是中序遍历结果。求该二叉树的结构。 由前序遍历结果可知1是根节点由中序遍历规则可以分开该树的左子树和右子树。 左子树结构看前序遍历1之后是2由前序遍历的特点先根在左后右得2是1的左孩子由前序遍历的特点得3是2的左孩子3由于下一个是4它在右子树中所以2没有右孩子且3是叶子。 右子树结构因为下一个是4所以4是1的右孩子。由中序遍历的先左在根后右。可以判断4的左子树是57右子树是6。前序遍历中4之后是5所以5是4的左孩子 7是5的右孩子。为什么如果7是5的左孩子那么在前序遍历中7会在5之前。 最后的结构如下 如果没看懂上面写的那就对二叉树遍历理解不太好。 节点个数
总节点数 最简单的方式就是传一个Size来计数。然后用遍历一遍即可。要判断传入节点是否为空指针。 注意这里要传Size的地址函数每次调用会开辟一个栈帧里面会存放函数的内容其中就有Size。当函数调用完后栈帧会被销毁掉Size保留的数据会被销毁如果这样Size就无法起到它的作用。
void TreeSize(BTNode* root, int* Size)
{if (root NULL)return;(*Size);TreeSize(root-leftchild, Size);TreeSize(root-rightchild, Size);
} 上面的写法可以实现目的那能不能不创建Size来实现呢其实是可以的。
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-leftchild) TreeSize(root-rightchild) 1;
} 我在这里就只写了左子树右子树与它相似大家可以自己试试。大家要结合图好好的理解感受一下。 叶子节点数 什么时候是叶子节点呢 大家想一下叶子节点有什么特点它没有孩子这就说明了它的左孩子和右孩子是相同的在创建节点时默认左孩子和右孩子都为NULL。这就是判断是否为叶节点的判断条件。 求叶子节点个数和求节点个数的思想是一致的。其实也就遍历一遍只不过加了额外的判断条件。 要判断传入节点是否为空指针。如果判断条件如果成立就返回1否则就继续。
int TreeLeafSize(BTNode* root)
{if (root NULL)return 0;return root-leftchild root-rightchild ? 1 : TreeLeafSize(root-leftchild) TreeLeafSize(root-rightchild);
} 第k层节点数 在这里要先认定第一层的高度为1不是0有些书上会把第一层的高度认为是0。 假设我们要第二层的节点数。 由上图可知当k 1时即到了该层 。其它的就和上面的求叶子节点个数一样了。 我们需要的是第1层当k小于1就没必要在继续了返回就行了。还有要判断传入节点是否为空指针。
int TreeNodeSize(BTNode* root, int k)
{if (k 1 || root NULL)return 0;return k 1 ? 1 : TreeNodeSize(root-leftchild, k - 1) TreeNodeSize(root-rightchild, k - 1);
} 查找值为x的节点 先找根节点再在左子树中找后在右子树中找。这和前序遍历很像。只是在前序遍历的基础上加了点限制条件。 在遍历左子树和右子树时要记录一下返回值别你找到了没带回来这就尴尬了。 要判断传入的节点是否为空。遇到要找的值那就一直返回直到跳出该函数。在此之前要加个判断返回的该节点不为NULL。如果没找到那就返回NULL。
BTNode* TreeFind(BTNode* root, int x)
{if (root NULL)return NULL;if (root-date x)return root;BTNode* ret1 TreeFind(root-leftchild, x);if (ret1)return ret1;BTNode* ret2 TreeFind(root-rightchild, x);if (ret2)return ret2;return NULL;
}
创建二叉树 好了经过上面知识的学习相信大家对二叉树有了一定的理解现在让我们创建二叉树吧 我们要创建一个数组用来存放值和空指针。为什么要存放空指针呢如果不存放那就有可能是任意一种遍历。在这里我将用#来表示空指针。传入的是数组数组需要下标来找数据所以在传参时要传下标的地址其原因和求节点数传地址的道理是一样的。 这里我用输入是前序遍历的情况来表示(下面的代码仅适用于前序遍历输入)。 要先判断是否为空后让下标加加加加时不要写在判断条件上因为如果不是空的话在判断之后下标会加加那就少了一个值。然后创建节点再把值放进去后加加然后构建左子树怎么做呢让节点的左孩子调用该函数即可。右子树的构建同理。最后返回创建节点即可。
BTNode* CreateTree(char* arr, int* i)
{if(arr[*i] #){(*i);return NULL;}TNode* root (TNode*)malloc(sizeof(TNode));root-val arr[(*i)];root-left CreateTree(arr, i);root-right CreateTree(arr, i);return root;
}
