题记
之前对二叉查找树的基本操作写了一篇文章《二叉查找树》，觉得还不过瘾。毕竟还没有实践。所以找了几个笔试题做做。小结如下：
经典题1：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
比如，二叉查找树的结构为
10
/ \
6 14
/ \ / \
4 8 12 16
调整后的结果是 4=6=8=10=12=14=16
经典题2：
输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
比如
10
/ \
6 14
/ \ / \
4 8 12 16
变成
10
/ \
14 6
/ \ / \
16 12 8 4
以上两题的二叉树结构都是
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
请先自己试着解答，然后看下面的分析和代码！【注意，本代码最后没有对bstree的内存释放！仅做参考】
题一：分析部分请见注释！！
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct BSTreeNode{
int m_value;
struct BSTreeNode *m_pLeft;
struct BSTreeNode *m_pRight;
}BSTreeNode;
//生成二叉查找树
BSTreeNode *insert(BSTreeNode *tree,BSTreeNode *n){
if(tree == NULL){
tree = n;
}else if(n->m_value < tree->m_value){
tree->m_pLeft = insert(tree->m_pLeft,n);
}else{
tree->m_pRight = insert(tree->m_pRight,n);
}
return tree;
}
//方法一:递归思想。
//假设节点左右子树都已经是"已排序的双向链表"，比如左子树链表指针为tLeft,右子树链表指针为tRight
//那么，只需要把此时的节点加入到这个链表里，最后返回指向这个调整后的链表即可！
//参数含义：
//cnode：当前处理的节点
//asLeft: 值取-1,0或1。-1表示无父节点;1表示当前节点是其父节点的左孩子;0表示是其父节点的右孩子；
//之所以asLeft这样取值，是因为最后返回的指针会指向链表的尾部或头部(尾部是cnode的前驱，头部是cnode的后继)！需要用它来判断！
//连接左孩子时需要链表的尾指针(tLeft)，连接右孩子时需要链表的头指针(tRight)！
BSTreeNode * convert(BSTreeNode *cnode,int asLeft){
if(cnode == NULL){
return NULL;
}
BSTreeNode *tLeft=NULL, *tRight=NULL;
if(cnode->m_pLeft != NULL){
tLeft = convert(cnode->m_pLeft,1);
}
if(tLeft != NULL){//调整好左子树
cnode->m_pLeft = tLeft;
tLeft->m_pRight = cnode;//左指针指向前驱节点，右指针指向后继节点
}
if(cnode->m_pRight != NULL){
tRight = convert(cnode->m_pRight,0);
}
if(tRight != NULL){//调整好右子树
cnode->m_pRight = tRight;
tRight->m_pLeft = cnode;
}
//以上部分已经调整好左右子树了，下面来返回该链表指针
if(asLeft == 0 || asLeft == -1){//如果没有父亲，则让其指向最小节点！
while(cnode->m_pLeft != NULL){
cnode = cnode->m_pLeft;
}
}else{//如果以cnode为根的子树是其父亲的左子树，那么父亲的前驱就是这颗子树中最大的节点
while(cnode->m_pRight != NULL){
cnode = cnode->m_pRight;
}
}
return cnode;
}
//方法二：还是递归法
//区别方法一：本方法利用中序遍历，每次递归时只假设当前节点cnode的前驱已经是一个排序的双向链表！
BSTreeNode * convert2(BSTreeNode *cnode,BSTreeNode *orderedList){
if(cnode == NULL){
return NULL;
}
//先访问左子树
if(cnode->m_pLeft != NULL){
orderedList = convert2(cnode->m_pLeft,orderedList);
}
if(orderedList != NULL){//调整orderedList和cnode的关系
cnode->m_pLeft = orderedList;
orderedList->m_pRight = cnode;
}
//生成新的orderedList
orderedList = cnode;
//访问右子树
if(cnode->m_pRight != NULL){
orderedList = convert2(cnode->m_pRight,orderedList);
}
return orderedList;//返回的是最大节点的指针，这点和方法一不同(方法一也可以改成这样！)
}
//生成测试的二叉查找树
BSTreeNode * create(){
int data[]={10,6,14,4,8,12,16};
int i;
BSTreeNode * tree=NULL;
for(i=0;i<sizeof(data)/sizeof(int);i++){
BSTreeNode *fresh = (BSTreeNode*)malloc(sizeof(BSTreeNode));
fresh->m_value = data[i];
fresh->m_pLeft = fresh->m_pRight = NULL;
tree = insert(tree,fresh);
}
return tree;
}
//测试方法一
void test_convert(){
BSTreeNode *p=NULL, *fptr=NULL;
BSTreeNode *tree = create();
tree = convert(tree,-1);
p=tree;
while(p != NULL){
printf("%d,",p->m_value);
fptr = p;
p = p->m_pRight;
free(fptr);
}
printf("\n");
}
//测试方法二
void test_convert2(){
BSTreeNode *p=NULL, *fptr=NULL;
BSTreeNode *tree = create();
printf("convert2:\n");
tree = convert2(tree,NULL);
p=tree;
while(p != NULL){//从右向左遍历
printf("%d,",p->m_value);
fptr=p;
p=p->m_pLeft;
free(fptr);
}
printf("\n");
}
int main(){
test_convert();
test_convert2();
return 0;
}
题二：
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct BSTreeNode{
int m_value;
struct BSTreeNode *m_pLeft;
struct BSTreeNode *m_pRight;
}BSTreeNode;
//先得写个简单的int栈
typedef struct stack{
BSTreeNode* data[MAXSIZE];
int top;
}Stack;
//-------- 栈的各种操作--------------------//
int isEmpty(Stack *s){
if(s->top == 0){
return 1;
}else{
return 0;
}
}
int push(Stack *s, BSTreeNode *node){
if(s->top>=MAXSIZE){
printf("error:栈已满\n");
return -1;
}
s->data[s->top++] = node;
return 1;
}
BSTreeNode * pop(Stack *s){
if(s->top == 0){
printf("error:栈内没有元素\n");
return NULL;
}
return s->data[--(s->top)];
}
//------- 树的各种操作 --------------------------//
//生成二叉查找树
BSTreeNode *insert(BSTreeNode *tree,BSTreeNode *n){
if(tree == NULL){
tree = n;
}else if(n->m_value < tree->m_value){
tree->m_pLeft = insert(tree->m_pLeft,n);
}else{
tree->m_pRight = insert(tree->m_pRight,n);
}
return tree;
}
//生成测试的二叉查找树
BSTreeNode * create(){
int data[]={10,6,14,4,8,12,16};
int i;
BSTreeNode * tree=NULL;
for(i=0;i<sizeof(data)/sizeof(int);i++){
BSTreeNode *fresh = (BSTreeNode*)malloc(sizeof(BSTreeNode));
fresh->m_value = data[i];
fresh->m_pLeft = fresh->m_pRight = NULL;
tree = insert(tree,fresh);
}
return tree;
}
//非递归的将二叉查找树变为其镜像
BSTreeNode * mirror(BSTreeNode *cnode){
if(cnode == NULL){
return NULL;
}
Stack s;
s.top=0;//初始化栈指针
BSTreeNode *p = cnode, *tmp=NULL;
while(cnode!=NULL || !isEmpty(&s)){
if(cnode){
push(&s,cnode);
cnode = cnode->m_pLeft;
}else{
cnode = pop(&s);
//交换cnode的左右孩子
tmp = cnode->m_pLeft;
cnode->m_pLeft = cnode->m_pRight;
cnode->m_pRight = tmp;
cnode = cnode->m_pLeft;
}
}
return p;
}
//递归版本
BSTreeNode *re_mirror(BSTreeNode *cnode){
BSTreeNode * tmp=NULL;
if(cnode != NULL){
//交换左右子树的指针
tmp = cnode->m_pLeft;
cnode->m_pLeft = cnode->m_pRight;
cnode->m_pRight = tmp;
//递归
cnode->m_pLeft = re_mirror(cnode->m_pLeft);
cnode->m_pRight = re_mirror(cnode->m_pRight);
}
return cnode;
}
void printTree(BSTreeNode *cnode){
if(cnode != NULL){
printTree(cnode->m_pLeft);
printf("%d,",cnode->m_value);
printTree(cnode->m_pRight);
}
}
int main(){
BSTreeNode *tree = create();
tree = re_mirror(tree);
BSTreeNode *p=NULL, *fptr=NULL;
printTree(tree);
printf("\n");
return 0;
}
小结：要想解决二叉树中的大多数问题一定要理解"递归"的思想！而且要知道非递归算法的写法！我自己对非递归算法都还有点不熟，汗！！
本文重点参考了 http://zhedahht.blog.163.com/ 的内容，深表感谢！！
我的代码都是用纯C语言实现的，而且分析写在了注释中。代码没有做过"优化"，主要是便于理解解题思想！
(全文完)