二叉树遍历、插入、删除等常见操作

落日映苍穹つ 2022-08-05 19:27 207阅读 0赞

本文总结了二叉树常见的题目。

如下是头文件的部分声明：

//tree.h
    #ifndef TEST_TREE_H
    #define  TEST_TREE_H
    
    typedef int ElementType;
    struct TreeNode;
    typedef struct TreeNode *Position;
    typedef struct TreeNode *SearchTree;
    
    struct TreeNode {
    	ElementType element;
    	SearchTree left;
    	SearchTree right;
    };
    ...
    #endif

从上述的声明可以看出**Positon、SearchTree均是指向树型结构的指针**，在下面的程序中注意。

**如下的程序中，有的是借助二叉搜索树的性质，因此是二叉树特有的；而大部分都是二叉树均有的算法。在每段代码开头都注明了是仅用于二叉搜素树或者是通用的。**

# 一、二叉搜索树一些实现 #

二叉搜索树特点：结点左子树的值均小于右子树的值。

//二叉搜索树的创建
    SearchTree CreateSearchTree(SearchTree tree) {
    	int tree_element;
    	while (cin >> tree_element) {
    		if (tree_element == '*')
    			break;
    		else
    			tree = InsertToTree(tree_element, tree);
    	}
    	return tree;
    }
    
    //二叉搜索树的查找
    Position FindFromTree(ElementType x, SearchTree tree) {
        if (tree == NULL)
            return NULL;
        if (tree->element < x)
            FindFromTree(x, tree->right);
        else if (x < tree->element)
            FindFromTree(x, tree->left);
        else
            return tree;
    }
    
    //寻找二叉搜索树的最大节点:递归和非递归
    Position FindMax(SearchTree tree) {
        if (tree != NULL)
            while (tree->right != NULL)
                tree = tree->right;
        return tree;
    }
    
    Position FindMax2 (SearchTree tree) {
        if (tree == NULL)
            return NULL;
        else if (tree->right == NULL)
            return tree;
        else
            return FindMax2(tree->right);
    }
    
    //寻找二叉搜索树的最小节点：递归和非递归
    Position FindMin(SearchTree tree) {
        if (tree != NULL)
            while (tree->left)
                tree = tree->left;
        return tree;
    }
    
    Position FindMin2(SearchTree tree) {
        if (tree == NULL)
            return NULL;
        else if (tree->left == NULL)
            return tree;
        else
            return FindMin(tree->left);
    }
    
    //二叉搜索树的插入
    SearchTree InsertToTree(ElementType x, SearchTree tree) {
        if (tree == NULL) {
            tree = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            if (tree == NULL) {
                cout << "malloc failed" << endl;
            }
            else {
                tree->element = x;
                tree->left = NULL;
                tree->right = NULL;
            }
        }
        else if (x < tree->element)
            tree->left = InsertToTree(x, tree->left);
        else if (x > tree->element)
            tree->right = InsertToTree(x, tree->right);
        return tree;
    }
    
    //二叉搜索树的删除
    SearchTree DeleteFromTree(ElementType x, SearchTree tree) {
        Position temp;
        if (tree == NULL) {
            cout << "The tree is empty, no element." << endl;
        }
        else if (x < tree->element) {  //寻找要删除的位置
            DeleteFromTree(x, tree->left);
        }
        else if (x > tree->element) {  //寻找要删除的位置
            DeleteFromTree(x, tree->right);
        }
        else if(tree->left && tree->right) {  //找到要删除的位置，该节点有两个孩子
            temp = FindMin(tree->right);
            tree->element = temp->element;
            tree->right = DeleteFromTree(tree->element, tree->right);
        }
        else { //仅有一个子树，或者为叶节点
            temp = tree;
            if (tree->left == NULL)
                tree = tree->right;
            else if (tree->right == NULL)
                tree = tree->left;
            free(temp);
        }
        return tree;
    }

# 二、二叉树的遍历 #

二叉树的遍历基本操作就是访问结点，无论按照哪一种次序进行遍历，对含有n个结点的二叉树，其**时间复杂度均为O(n)**。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则**最坏空间复杂度为O(n)**。

这里的遍历仅仅是控制台打印树结点的值，由下面函数完成：

void VisitTreeElement(SearchTree tree) {
    	cout << tree->element << " ";
    }

## 1. 先序遍历 ##

先序遍历是在元素入栈前，先访问该元素；然后将此节点入栈，再遍历其左子树；遍历完左子树后，从栈中弹出该元素，然后根据该元素的右子树指针去遍历该节点的右子树结构。给出了递归算法和几种非递归算法（大同小异，使用辅助栈）。

