数据结构--树

对任何一课二叉树n0=n2+1

BiTNode 或者*BiTree binarytreenode二叉树结点 二叉树的遍历有先(根)序，中(根)序，后(根)序 Preorder 都是将根结点作为参数传入 Inorder Postorder //递归算法

void Preorder(BiTree T) {

if(!T) return NULL;//有可能为空树 else{

visit(T);

Preorder(T->lchild); Preorder(T->rchild); } }

//中序非递归(用栈往上反)算法

核心就三句话：指针或栈不空就循环;指针不空就进栈，左走;否则出栈，访问，向右走 Status InOrderTraverse(BiTree T) {

InitStack(S);p=T;

while(p||!StackEmpty(S))//或者在循环之前将p进栈，那么条件改为(!StackEmpty(S)) {

if(p) {push(S,p);p=p->lchild;} else {

pop(S,p);visit(p); p=p->rchild; } }

return OK; }

//先序非递归(跟中序的唯一差别在于访问p的时机不同) Status PreOrderTraverse(BiTree T) {

InitStack(S);p=T;

while(p||!StackEmpty(S))//只有第一次循环栈是空的 {

if(p) {visit(p);push(S,p);p=p->lchild;} else {

pop(S,p); p=p->rchild; } }

return OK; }

//后序非递归

基本思想：需要区分两次进栈的不同返回点 typedef struct { BTNode *ptr;

enum{0,1,2} mark; } PMType;

void PostOrder_Stack(Bitree T) {

PMType a; InitStack(S); Push(S,{T,0});

while(!StackEmpty(S)) {

Pop(S,a);

switch(a.mark) {

case 0://左子树还没有访问 Push(S,{a.ptr,1});

if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); break;

case 1://左子树访问完了 Push(S,{a.ptr,2});

if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); break;

case 2://右子树访问完了 visit(a.ptr); } } }

中序非递归

GoFarLeft 取最左下角，没有左孩子的那个顶点,要用到栈

BiTNode GoFarLeft(BiTree T,Stack *s){ if(!T) return NULL; while(T) {

Push(s,T); T=T->lchild; }

return T;//这个时候T没有左孩子 }

//核心思想，找中序下第一个结点，访问完过后找后继，他或者是右子树中序下第一个结点(右子树最左下角结点)，或者是刚刚入栈的的结点(双亲结点) void Inorder_I(BiTree T) {

Stack *s;

if(!T) return NULL; else {

p=GoFarLeft(T,s);//找中序下访问的第一个结点 while(p){ visit(p);

if(p->rchild)//如果有右子树，那下一个就是右子树中序下第一个 p=GoFarLeft(p->rchild);

else if(!IsStackEmpty(s))//如果没有右子树，后继就是他的父结点 p=Pop(s); else

p=NULL; }

} }

//统计叶子结点个数,改自先序遍历的递归算法 CountLeaf

void CountLeaf(BiTree T,int &count) {

if((!T->lchild)&&(!T->rchild)) count++; else{

CountLeaf(T->lchild,count); CountLeaf(T->rchild,count); } }

//求二叉树的深度 Depth depthLeft

depthRight depthVal

int Depth(BiTree T) {

if(!T)return 0;//空树深度为0 else{

depthLeft=Depth(T->lchild); depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight? depthLeft:depthRight); } }

//求值为x的结点在二叉树中的层数 int GetDepth(GiTree &T,int x) {

if(T==NULL) return NULL; if(T->data==x) return 1; else{

j=GetDepth(T->lchild,x); i=GetDepth(T->rchild,x); return (i>j?i:j)+1; } }

//复制二叉树.复制左子树，复制右子树，利用指向左右子树的指针和给定数据建立根结点。递归

GetTreeNode 建立根结点 TelemType e树元素类型 lptr rptr

BiTNode GetTreeNode(TElemType e,BiTNode *lptr,BitNode *rptr) {

if(!T=(BiTree)malloc(sizeof(BiTNode))) exit(OVERFLOW); else{

T->data=e;T->lchild=lptr;T->rchild=rptr; }

return T; }

CopyTree newlptr newrptr

newT

重要提示，对于递归算法，你就按照递归局部的去理解，不要整个树或者图遍历去理解 BiTNode CopyTree(BiTree T) {

if(!T) return NULL; if(T->lchild)

newlptr=CopyTree(T->lchild);//如果有左子树就复制左子树 else

newlptr=NULL;

if(T->rchild)

newrptr=CopyTree(T->rchild);//如果有右子树就复制右子树 else

newrpt=NULL:

newT=GetTreeNode(T->data,newlptr,newrptr);//利用复制好的左右子树指针 return newT; }

//建立二叉树的存储结构(改自先序递归算法)创建根结点，创建左子，创建右子 Status

CreateBiTree ch

Status CreateBiTree(BiTree &T)//在已给指针下创建二叉树 {

scanf(&ch);//ch=getchar(); if(ch=='#') return NULL; else{

if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch;

CreateBiTree(T->lchild); CreateBiTree(T->rchild); } }

