题目：输入一个整数和一棵二元树。

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

例如 输入整数22和如下二元树

  10  

  / /   

 5  12   

 /   /   

4     7

则打印出两条路径：10, 12和10, 5, 7。

 

二叉树节点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree

{

    int m_nValue; // value of node

    BinaryTreeNode *m_pLeft; // left child of node

    BinaryTreeNode *m_pRight; // right child of node

};

#include <iostream>
#include <vector>
using namespace std;

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode *m_pLeft;
    BinaryTreeNode *m_pRight;
}n1,n2,n3,n4,n5;

BinaryTreeNode* buildTree()
{
    n1.m_nValue = 10;
    n1.m_pLeft = &n2;
    n1.m_pRight = &n3;
    n2.m_nValue = 5;
    n2.m_pLeft = &n4;
    n2.m_pRight = &n5;
    n3.m_nValue = 12;
    n4.m_nValue = 4;
    n5.m_nValue = 7;
    n3.m_pLeft = n3.m_pRight = n4.m_pLeft = n4.m_pRight = n5.m_pLeft = n5.m_pRight = NULL;
    return &n1;
}

void FindPath(BinaryTreeNode *pCurrent,int sum,int curval,vector<int> &path)
{
    if(pCurrent == NULL)
    {
        return ;
    }
    curval += pCurrent->m_nValue;
    path.push_back(pCurrent->m_nValue);
    if(curval == sum)
    {
        if(pCurrent->m_pLeft == NULL && pCurrent->m_pRight == NULL)
        {
            for(vector<int>::iterator it = path.begin();it != path.end();it++)
            {
                cout<<*it<<" ";
            }
            cout<<endl;
        }
    }
    else 
    {
        if(pCurrent->m_pLeft)
        {
            FindPath(pCurrent->m_pLeft,sum,curval,path);
        }
        if(pCurrent->m_pRight)
        {
            FindPath(pCurrent->m_pRight,sum,curval,path);
        }
    }        
    curval -= pCurrent->m_nValue;
    path.pop_back();
}

int main()
{
    BinaryTreeNode *pRoot;
    vector<int> path;
    
    pRoot = buildTree();
    FindPath(pRoot,22,0,path);
    
    system("pause");
    return 0;
}

题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10

/ \

6 14

/ \ / \

4 8 12 16

转换成双向链表

4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：

struct BSTreeNode

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

这个题不难，遍历一下即可，需要注意的是指针的链接不要出错。

#include <iostream>
using namespace std;

struct BSTreeNode
{
    int m_nValue;
    BSTreeNode *m_pLeft;
    BSTreeNode *m_pRight;
};

typedef BSTreeNode DeList;
DeList *head;
DeList *index;

//构造二叉树 
void buildBSTree(BSTreeNode *(&pCurrent),int value)
{
    if(pCurrent == NULL)
    {
        pCurrent = new BSTreeNode();
        pCurrent->m_pLeft = NULL;
        pCurrent->m_pRight = NULL;
        pCurrent->m_nValue = value;
    }
    else 
    {
        if(value < pCurrent->m_nValue)
        {
            buildBSTree(pCurrent->m_pLeft,value);
        }
        else if(value > pCurrent->m_nValue)
        {
            buildBSTree(pCurrent->m_pRight,value);
        }
    }
}

//转换成双向链表 
void convertToDeList(BSTreeNode *pCurrent)
{
    pCurrent->m_pLeft = index;
    if(index != NULL)
    {
        index->m_pRight = pCurrent;
    }
    else
    {
        head = pCurrent;
    }
    index = pCurrent;
    cout<<pCurrent->m_nValue<<endl;
}

//中序遍历二叉树 
void inOrder(BSTreeNode *pCurrent)
{
    if(pCurrent != NULL)
    {
        inOrder(pCurrent->m_pLeft);
        convertToDeList(pCurrent);
        inOrder(pCurrent->m_pRight);
    }
}

int main()
{
    BSTreeNode *pRoot = NULL;
    head = index = NULL;
    
    buildBSTree(pRoot,10);
    buildBSTree(pRoot,4);
    buildBSTree(pRoot,6);
    buildBSTree(pRoot,8);
    buildBSTree(pRoot,14);
    buildBSTree(pRoot,15);
    buildBSTree(pRoot,16);
    
    inOrder(pRoot);
    system("pause");
    
    return 0;
}