树和二叉树
一. 树
-
树的定义(递归)
树是n(n>=0)个节点的有限集。
若n=0，称为空树；
若n>0，则满足以下两个条件：
(1)有且仅有一个特定称为根的节点；
(2)其余节点可分为m(m>=0)个互不相交的有限集T1，T2…，Tm，其中每一个集合本身又是一棵树，并成为根的子树(SubTree)
-
树的基本术语
根结点：非空树中无前驱结点的结点。
结点的度：结点拥有的子树数。
树的度：树内各节点的度的最大值。
叶子（终端）结点：度=0。
分支节点（非终端结点）：度！=0。根结点以外的分支节点称为内部结点。
树的深度：树中结点的最大层次。
结点的子树的根称为该结点的孩子，该节点称为孩子的双亲。如果有共同的双亲，则互称为兄弟。位于同一层的结点为堂兄弟。结点的祖先：从根到该结点所经分支上的所有结点。
结点的子孙：以某结点为根的子树中任意结点。
有序树：树中结点的各子树从左到右有次序（最左边的为第一个孩子）。
无序树：树中结点的各子树无次序。
森林：是m（m>=0)棵互不相交的树的集合。
把根节点删除，树就变成了森林。
一棵树可以看做一个特殊的森林。
二. 二叉树
-
二叉树的定义
二叉树是n（n>=0）个结点的有限集，它或者是空集，或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。
特点
1、每个节点最多有两个孩子（二叉树中不存在度大于2的结点）。
2、子树有左右之分，其次序不能颠倒。
3、二叉树可以是空集合，根可以有空的左子树或空的右子树。
二叉树不是树的特殊情况，他们是两个概念。
二叉树及时只有一棵树也必须进行区分为左子树还是右子树。
-
二叉树的性质和存储结构
2.1性质
性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）。
性质2：深度为k的二叉树至多有2k-1个结点（k>=1）。
性质3：对任何一颗二叉树T，如果其叶子树为n0，度为2的结点数为n2，则n0=n2+1.
-
两种特殊形式的二叉树
编号：从上到下，从左到右
1.满二叉树：一颗深度为k且有2k-1个结点的二叉树称为满二叉树
2.完全二叉树：深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。
完全二叉树的性质
性质4：具有n个结点的完全二叉树深度为[log2n]+1.([x]的意思是向下取整)
性质5: 一棵有n个结点的完全二叉树,对任意结点i,有:如果i=1,则i为二叉树的根,如果i>1,则其双亲结点是[i/2]
如果2i>n,则结点i为叶子结点,无左孩子;否则,其左孩子是结点2i
如果2i+1>n,则结点i无右孩子;否则,其右孩子结点为2i+1.
2.2存储结构
2.2.1 顺序存储结构
实现: 按满二叉树的结点层次编号,依次存放二叉树中的数据元素.
通过编码按顺序将二叉树中的元素存储进数组中.(二叉树中空结点依然要占据数组中的一个位置设为空)
缺点: 容易浪费空间.
特点: 适合于存满二叉树和完全二叉树
2.2.2 链式存储结构
实现: 通过指针,将各个地址的元素串联起来.
typedef struct biNode {int data;struct biNode *left;struct biNode *right;//指向左孩子和右孩子 }biNode,*biTree; -
-
-
-
在n个结点的二叉链表中,有n+1个空指针域
-
遍历二叉树
3.1 遍历二叉树算法描述:
遍历方法: 依次遍历二叉树中的三个组成部分 L遍历左子树; D访问根结点; R遍历右子树. 则遍历整个二叉树的方案有:
DLR,LDR,LRD,DRL,RDL,RLD六种.
若规定先左后右,则只有前三种情况:
DLR——先(根)序遍历 LDR——中(根序遍历) LRD——后(根)序遍历
3.1.2 先序遍历:若二叉树为空,则进行空操作;否则 （1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。
例：
3.1.3 中序遍历：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
例：
3.1.4 后序遍历：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
例：
3.2 二叉树的递归遍历
3.2.1 先序递归遍历
void preOrder(biTree T) {// 先序递归遍历二叉树if(T != NULL) {printf("%d ", T->data);//访问根结点preOrder(T->left);// 递归遍历左节点preOrder(T->right);// 递归遍历右节点}
}
3.2.2 中序递归遍历
void inOrder(biTree T) {// 先序递归遍历二叉树if(T != NULL) {inOrder(T->left);// 递归遍历左节点printf("%d ", T->data);//访问根结点inOrder(T->right);// 递归遍历右节点}
}
3.2.3 后续递归遍历
void postOrder(biTree T) {// 先序递归遍历二叉树if(T != NULL) {postOrder(T->left);// 递归遍历左节点postOrder(T->right);// 递归遍历右节点printf("%d ", T->data);//访问根结点}
}
3.3 中序遍历的非递归算法（栈）
基本思想：（1）建立一个栈；（2）根结点进栈，遍历左子树；（3）根节点出栈，输出根结点，遍历右子树。
void inOrder2(biTree T) {initStack(S);//初始化栈biTree p = T;//p为用来遍历的指针while(p ||!=isEmpty) {// p或栈不为空时进循环if(p) {//向佐Push(S,p);//当前节点入栈p = p->left;//若左孩子不为空,则一直向左走}else {//出栈,并转向出栈节点的右孩子Pop(S,p);//栈顶元素出栈printf("%d ",p->data);//访问出栈节点p = p->right;//向右走}}
}
3.4 二叉树的层次遍历（队列）
概念：对于一颗二叉树，从根结点开始，按从上到下，从左到右的顺序访问每一个节点。每个节点仅访问一次。
基本思想：（1）将二叉树的根节点入队；
（2）若队列非空，则将队列头结点出队并访问该结点，若它有左孩子，则将其左孩子入队；若它有右孩子，则将其右孩子入队；
（3）重复（2），直至队列为空。
void levelOrder(biTree T) {initQueue(Q);//初始化辅助队列biTree p;//p为用来遍历的指针enQueue(Q,T);//将根节点入队while(!isEmpty(Q)) {//若队列不空,则进入循环deQueue(Q,p);//队头节点出队printf("%d ",p->data);//访问出队节点if(p->left!=NULL) {enQueue(Q,p->left);//若左孩子不为空,则左孩子入队}if(p->right!=NULL) {//若右孩子不空,则右孩子入队enQueue(Q,p->right);}}
}
图片源自:数据结构与算法
部分代码参考:CSDN