//先序遍历的递归方法
    void PreOrderTraversalRecursion(SearchTree tree) {
    	if (tree == NULL) {
    		return;
    	}
    	VisitTreeElement(tree);
    	PreOrderTraversalRecursion(tree->left);
    	PreOrderTraversalRecursion(tree->right);
    }
    
    //先序遍历的非递归方法（一）
    void PreOrderTraversal(SearchTree tree) {
        if (tree == NULL)
            return;
        stack<SearchTree> stk;
        Position cur = tree;
    
        while (cur != NULL || !stk.empty()) {
            while (cur != NULL) {
                VisitTreeElement(cur);
                stk.push(cur);
                cur = cur->left;
            }
            //if (!stk.empty()) {
            cur = stk.top();
            stk.pop();
            cur = cur->right;
            //}
        }
    }
    
    //先序遍历的非递归方法（二）
    void PreOrderTraversal2(SearchTree tree) {
        if (tree == NULL)
            return;
        stack<SearchTree> stk;
        stk.push(tree);
    
        while(!stk.empty()) {
            Position top_node = stk.top();
            VisitTreeElement(top_node);
            stk.pop();
            if (top_node->right)
                stk.push(top_node->right);
            if (top_node->left)
                stk.push(top_node->left);
        }
    }
    
    //先序遍历的非递归方法（三）
    void PreOrderTraversal3(SearchTree tree) {
        if (tree == NULL)
            return;
        stack<SearchTree> stk;
    
        while (tree) {
            stk.push(tree);
            VisitTreeElement(tree);
            tree = tree->left;
        }
    
        while (!stk.empty()) {
            Position top_node_right = stk.top()->right;
            stk.pop();
            while (top_node_right) {
                VisitTreeElement(top_node_right);
                stk.push(top_node_right);
                top_node_right = top_node_right->left;
            }
        }
    }

## 2. 中序遍历 ##

中序遍历遇到一个元素，先将其入栈，并遍历其左子树。遍历完左子树，从栈中弹出元素并访问，然后按照该元素指示的其右孩子去遍历右子树。  
其实前序和中序遍历仅仅是访问元素的时机不同，**前者是入栈时就访问，后者是在出栈时访问**。下面非递归中序遍历的两种方式分别与前序非递归的第（一）、第（三）种方式类似。

//中序遍历的递归方法
    void InOrderTraversalRecursion(SearchTree tree) {
    	if (tree == NULL)
    		return;
    	InOrderTraversalRecursion(tree->left);
    	VisitTreeElement(tree);
    	InOrderTraversalRecursion(tree->right);
    }
    
    //中序遍历的非递归方法（一），类似前序非递归遍历（一）
    void InOrderTraversal(SearchTree tree) {
        if (tree == NULL)
            return;
        stack<SearchTree> stk;
        Position cur = tree;
        
        while (cur != NULL || !stk.empty()) {
            while (cur != NULL) {
                stk.push(cur);
                cur = cur->left;
            }
            //if (!stk.empty()) {
            cur = stk.top();
            VisitTreeElement(cur);
            stk.pop();
            cur = cur->right;
            //}
        }
    }
    
    //中序遍历的非递归方法（二），类似前序非递归遍历（三）
    void InOrderTraversal2(SearchTree tree) {
        if (tree == NULL)
            return;
        stack<SearchTree> stk;
    
        while (tree) {
            stk.push(tree);
            tree = tree->left;
        }
    
        while (!stk.empty()) {
            Position top_node_right = stk.top()->right;
            VisitTreeElement(stk.top());
            stk.pop();
            while (top_node_right) {
                stk.push(top_node_right);
                top_node_right = top_node_right->left;
            }
        }
    }

## 3. 后序遍历 ##

后序遍历遇到一个元素，将其入栈，遍历其左子树。**遍历结束后，不能立即访问栈顶节点，而要遍历右子树**。遍历完右子树后才能访问该元素。另外，**当从栈中弹出一个元素时，还要判断该栈顶元素是从左边返回的**（这样要继续访问其右子树），**还是从右边返回的**（这时该元素左右子树均访问过了）。

