面试算法之二叉树操作集锦

开学了，找工作也正式拉开了序幕，每天光自己看书，也很没劲，和大家一起分享分享，交流一下笔试面试过程中的各种算法题目，如有问题，欢迎指正，希望大家一起进步。。。

下面是对数据结构二叉树的一些基本操作，可能在面试中都会涉及到。我们都知道二叉树的定义本身就是一种递归定义，所以对树的大部分操作都可以通过递归的方式进行，但递归不是万能的，因为递归的本身是一件很浪费内存资源的操作，所以在选择算法的时候要权衡各种因素，选取最合理的算法。下图Fig 1 是下面代码中举例会用到的图：

Fig 1

在本文中，所讨论的二叉树采取以下的定义方式：

Fig 2 B为A的一个子结构
那么对于这个题目的解题思路是：在A中查找与B根节点相同的节点X，找到后将该节点X的左右子树与B的左右子树依次比较，如果B的所有节点都在X的左右子树中，那么就认为B是A的子结构，如果B的所有节点不都在X的左右子树中，那么在A中继续查找另外一个X节点，直到结束。下面是代码：
/** * judge the serial is post-order traversal of binary search tree */template <typename Type>bool IsBSTPostOrder(const Type *post, int len){if(post == NULL || len <= 0)return false;int index;//查找小于根节点的左子树节点for (index = 0; index < len - 1; ++index){if(post[index] > post[len - 1])break;}//判断剩下的节点是否都为右子树的节点，即是否都大于根节点的值for (int i = index; i < len - 1; ++i){if(post[i] < post[len - 1])return false;}bool result = true;if(index > 0)result = IsBSTPostOrder(post, index);if(result && index < len - 1)result = IsBSTPostOrder(post + index, len - index - 1);return result;}

就先写这么多吧，后面还会继续添加，累死了。。。

Sept 2nd - 3rd, 2013 @lab