树和二叉树
树的概念
树状结构是结点间有分支的，层次的结构，它是一种常见的又很重要的非线性结构。
递归定义：树是n($n\ge 0$)个结点的有限集合T，如果T为空，则它是一棵空树(null tree)，否则
- T中有一个特别标出的称为根(root)的结点；
- 除根结点之外，T中其余结点被分成m个($m\ge 0$)互不相交的非空集合$T_1，T_2,T_3,T_m$，其中每个集合本身又者是树。树$T_1,T_2,\cdots ,T_m$称为T的根的子树。
一些基本术语
- 度数（degree）∶一个结点的子树个数。
- 树叶（leaf）∶没有子树的结点称为树叶或终端结点。
- 分支结点（branch node）∶非终端结点。
- 子女（child）或儿子（son）∶一个结点的子树的根是该结点的子女（或儿子）。
- 父母（parent）∶若结点s是结点p的儿子，则称 p是s的父母或父亲。
- 兄弟（sibling）∶有相同父母结点的结点互为兄弟。
- 子孙（descendent）∶根为r的树（或子树）中所有结点都是r的子孙。除，之外，它们又都是r的真子孙（proper descendent）。
- 祖先（ancestor）∶从根r到结点p的路径（有且仅有一条这样的路径）上的所有辅点都是p的祖先。除p之外，它们又都是p的真祖先（proper ancestor）。有序树（ordered tree）∶树中各结点的儿子都是有序的。
- 层数（level）∶定义树根的层数为1，其他结点的层数等于其父母结点的层数加》
- 高度（或深度）（height）∶树中结点的最大层数，规定空树的高度为0。
- 树林（或森林）（forest）∶n（n≥0）个互不相交的树的集合。
二叉树
二叉树的概念
二叉树的每个结点至多有两个子女，而且子女有左、右之分。
递归定义： 二叉树由结点的有限集合构成，这个有限集合或者为空集，或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。
二叉树的性质
- 任何一棵含有n（$n\gt0$）个结点的二叉树恰有 n一1 条边。
- 深度为h的二叉树至多有$2^h-1$个结点（$h\ge 0$）。
- 设二叉树的结点个数为n，深度为h，则$\lceil log_2^(n+1)\rceil\le h\le n$
如果对一棵有n个结点的完全二叉树的结点，按层次次序编号（每层从左右），则对任一结点i（$1\le i\le n$），下述结论成立：为其父母结点。
- 若i=1，则结点i为二叉树的根结点；若 i>1，则结点$\lfloor \frac i2\rfloor$为其父母结点
- 若$2i\gt n$，则结点i无左子女;否则，结点2i为结点i左于女。
（3）若$2i+1\lt n$，则结点i无右子女;否则，结点2i+1为其右子女。
定义：
- 一棵深度为h且有$2^h-1$个结点的二叉树称为满二叉树(full binary tree)
- 深度为h且有n个结点的二叉树，当且仅当其每一个结点都与深度为h的满二叉树中编号从1~n的结点一一对应时，称为完全二叉树。
二叉树的存储方式
顺序存储
完全二叉树：将完全二叉树的结点按层次从左至右的顺序存放在一维数组中，完全二叉树中结点与结点的关系可由数组的下标来判断。
非完全二叉树：用对应的完全二叉树（空的用空结点补齐）
链接存储
- leftchild-rightchild表示法
结点的结构是leftchild-data-rightchild
struct binaryTreeNode
{
ElementType data;
struct binaryTreeNode *LeftChild, *RightChild;
};
typedef struct binaryTreeNode BinaryTreeNode;
void InitBinaryTreeNode(BinaryTreeNode * btree, ElementType e, BinaryTreeNode *l,BinaryTreeNode *r)
{
btree->LeftChild=l;
btree->RightCHild=r;
btree->data=e;
}
BinaryTreeNode *CreateBTreeNode itme, BinaryTreeNode *lptr, BinaryTreeNode *rptr)
{
Binary *p;
p=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
if(p==NULL)
printf("Memory allocation failure\n");
else
InitBinaryTreeNode(p,time,lptr,rptr);
return p;
}三重链结构表示
结点结构：
| Parent | Data |
|---|---|
| LeftChild | RightChild |
树（树林）与二叉树的相互转换
树（树林）与二叉树之间存在一种1-1对应的关系。规定树林中各树的根结点互为兄弟的结点。
对应关系：
- 原来树（树林）中结点 x的第一子女与二叉树中结点x 的左子女1-1对应；
- 原来树（树林）中结点x的下一兄弟与二叉树中结点x 的右子女1-1对应。
递归定义：
定义树林$F=(T_1,T_2,\cdots,T_n)$到二叉树B(F)的转换为：
- 若$n=0$，则B(F)是空的的二叉树：
- 若$n\gt0$，则B(F)的根是$T_1$的根$W_1$，$B(F)$的左子树是$B(T_{11},T_{12},\cdots,T_{1m})$其中$T_{11},T_{12},\cdots,T_{1m}$是$W_1$的子树；B(F)的右子树是$B(T_2,\cdots,T_n)$。
设B是一棵二叉树，是B的根，L是r的左子树，R是r的右子树，则对应于 B的树林F(B)的定义为∶
- 若B为空，则F(B)是空的树林；
- 若B不为空，则F(B)是一棵树$T_1$加上树林F(R)，其中树$T_1$的根为r，r的子树为F(L)。
树（树林），二叉树的遍历
树（树林）的遍历
遍历基本都是递归定义的。
遍历一棵树（或一片树林）就是按一定的次序系统地访问树（树林）的所有结点。
宽度方向遍历
首先依次访问层数为1的结点，然后访问层数为 2的结点，等等，直到访问完最底层的所有结点
深度方向遍历
- 先根次序（先根后子女）（1）访问头一棵树的根；（2）在先根次序下遍历头一棵树树根的子树；（3）在先根次序下遍历其他树。
- 后根次序（先子女后根）（1）在后根次序下遍历头一棵树树根的子树；（2）访问头一棵树的根；（3）在后根次序下遍历其他树。
二叉树的遍历
LR都是向下递归，只有N是输出结点，这样就好理解了。
- 前序法（NLR次序），递归定义为∶访问根结点；按前序遍历左子树；按前序遍历右子树。
- 后序法（LRN次序），递归定义为∶按后序遍历左子树；按后序遍历右子树；访问根。
- 对称序（中序、LNR 次序），递归定义为按对称序遍历左子树；访问根；按对称序遍历右子树。
任何一棵树（树林）的先根次序正好与对应的二叉树的前序序列对应，后根次序正好与对应二叉树的对称序序列对应。
抽象数据类型 BinaryTree 以及 BinaryTree 结构
抽象数据类型BinaryTree
定义 ADT BinaryTree为
数据∶指向二叉树树根的指针 root。
结构∶LeftChild-RightChild 表示。
操作∶
BinaryTree—-初始化操作，置空树。
IsEmpty——判二叉树是否为空，若二叉树非空，则返回 FALSE，否则返回。
GetRoot--求根结点的函数。
MakeTree（bt，element，left，right）——构造二叉树，其根结点为 element，左子树根结点的指针为 left，右子树根结点的指针为 right。
PreOrder（root）——按前序遍历以 root为根的二叉树。
InOrder（root）——按对称序遍历以 root为根的二叉树。
PostOrder（root）—按后序遍历以 root 为根的二叉树。
#include "binarytreenode.h"
struct binaryTree
{
BinaryTreeNode *root;
};
typedef struct binaryTree BinaryTree;
void InitBinaryTree(BinaryTree *bt)
{
bt->root=NULL;
}
Bool IsEmpty(BinaryTree *bt)
{
return((bt->root)?FALSE:TRUE);
}
Bool getRoot(BinaryTree *bt, ElementType *x)
{
if(bt->root)
{
* x=bt->root->data;
return TRUE;
}
else return FALSE;
}
BinaryTreeNode *MakeTree(BinaryTree *bt, ElementType element, BinaryTreeNode *left,BinaryTreeNode *right)
{
bt->root=(BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
if(bt->root==NULL){
printf("Memory allocation failure!]n");
exit(1);
}
InitBinaryTreeNode(bt->root,element,left,right);
return bt->root;
}
void PreOrder(BinaryTreeNode *t)
{
if(t)
{
printf("%c",t->data);
PreOrder(t->LeftChild);
PreOrder(t->RightChild);
}
}
void InOrder(BinaryTreeNode *t)
{
if(t){
InOrder(t->LeftChild);
printf("%c",t->data);
InOrder(t->RightChild);
}
}
void PostOrder(BinaryTreeNode *t)
{
if(t){
PostOrder(t->LeftChild);
PostOrder(t->RightChild);
printf("%c",t->data);
}
}二叉树的非遍历算法
非递归（使用栈）的遍历算法
栈是实现递归最常用的结构，对于用递归方式定义的二叉树，最自然的实现遍历运算的方式是使用一个栈用来记录尚待遍历的结点或于树信息<保存子树的信息只需保存子树根结点的信息），以便以后遍历。
下面给出二叉树的三种遍历方式 NLR、LNR、LRN 使用栈的非递归算法，对应的算法分别为算法7.1、算法7.2、算法7.3。进入算法时，设指针变量t指向待遍历的二叉树的根结点。算法7.3 还用到一个标志数组tag[100]，在后序遍历中，如果tag[i]=0表示对应栈中stack[i]记录的二叉树结点的左子树已遍历，右子树还没有遍历；tag[i]=1则表示stack[i]中记录的二叉树结点的左、右子树都已遍历。
书上的没看懂，看这个吧。
#include "stdio.h"
#include "stdlib.h"
typedef struct tree
{
char data;
struct tree *lchild;
struct tree *rchild;
}*Ptree;
typedef Ptree ElementType;
typedef struct SNode *Stack;
struct SNode{
ElementType Data;
struct SNode *Next;
};
Stack CreateStack();
//判断是否空
int IsEmpty(Stack S);
//Push操作
void Push(ElementType item,Stack S);
//Pop操作
ElementType Pop(Stack S);
//树的建立
Ptree createTree() ;
//先序遍历
void preOrder(Ptree t);
//中序遍历
void intOrder(Ptree t);
//后序遍历
void postOrder(Ptree t);
//利用栈先序遍历二叉树
void PreOderTraversal(Ptree BT);
//利用栈中序遍历二叉树
void InOderTraversal(Ptree BT);
//利用栈后序遍历
void PostOderTraversal(Ptree BT);
//利用双栈法后序遍历
void PostOderTraversal2(Ptree BT);
void main()
{
Ptree t;
printf("先序创建二叉树,用空格代表虚结点：\n");
t=createTree();
printf("前序遍历：");
preOrder(t) ;
printf("\n");
printf("利用堆栈前序遍历：");
PreOderTraversal(t);
printf("\n");
printf("\n");
printf("中序遍历：");
intOrder(t) ;
printf("\n");
printf("利用堆栈中序遍历：");
InOderTraversal(t);
printf("\n");
printf("\n");
printf("后序遍历：");
postOrder(t) ;
printf("\n");
printf("利用堆栈后序遍历：");
PostOderTraversal(t);
printf("\n");
printf("利用双栈法后序遍历：");
PostOderTraversal2(t);
system("pause");
}
//堆栈的建立
Stack CreateStack(){
Stack S;
S=(Stack)malloc(sizeof(struct SNode));
S->Next=NULL;
return S;
}
//判断是否空
int IsEmpty(Stack S){
return(S->Next==NULL);
}
//Push操作
void Push(ElementType item,Stack S){
struct SNode *TmpCell;
TmpCell=(struct SNode *)malloc(sizeof(struct SNode));
TmpCell->Data=item;
TmpCell->Next=S->Next;
S->Next=TmpCell;
}
//Pop操作
ElementType Pop(Stack S){
struct SNode *FirstCell;
ElementType TopElem;
if(IsEmpty(S)){
printf("堆栈空\n");
return NULL;
}else{
FirstCell=S->Next;
S->Next=FirstCell->Next;
TopElem=FirstCell->Data;
free(FirstCell);
return TopElem;
}
}
Ptree createTree() //树的建立
{
char ch;
Ptree t;
ch=getchar(); //输入二叉树数据
if(ch==' ') //判断二叉树是否为空
t=NULL;
else
{
t=(Ptree)malloc(sizeof(Ptree)); //二叉树的生成
t->data=ch;
t->lchild=createTree();
t->rchild=createTree();
}
return t;
}
void preOrder(Ptree t) //先序遍历
{
if(t)
{
printf("%c",t->data);
preOrder(t->lchild);
preOrder(t->rchild);
}
}
void intOrder(Ptree t) //中序遍历
{
if(t)
{
intOrder(t->lchild);
printf("%c",t->data);
intOrder(t->rchild);
}
}
void postOrder(Ptree t) //后序遍历
{
if(t)
{
postOrder(t->lchild);
postOrder(t->rchild);
printf("%c",t->data);
}
}
//利用栈先序遍历
void PreOderTraversal(Ptree BT){
Ptree T=BT;
Stack S=CreateStack();
while(T||!IsEmpty(S)){
while(T){
printf("%c",T->data);
Push(T,S);
T=T->lchild;
}
T=Pop(S);
T=T->rchild;
}
};
//利用栈中序遍历
void InOderTraversal(Ptree BT){
Ptree T=BT;
Stack S=CreateStack();
while(T||!IsEmpty(S)){
while(T){
Push(T,S);
T=T->lchild;
}
T=Pop(S);
printf("%c",T->data);
T=T->rchild;
}
};
//利用栈后序遍历
void PostOderTraversal(Ptree BT){
Ptree T=BT;
Ptree TempT=NULL;//Temp记录被检查的节点的右儿子
Stack S=CreateStack();
while(T||!IsEmpty(S)){
while(T){
Push(T,S);
T=T->lchild;
}
T=Pop(S);Push(T,S);//相当于返回了栈顶元素
// 当前节点的右孩子如果为空或者已经被访问，则访问当前节点
if(T->rchild==NULL||T->rchild==TempT){
printf("%c",T->data);
TempT=T;
Pop(S);
T=NULL;
}
// 否则访问右孩子
else
T=T->rchild;
}
};
//利用双栈法后序遍历
void PostOderTraversal2(Ptree BT) // 后序遍历的非递归 双栈法
{
Ptree T=BT; // 指向当前要检查的节点
Stack S1=CreateStack();
Stack S2=CreateStack();
Push(T,S1);
while(!IsEmpty(S1)) // 栈空时结束
{
T = Pop(S1);
Push(T,S2);
if(T->lchild)
Push(T->lchild,S1);
if(T->rchild)
Push(T->rchild,S1);
}
while(!IsEmpty(S2))
{
printf("%c", Pop(S2)->data);
}
}线索化二叉树的遍历
不难证明，任何一棵含有n个结点的二叉树的LeftChild、RightChild表示中，有n＋1 个空链域，仅有n一1个指针是非空的。A.J.Perlis 和 C.Thornton提出了构造线索化二叉树（threaded binary tree）的技术，把那些没有左或右子树的结点链域改为指向某种遍历次序下前驱或后继结点的指针（以下简称为线索）。按照前面介绍的 3 种遍历次序，可以建立前序穿线树、对称序穿线树和后序穿线树。
为了区分一个结点的指针域是指向其子女的指针，还是指向其前驱或后继（某种次序下）的线索，可在每个结点中增加两个线索标志域，这样，线索链表中的结点结构为
LeftChild ltag data rtag RightChild
其中tag=0表示指针，tag=1表示线索
对称序线索化二叉树建立后，借助于线索的帮助找指定结点的对称序后继变得很容易。如果指定结点的 RightChild为线索，则线索所指结点即为指定结点的对称序后继如果指定结点的 RightChild为指针，则指定结点有右子树，指定结点的对称序后继即为指定结点右子树的对称序第一个结点，也就是右子树最左下的结点。
考虑线索化二叉树的生长，当往对称序线索化的二叉树中插入一个新结点后，仍要保证插入后的二叉树仍按对称序线索化。设在*p的对称序后继*r前插入一新结点*q *q所指的新结点作为*p的右子树的根，*p所指的原来的右子树作为新结点的右子树，如图7.16所示。
下面给出对称序递归的算法。
#include <stdio.h>
#include <stdlib.h>
enum boolen{FALSE=0,TRUE};
typedef enum boolen Bool;
typedef int ElementType;
struct threadedBTNode
{
Bool ltag,rtag;
ElementType data;
struct threadedBTNode *LeftChild, *RightChild;
};
typedef struct threadedBTNode ThreadedBTNode;
//对称序线索化二叉树
void InorderThreaded(ThreadedBTNode *p,ThreadedBTNode **pre)
{
if(p!=NULL)//不处理空指针
{
InorderThreaded(p->LeftChild, pre);//对称序在向左子树递归时不会改变pre
if(*pre!=NULL && (*pre)->rtag==1)
(*pre)->RightChild=p;//修改右子树线索在这里，
if(p->LeftChild==NULL)
{//对称序遍历到左树叶的左线索，可以直接修改LeftChild
p->ltag=TRUE;
p->LeftChild=*pre;
}
if(p->RightChild==NULL)
{//然而遍历到右子树的右线索却不能修改RightChild
*pre=p;
}//这个p的后续要等到递归出去才能知道，
InorderThreaded(p->RightChild,pre);
//因为这个语句在最后面LN处理完了，所以递归出去后会一直回到栈中最近一个递归左子树的p，在上面代码中进行处理
//在图中表现就是会一直略过向右下的树枝，回到最近一个左下的树枝上。
}
}
//查找指定结点的对称后序
void Inordernext(ThreadedBTNode *p,ThreadedBTNode **q)
{
if(p->rtag==1){
*q=p->RightChild;
}
else
{
*q=p->RightChild;
while((*q)->ltag==0)
*q=(*q)->LeftChild;
}
}
//对称序遍历线索化二叉树
void ThreadedInTravel(ThreadedBTNode *p){
if(p!=NULL){
while(p->ltag==0) p=p->LeftChild;
do
{
printf("%c",p->data);
if(p->rtag==1)
p=p->RightChild;
else
{
p=p->RightChild;
while(p->ltag==0)
p=p->LeftChild;
}
}while(p!=NULL);
}
}
//在对称序线索化二叉树中插入一新结点
void InsertThreadedBT(ThreadedBTNode *p,ThreadedBTNode *q)
{
ThreadedBTNode *r;
if(p->RightChild==NULL)
{
r=NULL;
}else{//寻找p结点的后续位置
if(p->rtag==1){
r=p->RightChild;
}
else{
r=p->RightChild;
while(r->ltag==0)
r=r->LeftChild;
}
}
//建立新结点的左线索
q->ltag=TRUE;
q->LeftChild=p;
//建立新结点的右线索
q->RightChild=p->RightChild;
q->rtag=p->rtag;
//插入新结点
p->rtag=FALSE;
p->RightChild=q;
/*建立指定结点对称序后续的左线索*/
if((r!=NULL)&&(r->ltag==1))
r->LeftChild=q;
}