先写点最基本的知识
前序遍历：
1.访问根节点 2.前序遍历左子树 3.前序遍历右子树 中序遍历： 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树 后序遍历： 1.后序遍历左子树 2.后序遍历右子树 3.访问根节点递归实现是很容易地，可以参考《算法导论》上的写法
1 //遍历 2 //前序、中序、后序遍历 3 PREVORDER-TREE-WALK(x) 4 if x != NIL 5 then print key[x] 6 PREVORDER-TREE-WALK(left[x]) 7 PREVORDER-TREE-WALK(right[x]) 8 //中序 9 INORDER-TREE-WALK(x)10 if x != NIL11 then INORDER-TREE-WALK(left[x])12 print key[x]13 INORDER-TREE-WALK(right[x])14 //后序15 POST-TREE-WALK(x)16 if x != NIL 17 then POST-TREE-WALK(left[x])18 POST-TREE-WALK(right[x])19 print key[x]
但看到这篇博文()中的写法，感觉很舒服，也拿过来
1 def VisitTree_Recursive(root, order):2 if root:3 if order == 'NLR': print(root.data)4 VisitTree_Recursive(root.left, order)5 if order == 'LNR': print(root.data)6 VisitTree_Recursive(root.right, order)7 if order == 'LRN': print(root.data)
上面都是铺垫，递归写法很简单，面试中也不会被问到，会拿来做问题的是非递归写法。感觉()这篇博文对思路的分析非常清楚，也拿过来
非递归的前序、中序遍历
如果不用递归呢？实际上我们要做的就是自己维护一个栈（数据结构）来保存需要但尚未来得及处理的数据。
前序和中序都是非常简单的，当遇到一个非空的根结点时，打印其数据（如果是前序遍历），并将其压栈，然后递归地（这里用循环来模拟递归）处理其左子结点；当没有左子结点时，从栈中弹出之前遇到的某个根结点（它没有做子结点，或者左子结点已经处理完毕，需要再处理右子结点），打印数据（如果是中序遍历），然后继续处理右子结点。同样地，把两种遍历方式写在一起以便比较。
1 def VisitTree(root, order): 2 s = [] 3 while root or s: 4 if root: 5 if order == 'NLR': print(root.data) 6 s.append(root) 7 root = root.left 8 else: 9 root = s.pop()10 if order == 'LNR': print(root.data)11 root = root.right
博主的python代码果然是清晰易懂，但看到的另外一篇文章()给出了实现代码，感觉更爽，代码拿过来。
这是基于模板实现的Stack类
1 #include2 3 using namespace std; 4 5 //Author: 过往记忆 6 //Blog: www.wypblog.com 7 //Email: wyphao.2007@163.com 8 /// 9 //stack 10 template 11 class Stack{12 public:13 Stack(int size = 50);14 ~Stack();15 void push(T* data);16 T* pop();17 bool isEmpty();18 T* peek();19 private:20 int size;21 int top;22 bool isFull();23 T **data;24 };25 26 template 27 Stack ::Stack(int size){28 if(size <= 0){29 cout << "分配的内存太小了" << endl; 30 }31 32 data = new T*[size];33 top = -1;34 this->size = size; 35 }36 37 template 38 Stack ::~Stack(){39 delete []data;40 }41 42 template 43 void Stack ::push(T* data){44 ++top;45 if(isFull()){46 cout << "貌似栈满了耶" << endl;47 exit(1); 48 } 49 this->data[top] = data; 50 } 51 52 template 53 T* Stack ::pop(){ 54 if(isEmpty()){55 cout << "栈为空，不可以再出元素了!" << endl;56 exit(1); 57 }58 59 return data[top--]; 60 }61 62 template 63 T* Stack ::peek(){64 if(isEmpty()){65 cout << "栈为空" << endl;66 exit(1); 67 }68 69 return data[top];70 }71 72 template 73 bool Stack ::isFull(){74 if(top == size){75 return true; 76 } 77 78 return false; 79 } 80 81 template 82 bool Stack ::isEmpty(){83 if(top < 0){84 return true; 85 } 86 87 return false; 88 }
下面是使用此Stack实现的非递归版本遍历
1 template2 class BTree{ 3 public: 4 BTree *left; 5 BTree *right; 6 T data; 7 8 BTree() : left(NULL), right(NULL), data(NULL){}; 9 ~BTree(){}; 10 }; 11 12 ///13 template 14 void PreOrder(BTree *root){15 if(root != NULL){16 Stack > stack ;17 BTree *ptr = root;18 BTree *temp; 19 stack.push(ptr);20 while(!stack.isEmpty()) {21 temp = stack.pop(); 22 cout << temp->data << " ";23 if(temp->right != NULL){24 stack.push(temp->right);25 }26 27 if(temp->left != NULL){28 stack.push(temp->left);29 }30 }31 cout << endl; 32 } 33 } 34 35 ///36 template 37 void InOrder(BTree *root){38 if(root != NULL){39 Stack > stack ;40 BTree *ptr = root;41 while(!stack.isEmpty() || ptr != NULL){42 while(ptr != NULL){43 stack.push(ptr);44 ptr = ptr->left;45 }46 47 if(!stack.isEmpty()){48 ptr = stack.pop();49 cout << ptr->data << " ";50 ptr = ptr->right;51 }52 53 }54 cout << endl; 55 }56 }57 58 ///59 template 60 void PostOrder(BTree *root){61 if(root != NULL){62 Stack > stack;63 BTree *ptr = root;64 BTree *temp;65 bool flags;66 67 do{68 while(ptr != NULL){69 stack.push(ptr);70 ptr = ptr->left;71 }72 73 temp = NULL;74 flags = true;75 76 while(flags && !stack.isEmpty()){77 ptr = stack.peek();78 if(ptr->right == temp){79 cout << ptr->data << " ";80 stack.pop();81 temp = ptr;82 }else{83 ptr = ptr->right;84 flags = false;85 }86 }87 }while(!stack.isEmpty());88 cout << endl; 89 }90 }
再次引用()中分析。
后序遍历要稍微复杂一点点，在前序和中序遍历的程序中，当我们准备进入根结点的右子树时，根结点就被扔出栈外了。但在后序遍历时，我们仍需保留它，直到右子树处理完毕。实际上当左子树遍历完成、或者右子树遍历完成时，我们都会在栈里看到根结点，为了区分这两种状态，添加一个临时变量记录前一次访问的结点，如果前一个结点是根结点的右子树，就说明左右子树全都遍历完成了。这也是以上PostOrder采用的方式。
看到中介绍二叉树的层序遍历，搜集一下，以备参考
非递归的时候，层序遍历使用的是队列，而非栈。处理过程非常简明，遇到一个结点，打印信息，然后依次将左、右子结点加入队列等待后续处理。
1 from collections import deque 2 3 def VisitTree_LevelOrder(root): 4 if not root: return 5 q = deque([root]) 6 while q: 7 root = q.popleft() 8 print(root.data) 9 if root.left: q.append(root.left)10 if root.right: q.append(root.right)
这篇博文()给出了层序遍历的实现代码，如下
首先是自定义队列
1 #define MAX 1000 2 3 typedef struct seqqueue{ 4 bintree data[MAX]; 5 int front; 6 int rear; 7 }seqqueue; 8 9 10 void enter(seqqueue *q,bintree t){ 11 if(q->rear == MAX){ 12 printf("the queue is full!\n"); 13 }else{ 14 q->data[q->rear] = t; 15 q->rear++; 16 } 17 } 18 19 bintree del(seqqueue *q){ 20 if(q->front == q->rear){ 21 return NULL; 22 }else{ 23 q->front++; 24 return q->data[q->front-1]; 25 } 26 } 然后是层序遍历，和上面提到的层序遍历一个道理
1 void level_tree(bintree t){ 2 seqqueue q; 3 bintree temp; 4 q.front = q.rear = 0; 5 if(!t){ 6 printf("the tree is empty\n"); 7 return ; 8 } 9 enter(&q,t); 10 while(q.front != q.rear){ 11 t=del(&q); 12 printf("%c ",t->data); 13 if(t->lchild){ 14 enter(&q,t->lchild); 15 } 16 if(t->rchild){ 17 enter(&q,t->rchild); 18 } 19 } 20 } 还提到二叉树的其他常用算法，一并拿过来
统计结点个数
1 int count_tree(bintree t){ 2 if(t){ 3 return (count_tree(t->lchild)+count_tree(t->rchild)+1); 4 } 5 return 0; 6 } 比较两个树是否相同
1 int is_equal(bintree t1,bintree t2){ 2 if(!t1 && !t2){ //都为空就相等 3 return 1; 4 } 5 if(t1 && t2 && t1->data == t2->data){ //有一个为空或数据不同就不判断了 6 if(is_equal(t1->lchild,t2->lchild)) 7 if(is_equal(t1->rchild,t2->rchild)){ 8 return 1; 9 } 10 } 11 return 0; 12 } 求二叉树的深度
1 int hight_tree(bintree t){ 2 int h,left,right; 3 if(!t){ 4 return 0; 5 } 6 left = hight_tree(t->lchild); 7 right = hight_tree(t->rchild); 8 h = (left>right?left:right)+1; 9 return h; 10 }
参考博文：
1.
2.
3.