バイナリ ツリー トラバーサル アルゴリズム
- 步履不停オリジナル
- 2019-06-20 11:51:0722396ブラウズ
A. バイナリ ツリー トラバーサル
1. バイナリ ツリーの事前順序トラバーサル:
(1) バイナリ ツリーが空の場合、それは何も行わず、空を返します。
(2) ルート ノードにアクセスします。
(3) 左側のサブツリーの事前順序走査。
(4) Preorder は、右のサブツリーをトラバースします。
a. バイナリ ツリーの事前順序走査のための再帰的アルゴリズム:
void PreOrderTraverse(BiTree BT)
{ if(BT)
{
printf("%c",BT->data); //访问根结点
PreOrderTraverse(BT->lchild); //前序遍历左子树
PreOrderTraverse(BT->rchild); //前序遍历右子树 }
} b. スタックを使用して各ノードの正しいサブツリーを保存するバイナリ ツリー事前順序トラバーサルの非再帰アルゴリズム:
( 1) ツリーが空の場合、ポインタ p はルート ノードを指します。p は現在のノード ポインタです。
(2) まず現在のノード p にアクセスし、p をスタック S にプッシュします。
(3) p がその左の子を指すようにします。
(4) p が空になるまで手順 (2) と (3) を繰り返します。
(5) スタック S から最上位の要素をポップし、p をこの要素の右側の子にポイントします。
(6) p が空になり、スタック S も空になるまで、手順 (2) ～ (5) を繰り返します。
(7) トラバースが終了します。
スタックの事前順序走査を使用する非再帰アルゴリズム:
void PreOrderNoRec(BiTree BT)
{
stack S;
BiTree p=BT->root; while((NULL!=p)||!StackEmpty(S))
{ if(NULL!=p)
{
printf("%c",p->data);
Push(S,p);
p=p->lchild;
} else
{
p=Top(S);
Pop(S);
p=p->rchild;
}
}
}c. バイナリ リンク リストを使用するstorage バイナリ ツリーの事前順序走査のための非再帰アルゴリズム:
void PreOrder(pBinTreeNode pbnode)
{
pBinTreeNode stack[100];
pBinTreeNode p; int top;
top=0;
p=pbnode; do
{ while(p!=NULL)
{
printf("%d\n",p->data); //访问结点p
top=top+1;
stack[top]=p;
p=p->llink; //继续搜索结点p的左子树 } if(top!=0)
{
p=stack[top];
top=top-1;
p=p->rlink; //继续搜索结点p的右子树 }
}while((top!=0)||(p!=NULL));
}2. バイナリ ツリーの順序どおりの走査:
( 1) バイナリ ツリーが空の場合、それは何も行わず、何も返しません。(2) 左側のサブツリーを順番に走査します。
(3) ルート ノードにアクセスします。
(4) 右側のサブツリーを順番に走査します。
void InOrderTraverse(BiTree BT)
{ if(BT)
{
InOrderTraverse(BT->lchild); //中序遍历左子树
printf("%c",BT->data); //访问根结点
InOrderTraverse(BT->rchild); //中序遍历右子树 }
}
b. スタック ストレージを使用したバイナリ ツリーの順序トラバーサルのための非再帰アルゴリズム:
(2) p をスタック S にプッシュし、p がその左の子を指すようにします。
(3) p が空になるまで手順 (2) を繰り返します。
(4) スタック S から最上位の要素をポップし、p がこの要素を指すようにします。
(5) 現在のノード p にアクセスし、p をその右側の子にポイントします。
(6) p が空になり、スタック S も空になるまで、手順 (2) ～ (5) を繰り返します。
(7) トラバースが終了します。
スタックの順序トラバーサルを使用した非再帰アルゴリズム:
void IneOrderNoRec(BiTree BT)
{
stack S;
BiTree p=BT->root; while((NULL!=p)||!StackEmpty(S))
{ if(NULL!=p)
{
Push(S,p);
p=p->lchild;
} else
{
p=Top(S);
Pop(S);
printf("%c",p->data);
p=p->rchild;
}
}
}
c. 次を使用します。バイナリ フォーク リンク リストに格納されたバイナリ ツリーを順番に走査するための非再帰アルゴリズム:
void InOrder(pBinTreeNode pbnode)
{
pBinTreeNode stack[100];
pBinTreeNode p; int top;
top=0;
p=pbnode; do
{ while(p!=NULL)
{
top=top+1;
stack[top]=p; //结点p进栈
p=p->llink; //继续搜索结点p的左子树 } if(top!=0)
{
p=stack[top]; //结点p出栈
top=top-1;
printf("%d\n",p->data); //访问结点p
p=p->rlink; //继续搜索结点p的右子树 }
}while((top!=0)||(p!=NULL));
}
3. 事後走査バイナリ ツリー:
(2) 左側のサブツリーの事後走査。
(3) 右サブツリーの事後走査。
(4) ルート ノードにアクセスします。
void PostOrderTraverse(BiTree BT)
{ if(BT)
{
PostOrderTraverse(BT->lchild); //后序遍历左子树
PostOrderTraverse(BT->rchild); //后序遍历右子树
printf("%c",BT->data); //访问根结点 }
}b.使用栈存储的二叉树后序遍历的非递归算法：
算法思想：首先扫描根结点的所有左结点并入栈，然后出栈一个结点，扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈，当一个结点的左、右子树均被访问后再访问该结点。因为在递归算法中，左子树和右子树都进行了返回，因此为了区分这两种情况，还需要设置一个标识栈tag，当tag的栈顶元素为0时表示从左子树返回，为1表示从右子树返回。
(1)当树为空时，将指针p指向根结点，p为当前结点指针。
(2)将p压入栈S中，0压入栈tag中，并令p指向其左孩子。
(3)重复执行步骤(2)，直到p为空。
(4)如果tag栈中的栈顶元素为1，跳至步骤(6)。
(5)如果tag栈中的栈顶元素为0，跳至步骤(7)。
(6)将栈S的栈顶元素弹出，并访问此结点，跳至步骤(8)。
(7)将p指向栈S的栈顶元素的右孩子。
(8)重复执行步骤(2)~(7)，直到p为空并且栈S也为空。
(9)遍历结束。
使用栈的后序遍历非递归算法：
void PostOrderNoRec(BiTree BT)
{
stack S;
stack tag;
BiTree p=BT->root; while((NULL!=p)||!StackEmpty(S))
{ while(NULL!=p)
{
Push(S,p);
Push(tag,0);
p=p->lchild;
} if(!StackEmpty(S))
{ if(Pop(tag)==1)
{
p=Top(S);
Pop(S);
printf("%c",p->data);
Pop(tag); //栈tag要与栈S同步 } else
{
p=Top(S); if(!StackEmpty(S))
{
p=p->rchild;
Pop(tag);
Push(tag,1);
}
}
}
}
}c.使用二叉链表存储的二叉树后序遍历非递归算法：
void PosOrder(pBinTreeNode pbnode)
{
pBinTreeNode stack[100]; //结点的指针栈 int count[100]; //记录结点进栈次数的数组 pBinTreeNode p; int top;
top=0;
p=pbnode; do
{ while(p!=NULL)
{
top=top+1;
stack[top]=p; //结点p首次进栈
count[top]=0;
p=p->llink; //继续搜索结点p的左子树 }
p=stack[top]; //结点p出栈
top=top-1; if(count[top+1]==0)
{
top=top+1;
stack[top]=p; //结点p首次进栈
count[top]=1;
p=p->rlink; //继续搜索结点p的右子树 } else
{
printf("%d\n",p->data); //访问结点p
p=NULL;
}
}while((top>0));
}B 线索化二叉树：
typedef struct node
{
DataType data; struct node *lchild, *rchild; //左、右孩子指针 int ltag, rtag; //左、右线索
}TBinTNode; //结点类型
typedef TBinTNode *TBinTree;
(1)中序线索化二叉树的算法：
void InOrderThreading(TBinTree p)
{ if(p)
{
InOrderThreading(p->lchild); //左子树线索化 if(p->lchild)
p->ltag=0; else
p->ltag=1; if(p->rchild)
p->rtag=0; else
p->rtag=1; if(*(pre)) //若*p的前驱*pre存在 { if(pre->rtag==1)
pre->rchild=p; if(p->ltag==1)
p->lchild=pre;
}
pre=p; //另pre是下一访问结点的中序前驱
InOrderThreading(p->rchild); //右子树线索化 }
}(2)在中序线索化二叉树下，结点p的后继结点有以下两种情况：
①结点p的右子树为空，那么p的右孩子指针域为右线索，直接指向结点p的后继结点。②结点p的右子树不为空，那么根据中序遍历算法，p的后继必是其右子树中第1个遍历到的结点。
TBinTNode *InOrderSuc(BiThrTree p)
{
TBinTNode *q; if(p->rtag==1) //第①情况 return p->rchild; else //第②情况 {
q=p->rchild; while(q->ltag==0)
q=q->lchild; return q;
}
}中序线索化二叉树求前驱结点的算法：
TBinTNode *InOrderPre(BiThrTree p)
{
TBinTNode *q; if(p->ltag==1) return p->lchild; else
{
q=p->lchild; //从*p的左孩子开始查找 while(q->rtag==0)
q=q->rchild; return q;
}
}(3)遍历中序线索化二叉树的算法
void TraversInOrderThrTree(BiThrTree p)
{ if(p)
{ while(p->ltag==0)
p=p->lchild; while(p)
{
printf("%c",p->data);
p=InOrderSuc(p);
}
}
}一般的な問題に関連する技術的な記事については、FAQ 列にアクセスして学習してください。
以上がバイナリ ツリー トラバーサル アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。