//后序遍历递归算法
    void PostOrderTraversalRecursion(SearchTree tree) {
        if (tree == NULL)
            return;
        PostOrderTraversalRecursion(tree->left);
        PostOrderTraversalRecursion(tree->right);
        VisitTreeElement(tree);
    }
    
    //后序非递归方法（一）
    void PostOrderTraversal(SearchTree tree) {
    	stack<SearchTree> stk;
    	Position cur = tree;
    	Position visited = NULL; //指向前一个访问的节点
    	while (cur != NULL || !stk.empty()) {
    		while (cur != NULL) { //一直遍历左子树
    			stk.push(cur);
    			cur = cur->left;
    		}
    		cur = stk.top();
    		//如果当前节点的右树为空或者右树已经访问过了，
    		//直接访问该节点并弹出该节点
    		if (cur->right == NULL || cur->right == visited) {
    			VisitTreeElement(cur);
    			visited = cur;
    			stk.pop();
    			cur = NULL;
    		}
    		else //否则遍历右子树
    			cur = cur->right;
    	}
    }
    
    //后序非递归方法（二）
    void PostOrderTraversal2(SearchTree tree) {
    	stack<SearchTree> s1, s2;
    	Position cur;
    	s1.push(tree);
    	while (!s1.empty()) {
    		cur = s1.top();
    		s1.pop();
    		s2.push(cur);
    		if (cur->left)
    			s1.push(cur->left);
    		if (cur->right)
    			s1.push(cur->right);
    	}
    	while (!s2.empty()) {
    		VisitTreeElement(s2.top());
    		s2.pop();
    	}
    }

## 4. 层次遍历 ##

## 1、所有元素依次输出，不换行 ##

和以上三种遍历方式不同：**层次遍历使用的辅助结构是队列，**先序、中序、后序遍历都使用辅助结构**栈**。

//层次遍历，入队前访问或出队前访问均可
    void LevelTraversal(SearchTree tree) {
    	queue<SearchTree> q;
    	VisitTreeElement(tree);
    	q.push(tree);
    	while (!q.empty()) {
    		Position cur = q.front();
    		q.pop();
    		if (cur->left) {
    			VisitTreeElement(cur->left);
    			q.push(cur->left);
    		}
    		if (cur->right) {
    			VisitTreeElement(cur->right);
    			q.push(cur->right);
    		}
    	}
    }

## 2、每行输出树的一层元素 ##

