云主机网站配置,洛阳市建设规划局网站,小程序注册开发流程,wordpress 显示小工具前言
这个专栏将会用纯C实现常用的数据结构和简单的算法#xff1b;有C基础即可跟着学习#xff0c;代码均可运行#xff1b;准备考研的也可跟着写#xff0c;个人感觉#xff0c;如果时间充裕#xff0c;手写一遍比看书、刷题管用很多#xff0c;这也是本人采用纯C语言…前言
这个专栏将会用纯C实现常用的数据结构和简单的算法有C基础即可跟着学习代码均可运行准备考研的也可跟着写个人感觉如果时间充裕手写一遍比看书、刷题管用很多这也是本人采用纯C语言实现的原因之一欢迎收藏 关注本人将会持续更新。 文章目录 树相关概念什么是二叉树二叉树定义基本概念基本形态二叉树性质性质1性质2性质3性质4性质五 特殊二叉树满二叉树完全二叉树 二叉树创建与遍历树创建树遍历前序递归非递归 中序递归非递归 后序递归非递归 总代码 树相关概念
什么是二叉树
二叉树定义
二叉树是n (n≥0)个结点的有限集合。
每个节点最多有两个子节点分别称为左子节点和右子节点。左子节点和右子节点可以为空。二叉树的子树也是二叉树。
基本概念
节点的度一个节点含有的子树的个数称为该节点的度叶节点度为0的节点称为叶节点分支节点度不为0的节点又称为非终端节点父节点若一个节点含有子节点则这个节点称为其子节点的父节点又称为双亲结点子节点一个节点含有的子树的根结点称为该节点的子节点又称为孩子节点兄弟节点具有相同父节点的节点互称为兄弟节点树的度一棵树中最大的节点的度称为树的度节点的层次从根节点开始定义根为第1层根的子节点为第2层以此类推树的高度或深度树中节点的最大层次堂兄弟节点双亲在同一层的节点互为堂兄弟节点的祖先从根到该节点所经分支上的所有节点子孙以某节点为根的子树中任一节点都称为该节点的子孙
基本形态 二叉树性质
性质1
二叉树第k (k1)层上至多有2k–1个结点。
思考题
若二叉树具有第k层的结点那么第k层结点数的取值范围是多少[1, 2k-1]
性质2
高度为h (h0)的二叉树至多有2h - 1个结点
思考题
高度为h的二叉树的结点数范围
证明高度为h的二叉树共有h层第k层节点数范围为[1, 2k-1] 故可知高度为h的二叉树至少具有 ∑ k 1 h 1 h \sum _{k1}^{h} 1h ∑k1h1h个节点高度为h的二叉树至多具有 ∑ k 1 h 2 k − 1 2 0 2 1 . . . 2 h − 1 2 h − 1 \sum ^{h}_{k1}2^{k-1}2^02^1...2^{h-1}2^h-1 ∑k1h2k−12021...2h−12h−1 ∑ k 1 h 2 k − 1 2 0 2 1 . . . 2 h − 1 2 h − 1 \sum ^{h}_{k1}2^{k-1}2^02^1...2^{h-1}2^h-1 k1∑h2k−12021...2h−12h−1
性质3
设二叉树叶子结点数为n0度为2的结点数为n2则有n0 n2 1。
性质4
结点数为n的完全二叉树的高度为 log 2 n \log_2{n} log2n 1或 log 2 ( n 1 ) \log_2{(n1)} log2(n1)
性质五
给有n个结点的完全二叉树按层次编号对于编号为i的结点
可计算i结点的双亲结点的编号 若i 1则无双亲否则双亲编号为 i 2 \frac i 2 2i 可计算i结点的左孩子结点的编号 若2*i n则无左孩子否则其左孩子编号为2*i 可计算i结点的右孩子结点的编号 若2*i1 n则无右孩子否则其右孩子编号为2*i1
特殊二叉树
满二叉树
深度为h且具有2h-1个结点的二叉树每一层都容纳了该层所能容纳的最大结点数结点的二叉树没有度数为1的结点且叶子结点均分布在最大层的二叉树 思考题
深度为h的满二叉树
结点总数为 2h - 1叶子结点数为 2h-1 度为1的结点数为0度为2的结点数为2h-1-1
具有n个结点的满二叉树
有多少个叶子(n 1) / 2有多少个度为2的结点(n - 1) / 2
完全二叉树
除去最大层是一棵满二叉树除去最大层是一棵满二叉树 完全二叉树的几个非常有趣的特点
除去最大层是一棵满二叉树最大层上的结点向左充满叶子只可能分布在最大层和次大层上。度为1的结点至多有1个。一棵满二叉树一定是一棵完全二叉树而一棵完全二叉树不一定是一棵满二叉树。对于具有相同结点数的二叉树而言完全二叉树的高度一定是其中最小的
思考题
高度为h的完全二叉树的结点范围[ 2k-1, 2k-1]
具有n个结点的二叉树的高度最小值为多少高度最大值为多少 [ log 2 n \log_2{n} log2n1, n]
完全二叉树最小 log 2 n \log_2{n} log2n1一层只有一个结点最大n
二叉树创建与遍历
树创建
节点封装二叉树封装就需要封装两个孩子
typedef struct TreeNode {char data;struct TreeNode* LChild;struct TreeNode* RChild;
}TreeNode;TreeNode* create_node(char data)
{TreeNode* new_node (TreeNode*)calloc(1, sizeof(TreeNode));assert(new_node);new_node-data data;return new_node;
}创建这里采用“最傻瓜式”创建如下代码所示
// 傻瓜式建立树
void create_tree(TreeNode* parent, TreeNode* lChild, TreeNode* rChild)
{// 父亲不为 NULL 即可assert(parent);parent-LChild lChild;parent-RChild rChild;
}// 创建如下
int main()
{// 一个一个创建节点TreeNode* a create_node(a); TreeNode* c create_node(c);TreeNode* d create_node(d);TreeNode* s create_node(s);TreeNode* h create_node(h);TreeNode* e create_node(e);TreeNode* b create_node(b);TreeNode* v create_node(v);TreeNode* m create_node(m);// 连接create_tree(a, c, d); // a为跟节点create_tree(c, s, h);create_tree(d, e, b);create_tree(s, NULL, v);create_tree(h, NULL, NULL);create_tree(e, m, NULL);create_tree(b, NULL, NULL);return 0;
}树遍历
前序
遍历顺序左中右动画如下所示(ppt制作) 递归
// 递归前序
void preorder_recursion(TreeNode* root)
{if (root NULL) {printf(NULL );return;}printf(%c , root-data);preorder_recursion(root-LChild);preorder_recursion(root-RChild);
}非递归
借助栈辅助
// 迭代前序遍历
// 注意一点节点入栈顺序与出栈顺序
void preorder_travel(TreeNode* root)
{assert(root);// 准备栈TreeNode* stack[1024] { 0 };int top -1;stack[top] root;while (top ! -1) {TreeNode* temp stack[top];top--;printf(%c , temp-data);if (temp-RChild ! NULL) stack[top] temp-RChild;if (temp-LChild ! NULL) stack[top] temp-LChild;}
}中序
遍历顺序中左右 递归
// 递归中序
void mid_recursion(TreeNode* root)
{if (root NULL) {printf(NULL );return;}mid_recursion(root-LChild);printf(%c , root-data);mid_recursion(root-RChild);
}非递归
要注意还有一个指针跟着栈走
// 中序回退靠栈
// 核心cur与栈配合维护cur指针
void mid_travel(TreeNode* root)
{assert(root);TreeNode* stack[1024] { 0 };int top -1;TreeNode* cur root;while (cur ! NULL || top ! -1) {if (cur ! NULL) {stack[top] cur;cur cur-LChild;}else {TreeNode* t stack[top];top--;printf(%c , t-data);cur t-RChild;}}
}后序
遍历顺序左右中 递归
// 递归后序
void last_recursion(TreeNode* root)
{if (root NULL) {printf(NULL );return;}last_recursion(root-LChild);last_recursion(root-RChild);printf(%c , root-data);
}
非递归
和前序遍历一样维护一个栈
// 后序
// 核心pre指针、cur指针以及什么时候pre 与 cur指针相遇以及为什么弹出后cur NULLpre cur
// 动画想清楚如果一个节点要打印则情况是什么pre一直在模拟左、右、中节点
void last_travel(TreeNode* root)
{assert(root);TreeNode* stack[1024] { 0 };int top -1;TreeNode* used NULL;TreeNode* cur root;while (cur ! NULL || top ! -1) {while (cur) {stack[top] cur;cur cur-LChild;}cur stack[top];if (cur-RChild NULL || cur-RChild used) {printf(%c , cur-data);top--;used cur;cur NULL;}else {cur cur-RChild;}}
}总代码
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef struct TreeNode {char data;struct TreeNode* LChild;struct TreeNode* RChild;
}TreeNode;TreeNode* create_node(char data)
{TreeNode* new_node (TreeNode*)calloc(1, sizeof(TreeNode));assert(new_node);new_node-data data;return new_node;
}// 傻瓜式建立树
void create_tree(TreeNode* parent, TreeNode* lChild, TreeNode* rChild)
{// 父亲不为 NULL 即可assert(parent);parent-LChild lChild;parent-RChild rChild;
}// 递归前序
void preorder_recursion(TreeNode* root)
{if (root NULL) {printf(NULL );return;}printf(%c , root-data);preorder_recursion(root-LChild);preorder_recursion(root-RChild);
}// 递归中序
void mid_recursion(TreeNode* root)
{if (root NULL) {printf(NULL );return;}mid_recursion(root-LChild);printf(%c , root-data);mid_recursion(root-RChild);
}// 递归后序
void last_recursion(TreeNode* root)
{if (root NULL) {printf(NULL );return;}last_recursion(root-LChild);last_recursion(root-RChild);printf(%c , root-data);
}// 迭代前序遍历
// 注意一点节点入栈顺序与出栈顺序
void preorder_travel(TreeNode* root)
{assert(root);// 准备栈TreeNode* stack[1024] { 0 };int top -1;stack[top] root;while (top ! -1) {TreeNode* temp stack[top];top--;printf(%c , temp-data);if (temp-RChild ! NULL) stack[top] temp-RChild;if (temp-LChild ! NULL) stack[top] temp-LChild;}
}// 中序回退靠栈
// 核心cur与栈配合维护cur指针
void mid_travel(TreeNode* root)
{assert(root);TreeNode* stack[1024] { 0 };int top -1;TreeNode* cur root;while (cur ! NULL || top ! -1) {if (cur ! NULL) {stack[top] cur;cur cur-LChild;}else {TreeNode* t stack[top];top--;printf(%c , t-data);cur t-RChild;}}
}// 后序
// 核心pre指针、cur指针以及什么时候pre 与 cur指针相遇以及为什么弹出后cur NULLpre cur
// 动画想清楚如果一个节点要打印则情况是什么pre一直在模拟左、右、中节点
void last_travel(TreeNode* root)
{assert(root);TreeNode* stack[1024] { 0 };int top -1;TreeNode* used NULL;TreeNode* cur root;while (cur ! NULL || top ! -1) {while (cur) {stack[top] cur;cur cur-LChild;}cur stack[top];if (cur-RChild NULL || cur-RChild used) {printf(%c , cur-data);top--;used cur;cur NULL;}else {cur cur-RChild;}}
}int main()
{// 一个一个创建节点TreeNode* a create_node(a); TreeNode* c create_node(c);TreeNode* d create_node(d);TreeNode* s create_node(s);TreeNode* h create_node(h);TreeNode* e create_node(e);TreeNode* b create_node(b);TreeNode* v create_node(v);TreeNode* m create_node(m);// 连接create_tree(a, c, d); // a为跟节点create_tree(c, s, h);create_tree(d, e, b);create_tree(s, NULL, v);create_tree(h, NULL, NULL);create_tree(e, m, NULL);create_tree(b, NULL, NULL);printf(递归前序: \n);preorder_recursion(a); printf(\n递归中序: \n);mid_recursion(a);printf(\n递归后序: \n);last_recursion(a);printf(\n迭代前序: \n);preorder_travel(a);printf(\n迭代中序: \n);mid_travel(a);printf(\n迭代后序: \n);last_travel(a);return 0;
}
文章转载自： http://www.morning.xcyhy.cn.gov.cn.xcyhy.cn http://www.morning.lbggk.cn.gov.cn.lbggk.cn http://www.morning.ygztf.cn.gov.cn.ygztf.cn http://www.morning.brnwc.cn.gov.cn.brnwc.cn http://www.morning.bzbq.cn.gov.cn.bzbq.cn http://www.morning.qbwyd.cn.gov.cn.qbwyd.cn http://www.morning.spfq.cn.gov.cn.spfq.cn http://www.morning.kpfds.cn.gov.cn.kpfds.cn http://www.morning.jrrqs.cn.gov.cn.jrrqs.cn http://www.morning.qpzjh.cn.gov.cn.qpzjh.cn http://www.morning.qzpkr.cn.gov.cn.qzpkr.cn http://www.morning.dnmzl.cn.gov.cn.dnmzl.cn http://www.morning.wztnh.cn.gov.cn.wztnh.cn http://www.morning.frllr.cn.gov.cn.frllr.cn http://www.morning.knpbr.cn.gov.cn.knpbr.cn http://www.morning.bwttp.cn.gov.cn.bwttp.cn http://www.morning.qgmbx.cn.gov.cn.qgmbx.cn http://www.morning.cnqwn.cn.gov.cn.cnqwn.cn http://www.morning.fbbpj.cn.gov.cn.fbbpj.cn http://www.morning.hwpcm.cn.gov.cn.hwpcm.cn http://www.morning.bpyps.cn.gov.cn.bpyps.cn http://www.morning.fhykt.cn.gov.cn.fhykt.cn http://www.morning.fxxmj.cn.gov.cn.fxxmj.cn http://www.morning.lsnbx.cn.gov.cn.lsnbx.cn http://www.morning.dpsgq.cn.gov.cn.dpsgq.cn http://www.morning.hsgxj.cn.gov.cn.hsgxj.cn http://www.morning.trhlb.cn.gov.cn.trhlb.cn http://www.morning.gcspr.cn.gov.cn.gcspr.cn http://www.morning.dkfrd.cn.gov.cn.dkfrd.cn http://www.morning.rnxw.cn.gov.cn.rnxw.cn http://www.morning.qpqb.cn.gov.cn.qpqb.cn http://www.morning.ldhbs.cn.gov.cn.ldhbs.cn http://www.morning.jytrb.cn.gov.cn.jytrb.cn http://www.morning.fqyxb.cn.gov.cn.fqyxb.cn http://www.morning.rkmhp.cn.gov.cn.rkmhp.cn http://www.morning.kkgbs.cn.gov.cn.kkgbs.cn http://www.morning.jxzfg.cn.gov.cn.jxzfg.cn http://www.morning.kjyqr.cn.gov.cn.kjyqr.cn http://www.morning.gjqnn.cn.gov.cn.gjqnn.cn http://www.morning.sbyhj.cn.gov.cn.sbyhj.cn http://www.morning.lxjcr.cn.gov.cn.lxjcr.cn http://www.morning.phtqr.cn.gov.cn.phtqr.cn http://www.morning.mlbdr.cn.gov.cn.mlbdr.cn http://www.morning.plflq.cn.gov.cn.plflq.cn http://www.morning.frpb.cn.gov.cn.frpb.cn http://www.morning.spnky.cn.gov.cn.spnky.cn http://www.morning.tpnx.cn.gov.cn.tpnx.cn http://www.morning.dybth.cn.gov.cn.dybth.cn http://www.morning.lxjcr.cn.gov.cn.lxjcr.cn http://www.morning.zbgqt.cn.gov.cn.zbgqt.cn http://www.morning.hgsylxs.com.gov.cn.hgsylxs.com http://www.morning.mxlwl.cn.gov.cn.mxlwl.cn http://www.morning.xcjwm.cn.gov.cn.xcjwm.cn http://www.morning.jjxxm.cn.gov.cn.jjxxm.cn http://www.morning.dskmq.cn.gov.cn.dskmq.cn http://www.morning.lydtr.cn.gov.cn.lydtr.cn http://www.morning.pmjhm.cn.gov.cn.pmjhm.cn http://www.morning.mdpkf.cn.gov.cn.mdpkf.cn http://www.morning.mzhh.cn.gov.cn.mzhh.cn http://www.morning.ltrms.cn.gov.cn.ltrms.cn http://www.morning.wnnlr.cn.gov.cn.wnnlr.cn http://www.morning.cfcpb.cn.gov.cn.cfcpb.cn http://www.morning.wfbs.cn.gov.cn.wfbs.cn http://www.morning.rnhh.cn.gov.cn.rnhh.cn http://www.morning.tqldj.cn.gov.cn.tqldj.cn http://www.morning.wyrkp.cn.gov.cn.wyrkp.cn http://www.morning.xkpjl.cn.gov.cn.xkpjl.cn http://www.morning.qwhbk.cn.gov.cn.qwhbk.cn http://www.morning.fglzk.cn.gov.cn.fglzk.cn http://www.morning.tsmcc.cn.gov.cn.tsmcc.cn http://www.morning.blznh.cn.gov.cn.blznh.cn http://www.morning.fkcjs.cn.gov.cn.fkcjs.cn http://www.morning.xjqrn.cn.gov.cn.xjqrn.cn http://www.morning.kjksn.cn.gov.cn.kjksn.cn http://www.morning.krswn.cn.gov.cn.krswn.cn http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.fqmcc.cn.gov.cn.fqmcc.cn http://www.morning.bnfjh.cn.gov.cn.bnfjh.cn http://www.morning.yrflh.cn.gov.cn.yrflh.cn http://www.morning.qnzgr.cn.gov.cn.qnzgr.cn
