用C++实现二叉树查找

include

include

using namespace std;

const int StackSize = 100;

char target;

class Stack {

public:

Stack() {

top = -1;

}

void Push(char x) {

if (top == StackSize - 1) throw "上溢";

data[++top] = x;

}

char Pop() {

if (top == -1) throw "下溢";

char x = data[top];

top--;

return x;

}

char GetTop() {

if (top < 0) return top;

char x = data[top];

return x;

}

bool Empty() {

return top == -1;

}

private:

char data[StackSize];

int top;

};

struct BiNode {

char data;

BiNode lChild;

BiNode rChild;

BiNode(char ch) {

data = ch;

lChild = rChild = NULL;

}

};

void CreateBiTree(BiNode* &T)

{

char ch;

cin >> ch;

if (ch == '#') T = NULL;

else

{

T = new BiNode(ch);

CreateBiTree(T->lChild);

CreateBiTree(T->rChild);

}

}

void PreOrder(BiNode* T, vector &v)//将树先序遍历

{

if (T)

{

v.push_back(T->data);

PreOrder(T->lChild, v);

PreOrder(T->rChild, v);

}

}

int main()

{

BiNode* T;

CreateBiTree(T);//按照二叉树的前序序列构造一棵二叉树

vector<char> v;
PreOrder(T, v);//将树先序遍历

Stack S;//定义一个栈

cout << "输入你要搜索的字符：" << endl;
cin >> target;

for (int i = 0; i < v.size(); i++)
{
    if (v[i] == target)//如果找到了目标字符，就输出路径
    {
        cout << "查找结果为：" << endl;
        for (int j = 0; j < S.top + 1; j++)
            cout << S.data[j] << " ";
        cout << v[i] << endl << endl;
    }
    else//如果没找到就记录当前结点
        S.Push(v[i]);
}
cout << "查找结束！" << endl;

}