澳门新葡亰信誉平台游戏遍历-哪位大神帮忙看看 老是报错

by admin on 2020年1月20日

话非常少说,上代码

哪位大神帮助看看 老是报错
#include
using namespace std;
#include
#include
typedef struct node
{
char data;
struct node *lchild,*rchild;
}BinTree;

include<iostream>

前中序需求叁个栈: stack<struct tree*> st;

typedef struct node1
{
BinTree *btnode;
bool isFirst;
}BTNode;

include<stack>

后序需求带标志的栈: stack<struct flagNode> sk;

void creatBinTree(char s,BinTree &rootState of Qatar//创设二叉树,s为形如A格局的字符串
{
int i;
bool isRight=false;
stack<BinTree> s1; //寄存结点
stack s2; //贮存分隔符
BinTree
p,*temp;
root->data=s[0];
root->lchild=NULL;
root->rchild=NULL;
s1.push;
i=1;
while(i {
if(s[i]==’
{
s2.push;
isRight=false;
}
else if(s[i]==’,’)
{
isRight=true;
}
else if’)
{
s1.pop();
s2.pop();
}
else if(isalpha
{
p=(BinTree *)malloc(sizeof;
p->data=s[i];
p->lchild=NULL;
p->rchild=NULL;
temp=s1.top();
if(isRight==true)

include<queue>

struct flagNode

{
temp->rchild=p;
cout<data<<“的右孩子是”< }
else
{
temp->lchild=p;
cout<data<<“的左孩子是”<<s[i]<<endl;
}
if(s[i+1]==’
s1.push;
}
i++;
}

include <list>

using namespace std;

/*
二叉树定义
*/
typedef struct BTNode{
char data;

struct BTNode *lchild;
struct BTNode *rchild;

}BTNode;

/*
构建二叉树
*/
BTNode *Create(BTNode T){
char ch;
cin >> ch;
if (ch == ‘#’){
T = NULL;
}
else{
T = (BTNode
)malloc(sizeof(BTNode));
T->data = ch;
T->lchild = Create(T->lchild);
T->rchild = Create(T->rchild);
}
return T;
}

/*

  • 先序遍历递归
    */
    void Preorder(BTNode *T){

    if (T != NULL){
    cout << T->data << ” “;
    Preorder(T->lchild);
    Preorder(T->rchild);
    }
    }

/*

  • 先序遍历非递归
    */

void Preorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;
if (T != NULL){
sta.push(T);
while (!sta.empty()){
p = sta.top();
cout << p->data << ” “;
sta.pop();

        if (p->rchild != NULL){
            sta.push(p->rchild);
        }

        if (p->lchild != NULL){
            sta.push(p->lchild);
        }
    }
}

}
/*

  • 中序遍历递归
    */
    void Inorder(BTNode *T){
    if (T != NULL){
    Inorder(T->lchild);
    cout << T->data << ” “;
    Inorder(T->rchild);
    }
    }

/*

  • 中序遍历非递归
    */

void Inorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;

if (T != NULL){
    while (!sta.empty() || p != NULL){
        while (p != NULL){
            sta.push(p);
            p = p->lchild;
        }
        if (!sta.empty()){
            p = sta.top();
            sta.pop();
            cout << p->data << "    ";
            p = p->rchild;
        }
    }
}

}
/*

  • 后序遍历递归
    */

void Postorder(BTNode *T){
if (T != NULL){
Postorder(T->lchild);
Postorder(T->rchild);
cout << T->data << ” “;
}
}

/*
后序遍历非递归
*/
void Postorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;
BTNode *q=NULL;

while (p != NULL || !sta.empty())
{
    while (p != NULL){
        sta.push(p);
        p = p->lchild;
    }
    p = sta.top();              //访问栈顶,判断若有右节点则右节点进栈,否则出栈。
    if (p->rchild == NULL || p->rchild == q){
        cout << p->data << "    ";
        q = p;
        sta.pop();
        p = NULL;
    }
    else{
        p = p->rchild;
    }
}

}
/*
双栈法 后序遍历非递归
*/
void Postorder3(BTNode *T){
stack<BTNode *> sta,stb;
BTNode *p = T;
sta.push(p);
while (!sta.empty()){
p = sta.top();
sta.pop();
stb.push(p);

    if (p->lchild != NULL){
        sta.push(p->lchild);
    }

    if (p->rchild != NULL){
        sta.push(p->rchild);
    }

}

while (!stb.empty()){
    cout << stb.top()->data << "    ";
    stb.pop();
}

}

/*
档期的顺序遍历
*/

void Levelorder(BTNode *T){
queue<BTNode *> qu;
BTNode *p = T;
if (p!=NULL)
{
qu.push(p);
while (!qu.empty()){
p = qu.front();
cout << p->data << ” ” ;
qu.pop();
if (p->lchild != NULL){
qu.push(p->lchild);
}

        if (p->rchild!=NULL){
            qu.push(p->rchild);
        }
    }
}

}

/*

  • 求二叉树的纵深
    */
    int GetDepth(BTNode *T) {

    /* if(T!=NULL){
    ++n;
    n=GetDepth(T->lchild,n)>GetDepth(T->rchild,n) ?
    GetDepth(T->lchild,n) : GetDepth(T->rchild,n);
    }*/
    int ld, rd;
    if (T == NULL) {
    return 0;
    }
    else {
    ld = GetDepth(T->lchild);
    rd = GetDepth(T->rchild);

      return (ld > rd ? ld : rd) + 1;
    

    }
    }

/*

  • 检索data为k的节点是或不是留存
    */

int FindData(BTNode *T, char k) {
//queue<BTNode *> qu;
BTNode p = T;
/
if(T!=NULL){
qu.push(p);
while(!qu.empty(卡塔尔(قطر‎卡塔尔(قطر‎{ //档案的次序遍历查找
p=qu.front();
if(p->data==k){
return 1;
}
qu.pop();
if(p->lchild!=NULL){
qu.push(p->lchild);
}
if(p->rchild!=NULL){
qu.push(p->rchild);
}

}
return  0;
}*/

if (T == NULL) {
    return 0;
}
else {
    if (T->data == k) {        //先序遍历查找
        return 1;
    }

    if (FindData(T->lchild, k) > 0) {
        return 1;
    }
    else {
        return FindData(T->rchild, k);
    }

}

}

/*

  • 输出先序遍历第K个节点的值
    */

void ShowK(BTNode T, int k) {
if (T != NULL) {
/
++n; //定义全局变量n
if(n==k){
cout<<“第”<<k<<“个节点的值为:
“<<T->data<<endl;
return;
}*/

    ShowK(T->lchild, k);
    ShowK(T->rchild, k);
}

}

/*

  • 求二叉树的肥瘦
    */
    int GetWidth(BTNode *T) {

    queue<BTNode *> qu;
    int width = 1;
    int currwidth = 1;
    int nextwidth = 0;
    BTNode *p = T;
    if (T != NULL) {
    qu.push(p);
    while (!qu.empty()) {
    while (currwidth > 0) {
    p = qu.front();
    currwidth–;
    qu.pop();

              if (p->lchild != NULL) {
                  qu.push(p->lchild);
                  nextwidth++;
              }
              if (p->rchild != NULL) {
                  qu.push(p->rchild);
                  nextwidth++;
              }
          }
    
          if (nextwidth > width)
              width = nextwidth;
          currwidth = nextwidth;
          nextwidth = 0;
      }
    
      return width;
    

    }
    return 0;
    }

/*

  • 二叉树第K层的节点个数
    */

int GetNum(BTNode *T, int k) {
queue<BTNode *> qu;
BTNode *p = T;
int currwidth = 1;
int nextwidh = 0;
int i = 0;
if (p != NULL) {
qu.push(p);
while (!qu.empty()) {
++i;
if (i == k) {
return currwidth;
}
while (currwidth > 0) {
p = qu.front();
currwidth–;
qu.pop();

            if (p->lchild != NULL) {
                qu.push(p->lchild);
                nextwidh++;
            }

            if (p->rchild != NULL) {
                qu.push(p->rchild);
                nextwidh++;
            }
        }
        currwidth = nextwidh;
        nextwidh = 0;
    }
}

return 0;

}

/*

  • 求叶子节点个数
    */

int Getleaves(BTNode *T) {
queue<BTNode *> qu;
BTNode *p = T;
int n = 0;
if (p != NULL) {
qu.push(p);
while (!qu.empty()) {
p = qu.front();

        qu.pop();
        if (p->lchild != NULL) {
            qu.push(p->lchild);
        }

        if (p->rchild != NULL) {
            qu.push(p->rchild);
        }

        if (p->lchild == NULL && p->rchild == NULL) {
            ++n;
        }
    }
}
return n;

}

/*
*前序和中序重新创立二叉树
*/

BTNode *RecreateByPI(char *pre, char *in, int nodeNum) {

if (pre == NULL || in == NULL || nodeNum < 1) {
    return NULL;
}
int i = 0;
BTNode *T;
T = (BTNode *)malloc(sizeof(BTNode));

for (; i < nodeNum; ++i) {
    if (*(in + i) == *pre) {      //先序遍历的第一个节点为根节点
        break;
    }
}
T->data = *pre;

T->lchild = RecreateByPI(pre + 1, in, i);      //i左边递归建立左子树
T->rchild = RecreateByPI(pre + i + 1, in + i + 1, nodeNum - 1 - i);    //i右边递归建立右子树
return T;

}

/*

  • 中序和后序重新创建树
    */

BTNode *RecreateByIL(char *last, char *in, int nodeNum) {
if (last == NULL || in == NULL || nodeNum < 1) {
return NULL;
}
int i = 0;
BTNode *T = (BTNode )malloc(sizeof(BTNode));
for (; i < nodeNum; ++i) {
if (
(in + i) == *(last + nodeNum – 1)) {
break;
}
}

T->data = *(in + i);
T->lchild = RecreateByIL(last, in, i);
T->rchild = RecreateByIL(last + i, in + i + 1, nodeNum - i - 1);

return T;

}

/*

  • 四个节点的集体祖先
    */

BTNode *FindAns(BTNode *T, char a, char b) {
if (T == NULL) {
return NULL;
}
if (T->data == a || T->data == b) {
return T;
}

BTNode *left = FindAns(T->lchild, a, b);
BTNode *right = FindAns(T->rchild, a, b);

if (left != NULL && right != NULL) {
    return T;
}

return (left != NULL) ? left : right;

}

/*

  • 笔录路线找寻国有祖先
    */

bool FindPath(BTNode *T, list<char> &li, char c) {
if (T == NULL) {
return false;
}
li.push_back(T->data);
if (T->data == c) {
return true;
}

bool find = FindPath(T->lchild, li, c) || FindPath(T->rchild, li, c);

if (find) {
    return true;
}
li.pop_back();       //在左树没找到,就弹出左树元素
return false;

}

char FindAns2(BTNode *T, char a, char b) {
if (T == NULL) {
return -1;
}

list<char> l1, l2;
bool b1 = FindPath(T, l1, a);
bool b2 = FindPath(T, l2, b);
char ans;

list<char>::iterator i1 = l1.begin();
list<char>::iterator i2 = l2.begin();
if (b1 && b2) {

    while (i1 != l1.end() && i2 != l2.end()) {
        if (*i1 == *i2) {
            ans = *i1;
        }
        else {
            break;
        }


        i1++;
        i2++;
    }
}

return ans;

}

/*

  • 求二叉树节点的最大间隔
    */

int mas = 0;

int MaxLegthTwoNode(BTNode *T) {

if (T == NULL) {
    return 0;
}

if (T->lchild == NULL && T->rchild == NULL) {
    return 0;
}

int a = GetDepth(T->lchild) + GetDepth(T->rchild);
int b = MaxLegthTwoNode(T->lchild);
int c = MaxLegthTwoNode(T->rchild);

int dis = (a > b ? a : b) > c ? (a > b ? a : b) : c;     //最大距离为左子树最大高度,或者右子树最大高度,或者左右深度之和

if (dis > mas) {
    mas = dis;
}
return dis;

}

/*

  • 打字与印刷根节点到叶子节点路线
    */
    list<char> li;
    void PrintRToL(BTNode T) {
    /
    queue<BTNode *> qu;
    BTNode *p = T;
    if (p != NULL) {
    qu.push(p);
    while (!qu.empty()) {
    p = qu.front();

    qu.pop();
    if (p->lchild != NULL) {
    qu.push(p->lchild);
    }
    if (p->rchild != NULL) {
    qu.push(p->rchild);
    }

    if (p->lchild == NULL && p->rchild == NULL) {
    list<char> li;
    if (FindPath(T, li, p->data)) {
    list<char>::iterator it = li.begin(卡塔尔(قطر‎; //记录叶子节点路线方法
    while (it != li.end()) {
    cout << it << ” “;
    it++;
    }
    }
    cout<<endl;
    }
    }
    }
    /

    if (T != NULL){
    li.push_back(T->data);
    if (T->lchild == NULL && T->rchild == NULL){
    list<char>::iterator it = li.begin();
    while (it != li.end()){
    cout << *it << ” “; //打印栈或队列成分,但不出栈
    it++;
    }
    cout << endl;
    }

      PrintRToL(T->lchild);
      PrintRToL(T->rchild);
      li.pop_back();           //第三次访问的时候,出栈,意味着此节点的左右子树已经遍历完毕,包括叶子节点
    

    }
    }

/*
累积和为钦定值的最长路线
*/
int s, i, tmp;
list<char> l2;
void printMaxSum(BTNode *T, int sum){
if (T != NULL){
li.push_back(T->data);
s += (T->data – ‘0’);
++i;
if (s == sum){
if (tmp < i){
tmp = i;
l2.clear();

            if (!li.empty()){
                list<char>::iterator it = li.begin();
                while (it != li.end())
                {
                    l2.push_back(*it);
                    ++it; 
                }
            }
        }

    }

    printMaxSum(T->lchild,sum);
    printMaxSum(T->rchild,sum);

    s -= (li.back() - '0');
    --i;
    li.pop_back();
}

if (li.empty()){
    list<char>::iterator it = l2.begin();
    while (it != l2.end())
    {
        cout << *it << "    ";
        ++it;
    }
}

}

/*
按层打字与印刷和ZigZag打字与印刷
*/

void printZigZag(BTNode T){
queue<BTNode
> qu;
stack<char> st;
BTNode *p = T;
int currWidth = 1;
int nextWidth = 0;
int i = 1;
if (p != NULL){
qu.push(p);

    while (!qu.empty()){
        if (i % 2 == 0){
            cout << "Level " << i << " from right to left : ";
        }
        else{
            cout << "Level " << i << " from left to right : ";
        }
        while (currWidth > 0){
            currWidth--;
            p = qu.front();
            qu.pop();
            if (i % 2 == 0){
                st.push(p->data);
            }
            else{
                cout << p->data << " ";
            }

            if (p->lchild != NULL){
                qu.push(p->lchild);
                nextWidth++;
            }

            if (p->rchild != NULL){
                qu.push(p->rchild);
                nextWidth++;
            }
        }
        while (!st.empty()){
            cout << st.top() << " ";
            st.pop();
        }
        cout << endl;
        ++i;
        currWidth = nextWidth;
        nextWidth = 0;

    }
}

}

void mmain(){
BTNode *T = NULL;
T = Create(T);

cout << "先序遍历:" << endl;
Preorder(T);
cout << endl;
/*
cout << "先序遍历非递归" << endl;
Preorder2(T);
cout << endl;

cout << "中序遍历:" << endl;
Inorder(T);
cout << endl;

cout << "中序遍历非递归:" << endl;
Inorder2(T);
cout << endl;

cout << "后序遍历:" << endl;
Postorder(T);
cout << endl;

cout << "后序遍历非递归:" << endl;
Postorder2(T);
cout << endl;

cout << "后序遍历非递归:" << endl;
Postorder3(T);
cout << endl;

cout << "层次遍历:" << endl;
Levelorder(T);
cout << endl;*/

printZigZag(T);

cout << endl;
system("pause");

}

{

}

   struct tree *ptr;

void display(BinTree root卡塔尔(قطر‎ //呈现树形布局
{
if(root!=NULL)
{
cout<data;
if(root->lchild!=NULL)
{
cout<<‘(‘;
display(root->lchild);
}
if(root->rchild!=NULL)
{
cout<<‘,’;
display(root->rchild);
cout<<‘)’;
}
}
}
void preOrder2(BinTree
rootState of Qatar //非递归前序遍历
{
stack<BinTree> s;
BinTree
p=root;
while(p!=NULL||!s.empty
{
while
{
cout<data<<” “;
s.push;
p=p->lchild;
}
if(!s.empty
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}

   bool right;

void inOrder2(BinTree rootState of Qatar //非递归中序遍历
{
stack<BinTree
> s;
BinTree *p=root;
while(p!=NULL||!s.empty
{
while
{
s.push;
p=p->lchild;
}
if(!s.empty
{
p=s.top();
cout<data<<” “;
s.pop();
p=p->rchild;
}
}

}

}

前序遍历:

void postOrder2(BinTree root卡塔尔国 //非递归后序遍历
{
stack<BTNode
> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty
{
while //沿左子树一直往下搜寻,直至现身没有左子树的结点
{
BTNode *btn=malloc(sizeof;
btn->btnode=p;
btn->isFirst=true;
s.push;
p=p->lchild;
}
if(!s.empty
{
temp=s.top();
s.pop();
if(temp->isFirst==true卡塔尔 //代表是第一遍面世在栈顶
{
temp->isFirst=false;
s.push;
p=temp->btnode->rchild;

    cout << “前序遍历n”;
    p = root;
    while(p != NULL ||
!st.empty())
    {
        if(p != NULL)
        {
            cout <<
p->data << ‘ ‘;
            if(p->rchild !=
NULL)
                st.push(p->rchild);
            p = p->lchild;
        }
        else
        {
            p = st.top();
            st.pop();
        }
    }
    cout << endl;

}
else //第壹遍出未来栈顶
{
cout<btnode->data<<” “;
p=NULL;
}
}
}

 

}

中序遍历:

void postOrder3(BinTree root卡塔尔(قطر‎ //非递归后序遍历
{
stack<BinTree
> s;
BinTree *cur; //当前结点
BinTree *pre=NULL; //前叁次访谈的结点
s.push;
while(!s.empty
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<data<<” “;
//若是当前结点未有子女结点恐怕子女节点皆已被访谈过
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)

    cout << “中序遍历n”;
    p = root;
    while(p != NULL ||
!st.empty())
    {
        if(p != NULL)
        {
            st.push(p);
            p = p->lchild;
        }
        else
        {
            cout <<
st.top()->data << ‘ ‘;
            p = st.top()->rchild;
            st.pop();
        }
    }
    cout << endl;

s.push(cur->lchild);
}
}

 

}

后序遍历:

int main(int argc, char *argv[])
{
char s[100];
while(scanf==1)
{
BinTree *root=(BinTree *)malloc(sizeof;
creatBinTree;
display;
cout<<endl;
preOrder2;
cout<<endl;
inOrder2;
cout<<endl;
postOrder2;
cout<<endl;
postOrder3;
cout<<endl;
}
return 0;
}

    cout << “后序遍历n”;
    stack<flagNode> sk;
    struct flagNode w;
    struct tree *p = root; //
traversal pointer
    while(p != NULL ||
!sk.empty())
    {
        if(p != NULL)
        {
            w.right = false;
            w.ptr = p;
            sk.push(w);
            p = p->lchild;
        }
        else
        {
            if(sk.top().right ==
false)
            {
                sk.top().right = true;
                p = sk.top().ptr->rchild;
            }
            else
            {
                cout <<
sk.top().ptr->data << ‘
‘;
                sk.pop();
            }

        }
    }
    cout << endl;

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图