//给定前序和中序求二叉树!!为什么root->element没办法赋值

#include<iostream>
#include<stack>
#include<queue>
#include<string.h>
using namespace std;

template <class T>
class Tree;

template <class T>
class Node {
friend class Tree<T>;

private:
T element;
Node<T>* leftChild;
Node<T>* rightChild;
Node<T>* p;//前驱
public:
Node();
Node(const T& ele)
{
element = ele;
leftChild = NULL;
rightChild = NULL;
}
Node(const T& ele, Node<T>* l, Node<T>* r)
{
element = ele;
leftChild = l;
rightChild = r;
}
Node<T>* getLeftChild() const
{
return leftChild;
}
Node<T>* getRightChild() const
{
return rightChild;
}
void setLeftChild(Node<T>* l)
{
leftChild = l;
}
void setRightChild(Node<T>* r)
{
rightChild = r;
}
T getValue() const
{
return element;
}
void setValue(const T& val)
{
element = val;
}
bool isLeaf() const
{
if (leftChild == NULL && rightChild == NULL)
return true;
return false;
}
};

template <class T>
class Tree {
private:
Node<T>* root;

public:
Tree()
{
root = NULL;
}
Tree(Node<T>*& r)
{
root = r;
}
void createSearchTree(); //2.3-a 构建二叉搜索树
void visit(Node<T>* current);
Node<T>* search(Node<T>* root, T x);
//2.3-b 二叉搜索树的查找值为x的结点，并返回此结点
void insertNode(const T& value); //2.3-c 二叉搜索树的插入x。
void deleteByCopying(Node<T>*& node); //2.3-d 复制删除
void setRoot(Node<T>* r);
Node<T>* getRoot();
Node<T>* getParent(Node<T>* root, Node<T>* current);
void zhongxudigui(Node<T>* root);
void zhongfei(Node<T>* root);
void houxudigui(Node<T> *root);
void qianxudigui(Node<T> *root);
void houfei(Node<T> *root);
void qianfei(Node<T> *root);
void queding(Node<T> *root);
void insert(Node<T> *root,int m);
void create1(string m,string n);
void preincreatetree(Node<T> *t,string pre,string in);
};
template <class T>
Node<T>* Tree<T>::getParent(Node<T>* root,Node<T>* current)
{
if (root != NULL)
   {
if (root == current) {
cout << "该节点为根结点，无父结点" << endl;
return NULL;
} else if (root->leftChild == current || root->rightChild == current) {
return root;
} else {
getParent(root->leftChild, current);
getParent(root->rightChild, current);
}
}
}
template <class T>
void Tree<T>::create1(string m,string n)
{
root = new Node<T>;
preincreatetree(root,m,n);
}
template <class T>
void Tree<T>::preincreatetree(Node<T> *root,string pre,string in)
{
int i=0;
int count1=0;
root->element=pre[0];
while(in[i]==pre[0])
{
        i++;
        count1=i;//A in
}
cout<<count1;
if(count1!=0)
{
        Node<T>*b;
        root->leftChild=b;
        b->p=root->leftChild;
        b->element=pre[1];
        string Bin;
        string Bpre;
        for(int i=0;i<count1;i++)
        {
            Bin[i]=in[i];
       }
       for(int i=1;i<count1;i++)
        {
            Bpre[i]=pre[i];
       }
       preincreatetree(b,Bpre,Bin);
}
else
{
        Node<T>* c=root->p;
        int m=pre.length();
        for(int i=1;i<m;i++)
        {
            c->rightChild->element=pre[i];
            c=c->rightChild;
       }
}
}
template <class T>
void Tree<T>::insert(Node<T> *root,int m)
{
   using std::queue;
   queue<Node<T> *> Q;
   Node<T> *pointer=root;
   if(pointer)
   {
       Q.push(pointer);
   }
   pointer->element=m;
   Q.pop();
   if(pointer->leftChild)
   {
       Q.push(pointer->leftChild);
   }
   if(pointer->rightChild)
   {
       Q.push(pointer->rightChild);
   }

}
template <class T>
Node<T>* Tree<T>::getRoot()
{
return root;
}
template <class T>
void Tree<T>::createSearchTree()
{
int a;
cout << "输入int型，以0为结束" << endl;
cin >> a;
while (a != 0)
   {
insertNode(a);
cin >> a;
}
}
template <class T>
void Tree<T>::insertNode(const T& value)
{
   Node<T> *p=root,*pre=NULL;
   while(p!=NULL)
   {
       pre=p;
       if(p->element<value)
       {
           p=p->rightChild;
       }
       else p=p->leftChild;
   }
       if(root==NULL)
       {
           root=new Node<T>(value);
       }
       else if(pre->element<value)
           pre->rightChild=new Node<T>(value);
       else
           pre->leftChild=new Node<T>(value);
}
template <class T>
void Tree<T>::qianxudigui(Node<T> *root)
{
   if(root!=NULL)
   {
       cout<<root->element<<" ";
       qianxudigui(root->leftChild);
       qianxudigui(root->rightChild);
       //cout<<root->element<<" ";
   }
}
template <class T>
void Tree<T>::qianfei(Node<T> *root)
{
   using std::stack;
   stack<Node<T>*> S;
   Node<T>* pointer=root;
   while(!S.empty()||pointer)
   {
       if(pointer)
       {
           cout<<pointer->element<<" ";
           if(pointer->rightChild!=NULL)
           {
               S.push(pointer->rightChild);
           }
           pointer=pointer->leftChild;
       }
       else
       {
           pointer=S.top();
           S.pop();
       }
   }
}
template <class T>
void Tree<T>::zhongxudigui(Node<T>* root)
{
if (root != NULL)
   {
   zhongxudigui(root->leftChild);
   cout<<root->element<<" ";
   zhongxudigui(root->rightChild);

}
}
template <class T>
void Tree<T>::zhongfei(Node<T>* root)
{
   using std::stack;// 栈
   stack<Node<T>*> aStack;
   Node<T>* pointer = root;
   while (!aStack.empty() || pointer) {
   if (pointer) {
aStack.push(pointer);// 当前指针入栈
       pointer = pointer->leftChild;   // 左路下降
}
       else
       {// 左子树访问完毕，转向访问右子树
       pointer = aStack.top();       // 获得栈顶元素
       aStack.pop();          // 栈顶元素退栈
       cout<<pointer->element<<" ";   // 访问当前结点
       pointer = pointer->rightChild; // 指针指向右孩子
   }
       }
}
template <class T>
void Tree<T>::houxudigui(Node<T> *root)
{
   if(root!=NULL)
   {
       houxudigui(root->leftChild);
       houxudigui(root->rightChild);
       cout<<root->element<<" ";
   }
}
template <class T>
void Tree<T>::houfei(Node<T> *root)
{
   using std::stack;
   stack<Node<T>* > s;
   Node<T> *p=root,*q =root;
   while(p!=0){
       for(;p->leftChild!=NULL;p=p->leftChild)
       s.push(p);
       while(p!=0&&(p->rightChild==NULL|| p->rightChild==q)){
       cout<<p->element<<" ";
       q =p;
       if(s.empty()) return;
       p=s.top();
           s.pop();
   }
       s.push(p);
       p = p->rightChild;
}

}
int main()
{
   /*Node<int>*tmp1,*tmp2,*tmp3;
Tree<int> st;
   st.createSearchTree();
tmp1=st.getRoot();
cout<<"前序递归"<<endl;
   st.qianfei(tmp1);
   cout<<endl;
st.qianxudigui(tmp1);
cout<<endl;
tmp2=st.getRoot();
cout<<"中序递归"<<endl;
st.zhongfei(tmp2);
cout<<endl;
st.zhongxudigui(tmp2);
cout<<endl;
tmp3=st.getRoot();
cout<<"后序递归"<<endl;
   st.houfei(tmp3);
   cout<<endl;
    st.houxudigui(tmp3);*/
    Node<char>*tmp;
Tree<char> t;
//t.createSearchTree();
tmp=t.getRoot();
    string a1;
    string a2;
    a1='ABECDFGHIJ' ;
   a2='EBCDAFHIGJ' ;
//t.create1(a1,a2);
t.preincreatetree(tmp,a1,a2);
t.qianxudigui(tmp);
return 0;

}

Centos 7分辨率怎么调整成适应虚拟机屏幕大小呢

zhang0610806

1个回复