二叉查找树的非递归操作

昨天同学去參加阿里巴巴面试，被问到二叉树的一些基本问题，分享一下：

1.怎样非递归dfs求得树的深度

2.怎样非递归bfs求得树的深度

*3.怎样非递归地中前后序遍历二叉查找树。

二叉树写过不下十次了。可是基本每次都是用递归来写。一时间问道还不能一下写出来。

问题二还是比較好写，一的话可能须要细致想想，可是假如是面试的话。可能我一时也说不出来。

老实说，我自己写得代码总得看来是满长的。可是局部核心的是相对照较好理解的。

/*********************************************************** > OS : Linux 3.13.0-24-generic (Mint-17) > Author : yaolong > Mail : dengyaolong@yeah.net > Time : 2014年09月18日 星期四 12时24分57秒 **********************************************************/ #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stack> #include <queue> #include <cstdlib> using namespace std; template<typename Comparable> class BinarySearchTree { public: BinarySearchTree() { root = NULL; }; void insert ( Comparable x ) //非递归插入 { if ( root == NULL ) //由于不是传引用指针 { root = new Node ( x ); } else { insert ( x, root ); } } bool contains ( Comparable x ) //递归查询 { return contains ( x, root ); } void travel_in() //非递归中序遍历 { travel_in ( root ); } void travel_dg_in() //递归中序遍历 { travel_dg_in ( root ); } void travel_pre() //非递归前序遍历 { travel_pre ( root ); } void travel_dg_pre() //递归前序遍历 { travel_dg_pre ( root ); } void travel_suf() //非递归后序遍历，略微难 { travel_suf ( root ); } void travel_dg_suf() //递归后序遍历 { travel_dg_suf ( root ); } int get_depth_dg() //递归搜索树的深度 { return get_depth_dg ( root ); } int get_depth_dfs() //非递归，深度搜索树的深度 { return get_depth_dfs ( root ); } int get_depth_bfs() //非递归。宽度搜索树得深度 { return get_depth_bfs ( root ); } private: class Node { public: Comparable element; Node *left; Node *right; Node ( Comparable e , Node *l = NULL, Node *r = NULL ) : element ( e ), left ( l ), right ( r ) { } }; void insert ( Comparable x, Node *p ) { while ( 1 ) { if ( x > p->element ) //比当前节点元素大。插入到右边 { if ( p->right == NULL ) { p->right = new Node ( x ); return; } p = p->right; } else if ( x < p->element ) { if ( p->left == NULL ) { p->left = new Node ( x ); return; } p = p->left; } else { //nothing to do return; } } } bool contains ( Comparable x, Node *p ) { while ( p != NULL ) { if ( x > p->element ) { p = p->right; } else if ( x < p->element ) { p = p->left; } else { return 1; } } return 0; } void travel_pre ( Node *p ) //前序遍历 { stack<Node *> stk; while ( p != NULL || !stk.empty() ) { while ( p != NULL ) //先读。再往左。知道叶子 { cout << p->element << " "; stk.push ( p ); p = p->left; } if ( !stk.empty() ) //左路訪问完，退回訪问右路，即用右儿子进行继续递归，进行前序遍历 { p = stk.top(); stk.pop(); p = p->right; } } } void travel_dg_pre ( Node *p ) { if ( p == NULL ) { return; } cout << p->element << " "; travel_dg_pre ( p->left ); travel_dg_pre ( p->right ); } void travel_in ( Node *p ) { stack<Node *> stk; while ( p != NULL || !stk.empty() ) { while ( p != NULL ) { stk.push ( p ); p = p->left; } if ( !stk.empty() ) { p = stk.top(); stk.pop(); cout << p->element << " "; p = p->right; } } } void travel_dg_in ( Node *p ) { if ( p == NULL ) { return; } travel_dg_in ( p->left ); cout << p->element << " "; travel_dg_in ( p->right ); } void travel_suf ( Node *p ) { stack<Node *> stk; Node *prev = NULL; while ( p != NULL || !stk.empty() ) { while ( p != NULL ) { stk.push ( p ); p = p->left; } p = stk.top(); if ( p->right == NULL || p->right == prev ) { cout << p->element << " "; prev = p; stk.pop(); p = NULL; } else { p = p->right; } } } void travel_dg_suf ( Node *p ) { if ( p == NULL ) { return; } travel_dg_suf ( p->left ); travel_dg_suf ( p->right ); cout << p->element << " "; } int get_depth_dfs ( Node *p ) { int depth = 0, d = 0; stack<Node *> stk; stack<int> stk_depth; while ( p != NULL || !stk.empty() ) { while ( p != NULL ) { stk.push ( p ); stk_depth.push ( d++ ); p = p->left; } if ( !stk.empty() ) { d = stk_depth.top(); depth = max ( d, depth ); p = stk.top(); stk.pop(); stk_depth.pop(); p = p->right; d++; } } return depth; } int get_depth_bfs ( Node *p ) { queue<Node *> q; queue<int> q_d; int d = 0; int depth = 0; q.push ( p ); q_d.push ( d ); while ( !q.empty() ) { p = q.front(); d = q_d.front() ; ++d; q.pop(); q_d.pop(); if ( p->left != NULL ) { q_d.push ( d ) ; q.push ( p->left ); depth = max ( depth, d ); } if ( p->right != NULL ) { q_d.push ( d ) ; q.push ( p->right ); depth = max ( depth, d ); } } return depth; } int get_depth_dg ( Node *p ) { int depth = 0; if ( p->left != NULL ) { depth = max ( depth, get_depth_dg ( p->left ) + 1 ); } if ( p->right != NULL ) { depth = max ( depth, get_depth_dg ( p->right ) + 1 ); } return depth; } Node *root; }; int main() { BinarySearchTree<int> t; for ( int i = 0; i < 100; i++ ) { int tmp = random() % 100000; //cout<<tmp; t.insert ( tmp ); } cout << "Insert OK" << endl; cout << t.contains ( 4 ) << endl; cout << t.contains ( 2 ) << endl; cout << "非递归递归前序遍历:\n"; t.travel_pre(); cout << "\n递归前序遍历\n"; t.travel_dg_pre(); cout << "\n递归中序遍历\n"; t.travel_dg_in(); cout << "\n非递归递归中序遍历:\n"; t.travel_in(); cout << "\n递归后序遍历\n"; t.travel_dg_suf(); cout << "\n非递归递归后序遍历:\n"; t.travel_suf(); cout << "\n递归求的树的高度\n"; cout << t.get_depth_dg(); cout << "\n非递归dfs求的树的高度\n"; cout << t.get_depth_dfs(); cout << "\n非递归bfs求的树的高度\n"; cout << t.get_depth_bfs(); }