数据结构 | 二叉树

 可参照

数据结构：树(Tree)【详解】_数据结构 树_UniqueUnit的博客-CSDN博客

---

树

树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

树的高、深度vs结点的高、深度 

树的高度和深度 | 结点的高度和深度_树的高度从0开始还是1_Ann's Blog的博客-CSDN博客

---

 

祖先：考虑结点K。根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。

双亲&孩子：路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。

兄弟：有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。

堂兄弟：双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。
度：树中一个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。
分支结点：度大于0的结点称为分支结点(又称非终端结点);

叶子结点：度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。

有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。

路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。
注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。

森林。森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

---

 树、森林、二叉树相互转换：

 树、森林与二叉树的相互转换_森林转化为二叉树的方法_薛定谔的猫ovo的博客-CSDN博客

---

 树的表示法

左孩子——右兄弟（二叉链表法）

双亲表示法（单链表）

孩子链表（单链表）

---

树的遍历

树的先序遍历  ：二叉树的先序遍历

树的后序遍历：二叉树的中序遍历 

---

高度为H的满二叉树一定有2的H次方减1个结点

---

二叉树

基本形状

性质

---

---

结点数

对于二叉树

第m层：全满结点数为2的m-1次方

总结点数(总m层）：结点数为2的m次方减1

对于树

度为m的树中第i层上至多有m的i−1次方个结点
高度为h的m叉树至多有 （m的h次方−1)/(m−1)个结点

对于完全二叉树

可以找到它的最后一个分支结点：若是有n 个结点的完全二叉树，最后一个结点的编号是i，则它的双亲是i/2，就是最后一个分支结点

若是有n 个结点的完全二叉树，求高度，{log2​ n}+1

---

三种顺序遍历 

---

后序遍历 （非递归）

void PostOrder(BiTree){  // 全篇❤
	InitStack(s);
	BiTree *p=T,*r=NULL; // r标记最近访问过的结点
	while(p!=NULL || !IsEmpty(s)){
		if(p!=NULL){
			push(s,p);  // 一直向左走，左孩子入栈
			p=p->lchild;
		}
		else{
			GetTop(s,p);
			// 获取s的栈顶元素赋值给p
			// GetTop(s,p)意思就是判断栈顶元素的情况
			//❤case one❤
			if(p->rchild && p->rchild!=r){
			// 若右孩子存在且未被访问
				p=p->rchild;  // 就让右孩子
				push(s,p)  // 入栈
				p=p->lchild;  // 让右孩子向左
				//上面三句意思就是让右孩子的左孩子一直入栈，一直向左走
			}
			// ❤case two❤
			else{
				pop(s,p);  // 右孩子为空或未被访问过，就出栈
				visit(p->data);
				r=p;  // r标记最近访问结点
				p=NULL;  // r置空
				// 置空原因：因为这个结点已经出栈了
				//继续指向就没必要了，置空后r不标记任何结点
			}
		}
	}
}

口诀 

---

二叉树前，中，后，需要定义栈

层次需要使用队列

 层次遍历（队列）

void LevelOrder(BiTree T){
	InitQueue(Q);	//初始化辅助队列
	BiTree p;
	EnQueue(Q, T);	//将根节点入队
	while(!IsEmpty(Q)){	//队列不空则循环
		DeQueue(Q, p);	//队头结点出队
		visit(p);	//访问出队结点
		if(p->lchild != NULL){
			EnQueue(Q, p->lchild);	//左子树不空，则左子树根节点入队
		}
		if(p->rchild != NULL){
			EnQueue(Q, p->rchild);	//右子树不空，则右子树根节点入队
		}
	}
}

---

 静态三叉链

#define n 5
struct hnode
{
 float weight;
int llink;
int rlink;
int plink;
};
hnode huftree[2*n];