二叉樹的先序遍歷要用棧嗎

1樓：網友

不用。用以下格式遞迴就好：

typedef struct node

char data;//節點資訊。

struct node *lchild;//左孩子struct node *rchild;//右孩子btnode;//定義二叉樹。

*建立二叉樹（省略）

void xianxu(btnode*&b)//先序btnode *p=b;

if(p!=null)

printf("%c ",p->data);/輸出當前根節點。

xianxu(p->lchild);/遍歷左子樹。

xianxu(p->rchild);/遍歷右子樹。

為什麼二叉樹的前序遍歷和中序遍歷對應入棧和出棧次序

2樓：仁昌居士

前序遍歷是按來照根左右源的順序訪問的。假設首先進棧的節點是p，前序序列是訪問該節點p以後該結點p進棧，然後去訪問p的左子樹，訪問p的左子樹的時候，也是先訪問左子樹根節點即p的左孩子，然後根節點入棧。先一路從根壓到最左邊的結點，左子樹都處理完了，才開始訪問右子樹。

中序遍歷是按照左根右的順序訪問的。假設首先出棧的節點是p，中序序列是訪問該節點p以後該結點p出棧，然後去訪問p的左節點，訪問p的左節點的時候，也是先訪問左節點的根節點即p的父親，然後左節點出棧。先一路從左壓到根部的結點，左子樹都處理完了，才開始訪問右子樹。

3樓：網友

二叉樹的抄定義是遞迴的。

襲遍歷的過程也是遞迴的。bai

遞迴在系統裡。

du面的實現是通過堆zhi棧完成的。dao在函式體本身入棧的時候，帶有被入棧函式體的位址和值。有點像是goto語句的標記tag或lab，在入棧的時候做了個標記一樣。

函式體出棧的時候，會得到出棧函式體的位址和值。有點像goto語句跳到之前做好的標記一樣。

這張圖表示的是圖的深度遍歷的時候，遞迴棧是怎麼運作的，拿來解釋二叉樹遍歷的遞迴棧運作道理是一樣的。

遞迴的時候本身系統會自動分配管理堆疊。

如果寫成迭代就要自己分配出棧和入棧。

二叉樹的後序遍歷是什麼?

4樓：教育小百科達人

後序遍歷是dgebhfca。

前序遍歷的第乙個節點為根節點，由前序遍歷可知，a為根節點。中序遍歷的根節點前面的節點均為左子樹的節點，所以左子樹上的節點為dbge。

去掉根節點和左子樹節點，右子數節點為chf。前序遍歷的第二個節點為b，由2知b為左子樹節點，所以b為左子樹的根節點。

在二叉樹中，求後序遍歷，先左後右再根，即首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。則該二叉樹的後序遍歷是dgebhfca。

二叉樹的後序遍歷是什麼意思？

5樓：博學小趙愛生活

樹的後序遍歷是指先依次後序遍歷每棵子樹，然後訪問根結點。當樹用二叉樹表示法(也叫孩子兄弟表示法)儲存時，可以找到唯一的一棵二叉樹與之對應，我們稱這棵二叉樹為該樹對應的二叉樹。那麼根據這個法則可知，樹的後序遍歷序列等同於該樹對應的二叉樹的中序遍歷。

從二叉樹的遞迴定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上。

訪問結點本身（n），⑵遍歷該結點的左子樹（l），⑶遍歷該結點的右子樹（r）。

以上三種操作有六種執行次序：

nlr、lnr、lrn、nrl、rnl、rln。

注意：前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。

從二叉樹的遞迴定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上。