二叉樹非遞歸遍歷方法小結，二叉樹非遞歸小結

二叉樹非遞歸遍歷方法小結，二叉樹非遞歸小結

二叉樹的遍歷是面試中經常考察的，其實前中後三種順序的遍歷都大同小異，自己模擬兩個棧用筆畫畫我相信是不難寫出代碼的。現羅列如下，均是自己所寫已通過leetcode。

 1 class Solution {
 2 public:
 3     vector<int> preorderTraversal(TreeNode *root) {
 4         vector<int> out;
 5         stack<TreeNode*> s;
 6         s.push(root);
 7         while(!s.empty() && root){
 8             TreeNode *node = s.top();
 9             out.push_back(node->val);
10             s.pop();
11             if(node->right) s.push(node->right);
12             if(node->left)  s.push(node->left);
13         }
14         return out;
15         
16     
17     }
18     vector<int> inorderTraversal(TreeNode *root) {
19         stack<TreeNode *> s;
20         vector<int> out;
21         TreeNode *node = root;
22         bool done = false;
23         while(!done){
24             if(node){
25                 s.push(node);
26                 node = node->left;
27             }else {
28                 if(s.empty()) done = true;
29                 else{
30                     node = s.top();
31                     s.pop();
32                     out.push_back(node->val);
33                     node = node->right;
34                 }
35             }
36         }
37         return out;
38     }
39     vector<int> postorderTraversal(TreeNode *root) {
40        vector<int> out;
41        stack<TreeNode*> s;
42        TreeNode* node = root;
43        s.push(node);
44        while(!s.empty()&&node){
45            node = s.top();
46            out.push_back(node->val);
47            s.pop();
48            if(node->left) s.push(node->left);
49            if(node->right)s.push(node->right);
50        }
51        reverse(out.begin(),out.end());
52        return out;
53     }
54 };

二叉樹的非遞歸遍歷

哈，我們數據結構的實驗：
typedef int Status;
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, * rchild;//左右孩子指針
}BiTNode, *BiTree;
typedef struct SqQueue
{
TElemType front ,rear ;
BiTree data[MAXQSIZE]; //循環隊列元素類型為二叉鏈表結點指針
int count;
}SqQueue; //循環隊列結構定義
int stack[MAX_TREE_SIZE],top=0;

Status CreateBiTree(BiTree *T)
{
//按先序輸入二叉樹中的結點的值（一個字符）,空格字符表示空樹
//構造二叉鏈表表示的二叉樹T
TElemType input;
if(!(*T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
fflush(stdin);
if(!fscanf(in,"%d",&input))
{
printf("Read Data Error!");
getch();
exit(0);
}
if(input==-1)
{
*T = NULL;
return FALSE;
}
else
{
(*T)->data=input;
//printf("%d",input);
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return OK;
}

Status PreOrderTraverse(BiTree T)
{
//先序遍歷二叉樹T的遞歸算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
elsereturn OK;
}
Status PreOrder(BiTree T)
{
//先序遍歷二叉樹T的非遞歸算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍歷二叉樹T的遞歸算法
if (T)
{
if (T->lchild)......余下全文>>
 

先序遍歷二叉樹的非遞歸算法

但是，遞歸本質上也是壓棧，只不過是程序壓棧，還不如這個效率高 如果先序遍歷的非遞歸算法還有其他版本，這個版本是最好記的 不過理解就是另