博客

树与二叉树

二叉树是有序树，若将其左右子树颠倒，则成为另一棵不同的二叉树。即使是树中节点只有一颗子树，也要区分它是左子树还是右子树。

特殊的二叉树：

1. 满二叉树：一棵高度为h，且含有2
   
   ^h
   
   -1个节点的二叉树成为满二叉树，即树中的每层含有最多的节点。

2. 完全二叉树：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

• 若i <
  
  
  
  ⌊

  n

  /

  2

  ⌋

  \lfloor n/2 \rfloor
  
  
  
  
  
  
  ⌊
  
  
  n
  
  
  /
  
  
  2
  
  
  ⌋
  
  
  
  
  
  ，则节点I为分支节点，否则为叶子结点

• 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点都依次排列在该层最左边的位置上
• 若有度为1的节点，则只可能有一个，且该节点只有左孩子而无右孩子
• 按层序编号后，一旦出现某节点(编号为i)为叶子结点或只有左孩子，则编号大于i的节点均为叶子结点
• 若n为奇数，则每个分支节点都有左孩子和右孩子；若n为偶数，则变好最大的分支节点(编号为n/2)只有左孩子，没有右孩子，其余分支节点左右孩子都有。

3. 二叉排序树：左子树上所有节点的关键字都小于跟节点的关键字；右子树上的所有节点的关键字都大于跟节点的关键字；左子树和右子树又各是一棵二叉排序树
4. 平衡二叉树：树上任意节点的左子树和右子树的深度之差不超过1

二叉树的存储结构

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的节点元素，即将完全二叉树上编号为i的节点元素存储在一维数组下标为i的分量中

依据二叉树的性质，完全二叉树和满二叉树更适合采用顺序存储。

链式存储，采用链表来完成对二叉树的存储。

二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个节点，使得每个节点均被访问一次，而且仅被访问一次。

常见的遍历次序：先序(NLR)，中序(LNR)，后序(LRN)

//先序遍历
void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
//中序遍历
void InOrder(BiTree T){
	if(T != NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

//后序遍历
void PostOrder(BiTree T){
	if(T != NULL){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

由二叉树的先序序列和中序序列可以唯一确定一棵二叉树；

由二叉树的后序序列和中序序列可以唯一确定一棵二叉树；

线索二叉树

作用：加速二叉树的遍历

规定：若无左子树，令lchild指向其前驱节点；若无右子树，令rchild指向其后继节点。

再增加两个标志域标识指针域是指向左(右)孩子还是前驱(后继)