数据结构--树

2024年4月4日发(作者：)

二叉树

对任何一课二叉树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()

{

case 0://左子树还没有访问

Push(S,{,1});

if(->lchild) Push(S,{->lchild,0});

break;

case 1://左子树访问完了

Push(S,{,2});

if(->rchild) Push(S,{->rchild,0});

break;

case 2://右子树访问完了

visit();

}

}

}

中序非递归

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