A. 二元樹的遍歷
##
## 1.前序遍歷二元樹:
(1)若二元樹為空,則為空操作,則返回空白。
(2)存取根結點。
(3)前序遍歷左子樹。
(4)前序遍歷右子樹。
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)重複步驟(2)、(3),直到p為空。
(5)從堆疊S彈出堆疊頂部元素,並將p指向此元素的右小孩。
(6)重複執行步驟(2)~(5),直到p為空且堆疊S也為空。
使用堆疊的前序遍歷的非遞歸演算法: 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;
}
}
}
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)中序遍歷左子樹。
void InOrderTraverse(BiTree BT)
{ if(BT)
{
InOrderTraverse(BT->lchild); //中序遍历左子树
printf("%c",BT->data); //访问根结点
InOrderTraverse(BT->rchild); //中序遍历右子树 }
}
(1)當樹為空時,將指標p指向根結點,p為目前結點指標。
(2)將p壓入堆疊S中,並令p指向其左子女。
(3)重複步驟(2),直到p為空白。
(4)從堆疊S彈出堆疊頂部元素,並將p指向此元素。
(5)存取目前結點p,並將p指向其右子。
(6)重複執行步驟(2)~(5),直到p為空且堆疊S也為空。
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;
}
}
}
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)); }
(1)若二元樹為空,則為空操作,返回空。
(2)後序遍歷左子樹。
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); } } }
更多常見問題的相關技術文章,請造訪常見問題欄位進行學習!
以上是二元樹的遍歷演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

國產AI黑馬DeepSeek強勢崛起,震撼全球AI界!這家成立僅一年半的中國人工智能公司,憑藉其免費開源的大模型DeepSeek-V3和DeepSeek-R1,在性能上與OpenAI等國際巨頭比肩,甚至在成本控制方面實現了突破性進展,贏得了全球用戶的廣泛讚譽。 DeepSeek-R1現已全面上線,性能媲美OpenAIo1正式版!您可以在網頁端、APP以及API接口體驗其強大的功能。下載方式:支持iOS和安卓系統,用戶可通過應用商店下載;網頁版也已正式開放! DeepSeek網頁版官方入口:ht

DeepSeek:火爆AI遭遇服務器擁堵,如何應對? DeepSeek作為2025年開年爆款AI,免費開源且性能媲美OpenAIo1正式版,其受歡迎程度可見一斑。然而,高並發也帶來了服務器繁忙的問題。本文將分析原因並提供應對策略。 DeepSeek網頁版入口:https://www.deepseek.com/DeepSeek服務器繁忙的原因:高並發訪問:DeepSeek的免費和強大功能吸引了大量用戶同時使用,導致服務器負載過高。網絡攻擊:據悉,DeepSeek對美國金融界造成衝擊,

2025年開年,國產AI“深度求索”(deepseek)驚艷亮相!這款免費開源的AI模型,性能堪比OpenAI的o1正式版,並已在網頁端、APP和API全面上線,支持iOS、安卓和網頁版多端同步使用。深度求索deepseek官網及使用指南:官網地址:https://www.deepseek.com/網頁版使用步驟:點擊上方鏈接進入deepseek官網。點擊首頁的“開始對話”按鈕。首次使用需進行手機驗證碼登錄。登錄後即可進入對話界面。 deepseek功能強大,可進行代碼編寫、文件讀取、創

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

記事本++7.3.1
好用且免費的程式碼編輯器

Dreamweaver CS6
視覺化網頁開發工具

Atom編輯器mac版下載
最受歡迎的的開源編輯器

SublimeText3漢化版
中文版,非常好用