参考： [http://www.cnblogs.com/miloyip/archive/2010/05/12/binary\_tree\_traversal.html][http_www.cnblogs.com_miloyip_archive_2010_05_12_binary_tree_traversal.html]

//每行输出一层节点的各个元素
    //方法一：
    //利用vector充当队列，两个指针current和last分别指向vector
    //中某层树元素的第一个和最后一个，当current < last时，依次遍历
    //本层每个元素
    typedef struct Tree{
    	Tree* left;
    	Tree* right;
    	int value; 
    } Tree, Node;
    void PrintNodeByLevel(Tree* tree) {
    	if (tree == NULL)
    		return;
    	vector<Node*> vec;
    	int current = 0, last = 1;
    	vec.push_back(tree);
    	while (current < vec.size()) {
    		last = vec.size();
    		while (current < last) {
    			cout << vec[current] -> value << " ";
    			if (vec[current]->left)
    				vec.push_back(vec[current]->left);
    			if (vec[current]->right)
    				vec.push_back(vec[current]->right);
    			++current;
    		}
    		cout << endl;
    	}
    }
    
    //方法二：
    //http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html
    //每层遍历结束，在队列中插入一个空指针，标志本层结束需要输出换行
    void PrintNodeByLevel2(Tree* tree) {
    	if (tree == NULL)
    		return;
    
    	queue<Node *> q;
    	q.push(tree);
    	while (!q.empty()) {
    		Node * node = q.front();
    		q.pop();
    		if (node) {
    			cout << node->value << " ";
    			if (node->left)
    				q.push(node->left);
    			if (node->right)
    				q.push(node->right);
    		}
    		else if (!q.empty()) {  //当发现是空指针时要判断队列还有没有元素，否则死循环
    			q.push(NULL);
    			cout << endl;
    		}
    	}
    	return;
    }

注意一点，当发现空指针(结束信号)时，要检查队列内是否还有节点，如果没有的话还插入新的结束信号，则会做成死循环。

# 三、二叉树的清空 #

清空操作是删除树的所有结点、释放内存。**后序遍历方式**，递归删除左右子树，然后删除根节点。

//二叉树的清空操作
    SearchTree MakeEmptyTree(SearchTree tree) {
    	if (tree != NULL) {
    		MakeEmptyTree(tree->left);
    		MakeEmptyTree(tree->right);
    		free(tree);
    	}
    	return NULL;
    }

# 四、二叉树的复制和镜像 #

//二叉树的拷贝
    SearchTree CopyTree(SearchTree tree) {
    	if (NULL == tree)
    		return NULL;
    	SearchTree pleft = CopyTree(tree->left);
    	SearchTree pright = CopyTree(tree->right);
    	tree->left = pleft;
    	tree->right = pright;
    	return tree;
    }
    
    //二叉树的镜像 offerT19
    void MirrorTree(SearchTree tree) {
        if (NULL == tree)
            return;
        if (NULL == tree->left && NULL == tree->right)
            return;
    
        SearchTree temp = tree->left;
        tree->left = tree->right;
        tree->right = temp;
    
        if (tree->left)
            MirrorTree(tree->left);
        if (tree->right)
            MirrorTree(tree->right);
    }

如下图是二叉树镜像求解过程，先交换根的左右子树，然后递归交换子树。

![SouthEast][]

# 五、二叉树和为某一值的路径 #

题目：输入二叉树和一个整数，求路径上结点的和等于输入的整数的路径。二叉树的路径是指，从根节点往下一直到叶节点所经过的节点形成的一条路径。

思路：用先序遍历，访问到某结点将其加入到路径上，并累加该结点的值。如果访问的不是叶结点，则继续访问其子树；如果访问到叶结点而且路径上的值等于输入的整数，那么这条路径就是符合要求的，将其打印出来。当递归函数退出时，自动回到了它的父节点，因此我们在函数退出时要在路径上删除当前结点并减去当前结点的值。

如下代码并没有使用stack完成栈的功能，因为打印路径要遍历栈结构，而stack是不可以遍历的，因此**使用vector来模拟栈**。

//offerT25
    //打印二叉树中和为某一值的路径
    void FindPathCore(SearchTree tree, int sum, vector<int>& path, int sum_current);
    
    void FindPath(SearchTree tree, int sum) {
    	if (NULL == tree)
    		return;
    	
    	vector<int> path;     //模拟栈，保存路径
    	int sum_current = 0;
    	FindPathCore(tree, sum, path, sum_current);
    }
    
    void FindPathCore(SearchTree tree, int sum, vector<int>& path, int sum_current) {
    	sum_current += tree->element;
    	path.push_back(tree->element);
    
    	bool isleef = (tree->left == NULL && tree->right == NULL);
    	if (isleef && sum_current == sum) {
    		cout << "a path: ";
    		vector<int>::iterator iter = path.begin();
    		while (iter != path.end())
    			cout << *iter++ << " ";
    		cout << endl;
    	}
    
    	if (tree->left)
    		FindPathCore(tree->left, sum, path, sum_current);
    	if (tree->right)
    		FindPathCore(tree->right, sum, path, sum_current);
    
    	path.pop_back();
    }

# 六、将二叉树转换为双向链表 #

题目：输入二叉搜索树，将其转换为一个排序的双向链表。要求不创建任何新结点，仅调整树中结点指针的指向。

思路：按照二叉搜索树的中序遍历，得到的就是排序的序列；这里**要求链表排序，因此也是中序遍历的思路**。如果没有要求链表排序，当然不必非要按中序遍历。

如下图所示，按照中序遍历左子树，当遍历到根结点（值为10）时，它的左子树已经转换为了排序的双向链表，并且处在链表最后一个结点的是当前最大的结点。将值为8的结点和根结点连接起来，此时链表最后一个结点就是10了。然后，遍历右子树，并将根结点和右子树最小的结点连接起来。如何转换左右子树，按照上述思路递归即可。

![SouthEast 1][]

//offerT27
    //二叉搜素树和双向链表(中序遍历)
    void CovertTreetoListCore(SearchTree tree, SearchTree* last_listnode);
    SearchTree CovertTreetoList(SearchTree tree) {
    	SearchTree last_listnode = NULL;
    	CovertTreetoListCore(tree, &last_listnode);
    	
    	//last_listnode指向双向链表尾部，这里将其指向头部
    	SearchTree head_list = last_listnode;
    	while (head_list && head_list->left != NULL)
    		head_list = head_list->left;
    
    	return head_list;
    }
    
    //函数第二个参数是指针的指针
    void CovertTreetoListCore(SearchTree tree, SearchTree* last_listnode) {
    	if (NULL == tree)
    		return;
    
    	SearchTree current = tree;
    
    	if (current->left)
    		CovertTreetoListCore(current->left, last_listnode);
    
    	current->left = *last_listnode;
    	if (*last_listnode)
    		(*last_listnode)->right = current;
    	
    	*last_listnode = current;
    
    	if (current->right)
    		CovertTreetoListCore(current->right, last_listnode);
    }

# 七、求二叉树的深度 #

下面的几个例子会用到求深度的算法。

//求二叉树的深度
    int GetNodeDeepth(SearchTree tree) {
    	if (tree == NULL)
    		return 0;
    	int deepth_left = GetNodeDeepth(tree->left);
    	int deepth_right = GetNodeDeepth(tree->right);
    	return deepth_right > deepth_left ? (deepth_right + 1): (deepth_left + 1);
    }

# 八、判断二叉树是不是平衡二叉树 #

offerT39

思路一：遍历树的每个结点，得到其左右子树的深度，如果某个结点左右子树深度之差超过1，该数就不是平衡树；否则是。该思路要多次重复遍历一个结点，效率很低。

思路二：如果某个树不是平衡树，那么它在根结点处就肯定不是平衡树。所以，后序遍历一次二叉树，求出二叉树左右的最大和最小深度，如果根的左右子树深度相差超过1，那么 树不是平衡二叉树。

如下，使用Depth结构存储节点左右子树的最大和最小深度。如果根的左右子树中，最大和最小深度相差不超过1，该树是平衡二叉树。

//Depth结构用于存储根结点的最大和最小深度
    struct Depth {
    	int min_depth;
    	int max_depth;
    };
    //函数返回根结点的最大和最小深度
    Depth GetDepth(SearchTree tree) {
    	if (NULL == tree) {
    		Depth empty = {0, 0};
    		return empty;
    	}
    
    	Depth lhs = GetDepth(tree->left);
    	Depth rhs = GetDepth(tree->right);
    	Depth depth;
    	depth.max_depth = 1 + max(lhs.max_depth, rhs.max_depth);
    	depth.min_depth = 1 + min(lhs.min_depth, rhs.min_depth);
    	return depth;
    }
    bool IsBalancedTree2(SearchTree tree) {
    	Depth depth = GetDepth(tree);
    	//如果根结点的最大深度和最小深度之差不超过1为平衡二叉树
    	if (depth.max_depth - depth.min_depth > 1)
    		return false;
    	else
    		return true;
    }

思路三：用后序遍历的方式遍历二叉树，在遍历到一个节点前，已经遍历了它的左右子树。那么首先判断结点左右子树是否平衡，若左右子树均平衡了，然后该该结点处也平衡了，那么，该树才是平衡的；如果左右子树有一个不平衡，就直接返回false，相对于思路二需要遍历的节点数目会少，虽然这两种思路复杂度都是O（n）。

//offerT39
    //判断一棵树是不是平衡树（后序遍历）
    bool IsBalancedTreeCore(SearchTree tree, int *depth);
    bool IsBalancedTree(SearchTree tree) {
    	int depth = 0;
    	return IsBalancedTreeCore(tree, &depth);
    }
    
    bool IsBalancedTreeCore(SearchTree tree, int *depth) {
    	if (NULL == tree) {
    		*depth = 0;
    		return true;
    	}
    
    	int depth_left, depth_right;
    	if (IsBalancedTreeCore(tree->left, &depth_left) && 
    		IsBalancedTreeCore(tree->right, &depth_right)) {
    		int diff = depth_left - depth_right;
    		if (diff >= -1 && diff <= 1) {
    			*depth = (depth_left > depth_right ? depth_left : depth_right) + 1;
    			return true;
    		}
    	}
    
    	return false;
    }

# 九、求二叉树中节点的最大距离 #

即二叉树中相距最远的两个节点之间的距离。  
递归解法：  
（1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0  
（2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，同时记录左子树和右子树节点中到根节点的最大距离。

方法一：

//求二叉树中结点的最大距离
    
    struct Result {
    	int max_distance;
    	int max_depth;
    };
    
    Result GetMaxDistanceCore(SearchTree tree);
    int GetMaxDistance(SearchTree tree) {
    	return GetMaxDistanceCore(tree).max_distance;
    }
    
    Result GetMaxDistanceCore(SearchTree tree) {
    	if (NULL == tree) {
    		//最大深度初始化为-1是因为调用这对其加1，然后变为0
    		Result empty = {0, -1};
    		return empty;
    	}
    
    	Result lhs = GetMaxDistanceCore(tree->left);
    	Result rhs = GetMaxDistanceCore(tree->right);
    	Result result;
    	result.max_depth = max(lhs.max_depth + 1, rhs.max_depth + 1);
    	result.max_distance = max(max(lhs.max_distance, rhs.max_distance), 
    		                      lhs.max_depth + rhs.max_depth + 2);
    
    	return result;
    }

方法二：

该代码更简单，要调用求二叉树深度的函数GetNodeDepth：

int GetMaxDistance2(TreeNode * pRoot){
    	if (pRoot == NULL)
    		return 0;
    
    	return max(GetNodeDeepth(pRoot->left) + GetNodeDeepth(pRoot->right), 
    		GetMaxDistance2(pRoot->left), GetMaxDistance2(pRoot->right));
    }

# 十、由先序遍历和后序遍历，构造二叉树 #

题目：输入两个序列，分别表示先序遍历和后序遍历的结果，构造二叉树。下一题也是这个思路。

//由先序和中序遍历构造二叉树
    Position ConstructBiTreeCore(int *startPreOrder, int *endPreorder, 
    	                         int *startInorder, int *endInorder) {
    	int root_value = startPreOrder[0];
    	Position root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    	if (root == NULL)
    		return NULL;
    	root->element = root_value;
    	root->right = root->left = NULL;
    
    	if (startPreOrder == endPreorder) {
    		if (startInorder == endInorder && *startInorder == *startPreOrder)
    			return root;
    		else { //当输入序列不符合要求时，返回NUll之前释放root，以免内存泄露
    			free(root);
    			return NULL;
    		}
    	}
    
    	int *rootInorder = startInorder;
    	while (rootInorder <= endInorder && *rootInorder != root_value)
    		++rootInorder;
    
    	int left_len = rootInorder - startInorder;
    	int *leftPreOrderEnd = startPreOrder + left_len;
    	if (left_len > 0) {
    		root->left = ConstructBiTreeCore(startPreOrder + 1, leftPreOrderEnd, 
    			startInorder, rootInorder - 1);
    	}
    	if (left_len < endPreorder - startPreOrder) {
    		root->right = ConstructBiTreeCore(leftPreOrderEnd + 1, endPreorder, 
    			rootInorder + 1, endInorder);
    	}
    	return root;
    }
    
    Position ConstructBiTree(int *preorder, int *inorder, int len) {
        if (preorder == NULL || inorder == NULL || len <= 0)
            return NULL;
        return ConstructBiTreeCore(preorder, preorder + len - 1,
            inorder, inorder + len - 1);
    }

# 十一、根据先序遍历和中序遍历，求后序遍历序列 #

和上一题的思路一模一样，只是这里仅求后序序列，不用构建二叉树。

先序遍历的第一个结点在后序遍历中是最后一个结点（此结点时根结点），因此递归遍历根的左子树和右子树：在左右子树遍历中，左子树会先于根输出，右子树在左子树后输出，最后输出根（这恰好就是后序遍历的最后一个元素）。于是后序遍历序列输出完成。

//根据先序遍历和中序遍历求后序遍历(和上题构造二叉树原理一样)
    void PrintPostOrderCore(int *startPreorder, int *endPreorder,
        int *startInorder, int *endInorder) {
        int root_value = startPreorder[0];
    
        //当先序遍历和后序遍历仅有一个元素且该元素相等时，输出
        //否则是非法输入
        if (startPreorder == endPreorder) {
            if (startInorder == endInorder && *startPreorder == *startInorder) {
                cout << root_value << " ";
            }
            else {
                throw exception("invalid input");
            }
        }
    
        //在中序遍历中寻找根的位置
        int *rootInorder = startInorder;
        while (rootInorder <= endInorder && *rootInorder != root_value)
            ++rootInorder;
    
        //递归遍历左右子树
        int left_length = rootInorder - startInorder;
        int *leftPreorderEnd = startPreorder + left_length;
        if (left_length > 0)
            PrintPostOrderCore(startPreorder + 1, leftPreorderEnd,
                  startInorder, rootInorder - 1);
        if (left_length < endPreorder - startPreorder)
            PrintPostOrderCore(leftPreorderEnd + 1, endPreorder,
                  rootInorder + 1, endInorder);
        
        //左右子树输出完成后，在输出根结点值
        cout << root_value << " ";
    }
    
    void PrintPostOrder(int *preorder, int *inorder, int length) {
    	if (preorder == NULL || inorder == NULL || length <= 0)
    		return;
    	PrintPostOrderCore(preorder, preorder + length - 1,
    		inorder, inorder + length -1);
    }

# 十二、判断是否为二叉搜索树的后序遍历序列 #

题目：判断输入的序列是不是一个二叉搜索树的后序遍历序列。

思路：后序遍历时，最后遍历的是根结点。二叉搜索树根节点值大于所以左子树的值，且小于所以右子树的值；在子树中递归利用此性质，如果不满足，那么就不是二叉搜索树的后序遍历序列。

//offerT24
    //判断某个整数数组是不是一个二叉搜索树的后序遍历序列
    bool IsPostOrderBST(int array[], int length) {
    	if (length < 1 || array == NULL)
    		return false;
    
    	int root = array[length - 1];
    
    	int length_left = 0;
    	for ( ; length_left < length - 1; ++length_left) {
    		if (array[length_left] > root)
    			break;
    	}
    
    	int pos_right = length_left;
    	for ( ; pos_right < length - 1; ++pos_right) {
    		if (array[pos_right] < root)
    			return false;
    	}
    
    	//判断左子树是不是BST的后序遍历序列
    	bool result_left = true;
    	if (length_left > 0)
    		result_left = IsPostOrderBST(array, length_left);
    
    	//判断右子树是不是BST的后序遍历序列
    	bool result_right = true;
    	if (length_left < length - 1)
    		result_right = IsPostOrderBST(array + length_left, length - length_left - 1);
    
    	return (result_left && result_right);
    }

# 十三、判断两棵树是否相等 #

//二叉树A和B，判断A和B是否相等
    bool EqualBinaryTree(SearchTree treea, SearchTree treeb) {
    	if (treea == NULL && treeb == NULL)
    		return true;
    	if ((!treea && treeb) || (treea && !treeb))
    		return false;
    
    	if (treea->element == treeb->element) {
    		return EqualBinaryTree(treea->left, treeb->left) &&
    			EqualBinaryTree(treea->right, treeb->right);
    	}
    	return false;
    } 
    
    //二叉树A和B，判断可以旋转的A和B是否相等,旋转是指左右子树可交换
    bool EqualBinaryTree2(SearchTree treea, SearchTree treeb) {
    	if (treea == NULL && treeb == NULL)
    		return true;
    	if ((!treea && treeb) || (treea && !treeb))
    		return false;
    
    	if (treea->element == treeb->element) {
    		return (EqualBinaryTree2(treea->left, treeb->left) && 
    			EqualBinaryTree2(treea->left, treeb->left)) || 
    			(EqualBinaryTree2(treea->left, treeb->right) && 
    			EqualBinaryTree2(treea->right, treeb->left));
    	}
    	return false;
    }

# 十四、判断一棵树是不是另一棵树的子树 #

//offerT18
    //二叉树A和B，判断B是不是A的子结构
    bool SubTreeCore(SearchTree treea, SearchTree treeb) {
    	if (treeb == NULL)
    		return true;
    	if (treea == NULL)
    		return false;
    	if (treea->element != treeb->element)
    		return false;
    	return SubTreeCore(treea->left, treeb->left) &&
    		SubTreeCore(treeb->right, treeb->right);
    }
    
    bool IsSubTree(SearchTree treea, SearchTree treeb) {
    	bool result = false;
    	if (treea && treeb) {
    		if (treea->element == treeb->element)
    			result = SubTreeCore(treea, treeb);
    		if (!result)
    			result = IsSubTree(treea->left, treeb);
    		if (!result)
    			result = IsSubTree(treea->right, treeb);
    	}
    	return result;
    }

# 十五、判断二叉树是不是完全二叉树 #

思路：如果一棵树是完全二叉树，那么，如果某个结点只有右孩子，树不是完全的；如果某个结点只有左孩子，只有当层次遍历时，该结点之后所有结点都是叶子结点时，树才是完全的；如果某个结点是叶子结点，那么按照层次遍历时，其后的结点必须都是叶子结点，那么树才是完全的。

//判断二叉树是不是完全二叉树
    bool IsCompletedTree(SearchTree tree) {
    	if (NULL == tree)
    		return false;
    	bool result = true;
    	bool must_leaf = false;
    	
    	queue<SearchTree> nodes;
    	nodes.push(tree);
    	while (!nodes.empty()) {
    		SearchTree node = nodes.front();
    		nodes.pop();
    		
    		//如果某节点只有左子树，那么按照层次遍历时
    		//其后结点必须全为叶子结点，否则该树不是完全二叉树
    		if (must_leaf) {
    			if (node->left || node->right) {
    				result = false;
    				break;
    			}
    		}
    		else {
    			if (node->left && node->right) {
    				nodes.push(node->left);
    				nodes.push(node->right);
    			}
    			else if (node->left && ! node->right) {
    				must_leaf = true;
    				nodes.push(tree->left);
    			}
    			else if (!node->left && node->right) {
    				result = false;
    				break;
    			}
    			else
    				must_leaf = true;
    		}
    	}
    	return true;
    }

# 十六、求树中两个节点的最低公共祖父 #

offerT50

## 1、如果是在二叉搜索树中 ##

如果是二叉搜索树，那么左子树元素均小于根，右子树均大于根。

那么从根开始和输入的两个结点比较：

如果当前结点比输入的两个数都大，那么最低公共祖先一定在当前结点的左子树中，于是下一步遍历当前结点的左子树结点。

如果当前结点的值比两个输入结点都小，那么最低公共祖先在右子树，下一步遍历右子树结点。

这样，从树中找到第一个在两个输入结点值之间的结点，就是最低公共祖父节点。

## 2、如果不是二叉搜索树，但是有指向父节点的指针 ##

如果除了根结点外的每个结点都有个一个指向父节点的指针，那么这个问题就可以转换为[求两个链表的第一个公共结点][Link 1]。

## 3、如果没有指向父节点的指针，普通树 ##

思路一、思路二：[http://zhedahht.blog.163.com/blog/static/25411174201081263815813/][http_zhedahht.blog.163.com_blog_static_25411174201081263815813]

# 十七、二叉搜索树的前驱和后继 #

二叉搜索树按照中序遍历时，输出的节点是从小到大排列好的。如果各个节点关键字不相等，那么节点x的前驱就是中序遍历的x的前一个，后继就是中序遍历的x的后一个节点。  
**寻找节点后继的思想**：**如果节点的右子树不为空，其后继就是右子树的最小节点；如果节点x右子树为空，并且该节点有后继节点y，则y是x的最低的祖先节点，并且y的左儿子也是x的祖先(这里可以认为每个节点都是自己的祖先)。**

如下图所示，节点13没有右子树，而该节点是有后继的，因此其后继节点就是其最低的祖先节点，且该祖先节点的左孩子也是其祖先。那么可以判断13的后继节点是15。

再比如，节点9没有右子树，且该节点有后继节点；那么13是节点9的后继节点，此时13的右孩子是节点9自己，此时可以认为9是自己的祖先节点。

![Center][]

同理，对于**寻找前驱节点**：**如果节点x有左子树，那么其前驱节点就是左子树中最大的那个节点；如果该节点x没有左子树，且该节点存在前驱节点y，则y是x的最低祖先结点，且y的右孩子也是x的祖先（可以认为自己是自己的祖先节点）。**

例如上图中9没有左子树，因此其前驱为7，此时7是9的祖先，且7的右节点也是9的祖先。

再比如7的前驱是6，此时6的右孩子（节点7本身）是节点7的祖先节点（7是7本身的祖先节点）。

从上面的分析可以看出，要求出某结点的前驱和后继节点，都需要指向结点父亲的指针，如果有指向父节点的指针，那么，问题就很容易了，代码参考[STL源码：红黑树][STL]。

伪代码如下：

找后继：

TREE-SUCCESSOR(x)
    	if rithx[x]≠NIL
    		then return TREE-MINIMUM(right[x])
    	y←p[x]
    	while y≠NIL and x=right[y]
    	        do x←y
    		 y←p[y]
    	return y

找前驱：

TREE-PREDECESSOR(x)
    	if left[x]≠NIL
    		 then return TREE-MAXMUM(left[x])
    	y←p[x]
    	while y≠NIL and x=left[x]
    		do x←y
    			y←p[y]
    	return y

[http_www.cnblogs.com_miloyip_archive_2010_05_12_binary_tree_traversal.html]: http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html
[SouthEast]: /images/20220806/bfe5bb6d9e534f8090a60a173a6c5444.png
[SouthEast 1]: /images/20220806/54dc7acdf2594876a983b94b77828b0c.png
[Link 1]: http://blog.csdn.net/u013074465/article/details/41452147#t16
[http_zhedahht.blog.163.com_blog_static_25411174201081263815813]: http://zhedahht.blog.163.com/blog/static/25411174201081263815813/
[Center]: /images/20220806/9240777dff32414eac6b01ac4eb76be5.png
[STL]: http://blog.csdn.net/u013074465/article/details/44751877#t3