//线索二叉树 BiThrNode

LTag RTag 左右标志

Link Thread 左右标志的取值，分别代表0,1,指向孩子，指向前趋或后继 //中序遍历中序线索二叉树(可以达到非递归不用栈的效果) 问题1:第一个结点?最左下(没有左孩子的)结点

问题2:后继结点?若有右子树，为右子树中序下第一个结点(最左下) 否则，为后继线索所指向的结点 InOrderTraverse_Thr

void InOrderTraverse_Thr(BiTree T) {

if(!T) return NULL;

p=T->lchild; //注意这个T不是树的根结点而是另加的头结点 while(p!=T){

while(p->LTag==Link) p=p->lchild;visit(p); while(p->RTag==Thread && p->rchild!=T) { p=p->rchild;visit(p);}//有后继找后继

p=p->rchild; //没后继那肯定有右子树，进右子树 } }

//先序遍历中序线索二叉树

void PreOrderTraverse_Thr(BiTree T) {

if(!T) return NULL;

p=T->lchild; //注意这个T不是树的根结点而是另加的头结点 while(p!=T){

while(p->LTag==Link) {visit(p);p=p->lchild;} visit(p);

while(p->RTag==Thread && p->rchild!=T) { p=p->rchild;}//有后继找后继

p=p->rchild; //没后继那肯定有右子树，进右子树 } }

//建立中序线索链表(改自中序的递归算法) InThreading BiThrTree

void InThreading(BiThrTree p) {

if(p){

InThreading(p->lchild);

if(!p->lchild) {p->LTag=1;p->lchild=pre;} if(!pre->rchild) {pre->RTag=1;pre->rchild=p;} pre=p;

InThreading(p->rchild); } }

InOrderThreading

BiThrTree 线索二叉链表的结点类型 Thrt 线索二叉链表的头结点 pre p

注意头结点的左孩子指向后继，右孩子指向前趋，与其他结点相反 Status InOrderThreading(BiThrTree T){//将树的根结点传入 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);

Thrt->lchild=T;Thrt->LTag=Link;Thrt->RTag=Thread;Thrt-rchild=NULL; if(!T) Thrt-rchild=Thrt; else {

InThreading(T);//当p为空时线索化结束，pre指向最后一个结点 pre->RTag=Thread;pre->rchild=Thrt; Thrt->rchild=pre; }

return OK; } 树

//求树的深度 TreeDepth

CSTree 采用孩子兄弟链表进行存储 firstchild nextsibling

int TreeDepth(CSTree T){ if(!T) return NULL; else {

h1=TreeDepth(p->firstchild); h2=TreeDepth(p->nextsibling);

return ((h1+1)>h2? (h1+1):h2);//注意兄弟结点与根结点是在同一层的 } // 所以取他的深度作为树的深度不需要加一 }

//输出二叉树上从根到所有叶子结点的路径 AllPath BiTree Stack

void AllPath(BiTree T,Stack s){ if(T){

Push(s,T);

if(!T->lchild&&!T->rchild) PrintStack(s); else{

AllPath(T->lchild); AllPath(T->rchild); } Pop(s); } }

//输出森林中所有从根到叶子的路径 firstchild nextfibling

与上面的算法有两点不同

不同点一：左子树空的结点就是森林的叶结点

不同点二：不同的兄弟结点是在不同的路径上，所以每次向右走当前结点退栈 void OutPath(BiTree T,Stack &s){ if(T){

Push(s,T);

if(!T->firstchlid) printfStack(s); else

OutPath(T->firstchild); Pop(s);T=T->nextsibling; } }

//建立树的二叉链表存储结构 CreateTree CSTree 树类型

GetTreeNode 创建结点 GetHead 取得队头元素 firstchild nextsibling

根据输入的数队建立结点，在队列中寻找双亲结点，判断双亲结点是否有孩子，如果没有，直接连上，如果有，那么连到同样以该结点为双亲的刚刚建立的结点上 void CreateTree(CSTree T){ T=NULL;

for(scanf(&fa,&ch);ch!='#';scanf(&fa,&ch);){ p=GetTreeNode(ch); EnQueue(p);

if(fa='#') p=T;//输入的是第一个结点 else {

GetHead(Q,s);

while(s->data!=ch)

{DeQueue(Q,s);GetHead(Q,s);}

if(!s->firstchild) {s->firstchild=p;r=p;} else {r->nextsibling=p;r=p;} } } }