第四題
題目：輸入一個整數和一棵二元樹。
從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
打印出和與輸入整數相等的所有路徑。
例如 輸入整數22和如下二元樹
10
/ \
5 12
/ \
4 7
則打印出兩條路徑：10, 12和10, 5, 7。
分析：（本人拙見）
這道題目主要考察的是二叉樹的非遞歸周游，因此很容易想到使用棧來作為數據遍歷的時候的節點存儲。每次壓入棧數據的時候判斷是否達到了葉節點且棧中元素之和
滿足給定值，如果滿足上面兩個條件，為真，打印棧中的元素。繼續遍歷。
首先是樹的構建，為了方便這裡使用了廣度優先的插入算法，跟這道題木有太大關系。
然後就是對於二叉樹的非遞歸周游。
[cpp]
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
typedef struct NodeBinaryTree
{
int value;
NodeBinaryTree * nodeLeft;
NodeBinaryTree * nodeRight;
}NodeBinaryTree;
class BinaryTree
{
private:
NodeBinaryTree * root;
stack<int> Path;
public:
BinaryTree();
//~BSTree(); 這個地方需要遞歸delete所有節點
NodeBinaryTree * Root(){return root;}
void addNodeBSTree(const int item);
void inOrder(NodeBinaryTree * root);
void inOrderStack(const int item);
};
BinaryTree::BinaryTree()
{
root = NULL;
}
void BinaryTree::addNodeBSTree(const int item)
{
//這個地方寫代碼的時候使用了廣度優先的插入節點，當時不知道怎麼想的就寫了這個
//與本題關系不大，可以直接忽略
if(NULL==root)
{
NodeBinaryTree * node2add = new NodeBinaryTree();
node2add->value = item;
node2add->nodeLeft = NULL;
node2add->nodeRight = NULL;
root = node2add;
}
else
{
//BinaryTree的節點的插入采用的是廣度優先的插入方式，因此這裡我們定義了一個隊列,直接采用了STL裡面的隊列
using std::queue;
queue<NodeBinaryTree *> aQueue;
NodeBinaryTree * pointer = root;
if(pointer)
aQueue.push(pointer);
while(!aQueue.empty())
{
pointer = aQueue.front();
aQueue.pop();
if(NULL!=pointer->nodeLeft && NULL!=pointer->nodeRight){//為什麼書上這個地方有括號
aQueue.push(pointer->nodeLeft);
aQueue.push(pointer->nodeRight);
}
else if(NULL!=pointer->nodeLeft && NULL==pointer->nodeRight)
{
//找到當前的沒有右子樹的點，將待加入的點插入的右子樹
NodeBinaryTree * node2add = new NodeBinaryTree();
pointer->nodeRight = node2add;
node2add->value = item;
node2add->nodeLeft = NULL;
node2add->nodeRight = NULL;
break;
}
else //說明是左子樹是NULL
{
NodeBinaryTree * node2add = new NodeBinaryTree();
pointer->nodeLeft = node2add;
node2add->value = item;
node2add->nodeLeft = NULL;
node2add->nodeRight = NULL;
break;
}
}
}
}
void BinaryTree::inOrder(NodeBinaryTree * root)
{
if(NULL!=root)
{
inOrder(root->nodeLeft);
cout<<root->value<<" ";
inOrder(root->nodeRight);
}
}
void BinaryTree::inOrderStack(const int item)
{
cout<<"the expected sum of the path is "<<item<<endl;
NodeBinaryTree * root = this->root;
//非遞歸周游二叉樹
enum Tags{Left,Right};
struct StackElement
{
NodeBinaryTree * pointer;
Tags tag;
};
StackElement element;
StackElement elementCopy;
stack<StackElement> aStack;
stack<StackElement> aCopyStack;
NodeBinaryTree * pointer;
if(NULL==root){return;}
else pointer = root;
int sumValue = 0;
int nodeValue;
while(true){
while(NULL!=pointer)
{
element.pointer = pointer;
element.tag = Left;
aStack.push(element);
sumValue = sumValue + element.pointer->value;
pointer = pointer->nodeLeft;
}
element = aStack.top();
if(element.tag==Right && NULL==element.pointer->nodeLeft&& NULL== element.pointer->nodeRight && item==sumValue)
{
//因為每次考慮Tag的時候考慮了right和left 所以要使不使用element.tag==Right判斷條件會打印兩遍
//若找到了路徑
//輸出棧中的元素 然後再把棧重新組織成原來的樣子
while(!aStack.empty()){
elementCopy = aStack.top();
aStack.pop();
aCopyStack.push(elementCopy);
}
while(!aCopyStack.empty()){
elementCopy = aCopyStack.top();
aCopyStack.pop();
aStack.push(elementCopy);
cout<<elementCopy.pointer->value<<" ";
}
cout<<endl;
}
aStack.pop();
sumValue = sumValue - element.pointer->value;
pointer = element.pointer;
//從右子樹回來
while(element.tag==Right){
if(aStack.empty()) return;
else {
element = aStack.top();
aStack.pop();
sumValue = sumValue - element.pointer->value;
pointer = element.pointer;
}
}
//從左子樹回來
element.tag = Right;
aStack.push(element);
sumValue = sumValue + element.pointer->value;
pointer = pointer->nodeRight;
}
}
int main()
{
BinaryTree a;
a.addNodeBSTree(1);
a.addNodeBSTree(2);
a.addNodeBSTree(3);
a.addNodeBSTree(4);
a.addNodeBSTree(6);
a.addNodeBSTree(5);
a.addNodeBSTree(7);
NodeBinaryTree * head = a.Root();
//test inorder
a.inOrder(head);
cout<<endl;
a.inOrderStack(9);
return 0;
}
