考研408总结【数据结构】---树与二叉树（上）
本篇先总结树的基本概念和计算、二叉树的遍历和线索二叉树的内容。
下篇总结树和森林、以及应用（二叉排序树、平衡二叉树、哈夫曼树）的内容。
树的性质
树的结点数等于所有结点的度数加1.
度为m的树中第i层上至多有mi−1m^{i-1}mi−1个结点（i>=1)
高度为h，度为m的树【度为m的树指的是结点最多有m个孩子结点】至多有mh−1m−1\frac{m^{h}-1}{m-1}m−1mh−1个结点.
（推导利用等比数列的求和公式）
具有sum个结点，度为m的树的最小高度为⌈logm(sum(m−1)+1)⌉\lceil log_m(sum(m-1)+1) \rceil⌈logm(sum(m−1)+1)⌉
(利用第三个公式逆推得到h，注意是向上取整)
二叉树的性质
二叉树的第i层上至多有2i−12^{i-1}2i−1个结点
深度为k的二叉树至多有2k−12^k-12k−1个结点.
对于一棵非空二叉树，如果叶子节点数为m0m_0m0,度为2的结点数m2m_2m2,则有m0=m2+1m_0=m_2+1m0=m2+1
（重点经常在选择题遇到！！！）
具有n个结点的完全二叉树的深度为⌊log2n⌋+1\lfloor log_2 n \rfloor+1⌊log2n⌋+1
任何一棵完全二叉树中度为1的结点数要么有1个，要么就没有.
二叉树的遍历
下面是三种遍历的递归代码，后续很多题型以此拓展得来。
//二叉树的存储结构 typedef struct BTNode{ char data; struct BTNode *lchild; struct BTNode *rchild; } //先序遍历 根左右 void preorder(BTNode *p){ if(p!=NULL){ Visit(p);//对p进行访问。比如打印p对应的数值 preorder(p->lchild); preorder(p->rchild); } } //中序遍历 左根右 void inorder(BTNode *p){ if(p!=NULL){ inorder(p->lchild); Visit(p); inorder(p->rchild); } } //后序遍历 左右根 void postorder(BTNode *p){ if(p!=NULL){ postorder(p->lchild); postorder(p->rchild); Visit(p); } } 复制代码相关题型
表达式(a-(b+c))*(d/e)存储在一棵以二叉链表为存储结构的二叉树中，编写程序求表达式的值。（提示，左右子树不为空则为表达式，用后序遍历求值，左右子树都为空，则为数值）
求一棵二叉树的深度。（提示左右子树深度最大值＋1）
查找二叉树中等于key的结点是否存在。
根据前和后遍历序列不能确定二叉树
输出先序（中/后）遍历序列中第k个结点的值
使用非递归算法描述先序后序中序代码(利用栈)
下面是层次遍历的代码
//层次遍历 void level(BTNode *p){ int front,rear; BTNode *que[maxSize]; //定义一个循环队列 front=rear=0; BTNode *q; if(p!=NULL){ rear=(rear+1)%maxSize; que[rear]=p; //根结点入队 while(front!=rear){ front=(front+1)%maxSize; q=que[front]; //队头结点出队 Visit(q); if(q->lchild!=NULL){ //左子树不空，左子树的根结点入队 rear=(rear+1)%maxSize; que[rear]=q->lchild; } if(q->rchild!=NULL){ //右子树不空，右子树的根结点入队 rear=(rear+1)%maxSize; que[rear]=q->rchild; } } } } 复制代码线索二叉树
有一棵结点数目为n的二叉树，采用二叉链表的形式存储。二叉链表中存在n+1个空指针域。
可以利用这些空指针进行线索化。
若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。
若结点的右子树为空，则该结点的右孩子指针指向其后继结点。
图片来自Chilan Yuk
【习题】
【2010年408】
【2014年408】
作者：陈奕湫
链接：https://juejin.cn/post/7025934339791650853