贵阳市城乡建设部网站,logo制作app,展示网站模板下载,株洲网红目录 一#xff0c;二叉树的结构深入认识 二#xff0c;二叉树的遍历 三#xff0c;二叉树的基本运算 
3-1#xff0c;计算二叉树的大小 
3-2#xff0c;统计二叉树叶子结点个数 
3-3#xff0c;计算第k层的节点个数 
3-4#xff0c;查找指定值的结点 一#xff0c;二叉…目录 一二叉树的结构深入认识 二二叉树的遍历 三二叉树的基本运算 
3-1计算二叉树的大小 
3-2统计二叉树叶子结点个数 
3-3计算第k层的节点个数 
3-4查找指定值的结点 一二叉树的结构深入认识 二叉树是不可随机访问的二叉树的结构是通过双亲结点与孩子结点之间的连接进行遍历访问因此二叉树的结构是用链式结构来存储的。如下 
二叉树的结构 #include stdio.h #include stdlib.h typedef struct Tree {     int val;//数据     struct Tree* leftchild;//左孩子结点     struct Tree* rightchild;//右孩子结点 }Tree; 要说明的是学习二叉树的结构不跟栈和队列之类的一样用于增删查改二叉树没有这些操作二叉树的运用比较复杂下面会依次讲解。 二二叉树的遍历 二叉树的遍历有前序遍历中序遍历后序遍历层序。通常在这些遍历算法中除了层序遍历外其它的遍历都要运用递归结构。 1前序遍历(也称先序遍历)——访问根结点的操作发生在遍历其左右子树之前即遍历的 
顺序为根左子树右子树。 2中序遍历——访问根结点的操作发生在遍历其左右子树之间。即遍历的顺序为左子树根右子树。 3后序遍历——访问根结点的操作发生在遍历其左右子树之后。即遍历的顺序为左子树右子树根。 4层序遍历——从左到右一层一层的遍历此遍历非常简单就如从开始到结尾的遍历顺序表一样。 注意这里要说明的是以上的遍历除了层序遍历外其它的遍历都是递归式的遍历可不是单纯普通式按照以上顺序循环式的遍历正确的遍历如下图 说明一下在二叉树的遍历中前中后遍历的思路基本相同而层序遍历一般要借助队的结构来实现本篇文章先不做介绍后文深入运用时会详细说明。前中后的三种遍历代码如下 
//前序遍历
void FrontOrder(struct Tree* root) {//当递归到空结点时退出if (root  NULL) {return;}//输出fprintf(stdout, %d , root-val);//递归左子树FrontOrder(root-leftchild);//递归右子树FrontOrder(root-rightchild);
}
//中序遍历
void MiddleOrder(struct Tree* root) {//当递归到空结点时退出if (root  NULL) {return;}//递归左子树MiddleOrder(root-leftchild);//输出fprintf(stdout, %d , root-val);//递归右子树MiddleOrder(root-rightchild);
}
//后序遍历
void RearOrder(struct Tree* root) {//当递归到空结点时退出if (root  NULL) {return;}//递归左子树RearOrder(root-val);//递归右子树RearOrder(root-val);//输出fprintf(stdout, %d , root-val);
}解析 递归本身有点不好理解而上面的递归遍历中当进行递归遍历时可看做从此函数的根结点开始不断往下面的左右孩子结点遍历当递归到根结点为空时结束下一次递归并返回到此结点的双亲结点可以说二叉树的递归遍历是不断往下层进行的只有当遍历到最下层或下层的空结点时才返回也就是递归遍历是从最后开始然后不断往回返直到返回到二叉结构的根节点才结束整个递归程序。 
补充 函数的递归其实跟我们学习的栈结构一样递归入函数(即进入函数栈帧)相当于入栈出函数(即函数栈帧的销毁)相当于出栈。 
学习建议 遍历思想是学习二叉树的基本很多二叉树的算法思想都要在此递归遍历的思想上进行开阔的因此如果这中递归思路不明白一定要先理清思路不建议先往后面看。 三二叉树的基本运算 在讲解这一部分内容前我们要先明白递归中设置局部变量的用法。 二叉树递归设置局部变量的注意 在二叉树计数中我们难免要设定局部变量而在进行递归返回中可能有些人说函数的返回值会覆盖之前的值不明白为什么覆盖后的值就是我们想要统计的数值。其实这原理很简单在讲解二叉树遍历的解析说过二叉树的递归遍历是不断往下层进行的只有当遍历到最下层时才返回也就是递归程序是从最后开始不断往前返回当我们递归遍历二叉树时满足计数的条件会不断往上层返这时计数的值相当于以此函数中root为根结点的子树的以下计数值也就是我们要统计的数值。 
3-1计算二叉树的大小 计算二叉树的大小说白了就是确定有几个不为空的结点此算法比较简单我们可直接遍历整个二叉结构不断加一来实现。代码如下 
//统计二叉树中叶子结点的个数
int TreeSize(Tree* root) {//当为空结点时说明此时为0if (root  NULL) {return 0;}//不断递归遍历遍历一个结点加1。return TreeSize(root-leftchild)  TreeSize(root-rightchild)  1;
} 以上代码虽然省力但可能对于部分人来说比较难理解展开后的代码如下 
int TreeSize(Tree* root) {if (root  NULL) {return 0;}//遍历左子树的结点个数int leftsize  TreeSize(root-leftchild);//遍历右子树的结点个数int rightsize  TreeSize(root-rightchild);//返回以此结点为根结点的二叉树结点个数此二叉树是子二叉树return leftsize  rightsize  1;
} 对于当初学者笔者建议用展开后的代码对递归了解比较深入后再用合成版代码。 
3-2统计二叉树叶子结点个数 此算法与计算二叉树的结点个数方法相似不同的是当进行递归遍历时我们可利用叶子结点的左右孩子都为空的特点来计数当递归遍历时满足这一特点进行计数不满足进行递归遍历代码如下 
int LeavesNodeSize(Tree* root) {if (root  NULL) {return 0;}//当此结点是叶子结点时计数1if (root-leftchild  NULL  root-rightchild  NULL) {return 1;}//左孩子结点的叶子结点数int count1  LeavesNodeSize(root-leftchild);//右孩子结点的叶子结点数int count2  LeavesNodeSize(root-rightchild);//返回当前以root为根结点的子二叉树的叶子结点总个数return count1  count2;
} 当我们明白以上原理后可进行简化算法跟之前一样先理清以上思路再进行简化。如下 
int LeavesNodeSize(Tree* root) {if (root  NULL) {return 0;}if (root-leftchild  NULL  root-rightchild  NULL) {return 1;}return LeavesNodeSize(root-leftchild)  LeavesNodeSize(root-rightchild);
} 
3-3计算第k层的节点个数 记录第k层的二叉树结点也是同理在递归遍历过程中往下层递归一次将k减1当k1时就递归到了第k层也就是在此时开始计数而函数返回值将返回以此函数中的root为根结点的子二叉树的第k层结点数。 
int NodeCount(Tree* root, int k) {if (root  NULL) {return 0;}//当k  1 时此时遍历到了第k层此时计数if (k  1) {return 1;}//以此函数的root为根结点以下的子二叉树第k层的左孩子结点数int leftchild  NodeCount(root-leftchild, k - 1);//以此函数的root为根结点以下的子二叉树第k层的右孩子结点数int rightchild  NodeCount(root-rightchild, k - 1);//返回以此函数的root为根结点以下的子二叉树第k层的结点数return leftchild  rightchild;
} 算法合并简化后如下 
int NodeCount(Tree* root, int k) {if (root  NULL) {return 0;}if (k  1) {return 1;}return NodeCount(root-leftchild, k - 1)  NodeCount(root-rightchild, k - 1);
} 
3-4查找指定值的结点 此算法的坑比较多首先我们要考虑的是当遍历到要查找的结点时如何停止遍历并最终返回该结点。要知道一点当我们要查找的结点在中间时直接返回是上一次的递归函数因此我们要做的是让查找的指定结点不断返回直到递归结束。 算法详细步骤如下 
Tree* FoundNode(Tree* root, int x) {if (root  NULL) {return NULL;}if (root-val  x) {return root;}Tree* leftchild  FoundNode(root-leftchild, x);//当左孩子是我们要找的结点时就不往下继续遍历了直接返回此结点if (leftchild ! NULL  leftchild-val  x) {return leftchild;}Tree* rightchild  FoundNode(root-rightchild, x);//当左孩子是我们要找的结点时就不往下继续遍历了直接返回此结点if (rightchild ! NULL  rightchild-val  x) {return rightchild;}//当查找不到返回NULLreturn NULL;
} 算法的化简代码如下 
Tree* FoundNode(Tree* root, int x) {if (root  NULL) {return NULL;}if (root-val  x) {return root;}Tree* leftchild  FoundNode(root-leftchild, x);//当左孩子是我们要找的结点时就不往下继续遍历了直接返回此结点if (leftchild ! NULL  leftchild-val  x) {return leftchild;}//遍历右结点当右孩子是我们要找的结点时返回此结点return FoundNode(root-rightchild, x);
} 总结学习到这里学者们明显感到难度增大了不过也不用担心只要我们多多思考并加之练习其实逻辑也不是那么难上面的算法程序笔者之所以将步骤展开和步骤合并一并写入就是为了让大家多多练习以上的思路其实逻辑也都是一样的只是为了强化思维罢了。