C++编程问题 - 站长资源库

答案：// 二叉树部分 楼上的都已经写了 我就把第2题 树部分写一下
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

class BinaryTree {
public:
char data;
BinaryTree *lchild, *rchild;
BinaryTree(char d) : lchild(NULL), rchild(NULL) {
data = d;
}
};

class Tree;

class ChildTree {
friend Tree;
private:
ChildTree *next;
Tree *tree;
public:
ChildTree() : next(NULL), tree(NULL) {}
};

class Tree {
private:
char data;
ChildTree *child;
void (*Visit)(char);
Tree(char d) : child(NULL) { data = d; }
public:
Tree() : child(NULL) {}

~Tree() {
if (child != NULL) {
stack<ChildTree*> stk;
for( ; child != NULL; child = child->next)
stk.push(child);
while(!stk.empty()) {
ChildTree *temp = stk.top();
stk.pop();
for( ; temp->tree->child != NULL; temp->tree->child = temp->tree->child->next)
stk.push(temp->tree->child);
delete temp;
}
}
}

bool Create(char *str) {
data = *str++;
if(*str++ != '@')
return false;
queue<ChildTree**> stk;
stk.push(&child);
while(*str != '#') {
ChildTree **temp = stk.front();
stk.pop();
for( ; *str != '@'; ++str, temp = &(*temp)->next) {
*temp = new ChildTree;
(*temp)->tree = new Tree(*str);
stk.push(&(*temp)->tree->child);
}
++str;
}
}

void SetVisitFun(void (*v)(char)) { Visit = v; }

void PreOrder() { PreOrder(this); }
void PreOrder(Tree *head) {
(*Visit)(head->data);
ChildTree *temp = head->child;
for( ; temp != NULL; temp = temp->next)
PreOrder(temp->tree);
}

void PostOrder() { PostOrder(this); }
void PostOrder(Tree *head) {
ChildTree *temp = head->child;
for( ; temp != NULL; temp = temp->next)
PostOrder(temp->tree);
(*Visit)(head->data);
}

void PreOrderUnrec() {
(*Visit)(data);
stack<ChildTree*> stk, tempStk;
ChildTree *temp = child;
for( ; temp != NULL; temp = temp->next)
tempStk.push(temp);
while(!tempStk.empty()) {
stk.push(tempStk.top());
tempStk.pop();
}
while(!stk.empty()) {
temp = stk.top();
stk.pop();
(*Visit)(temp->tree->data);
temp = temp->tree->child;
for( ; temp != NULL; temp = temp->next)
tempStk.push(temp);
while(!tempStk.empty()) {
stk.push(tempStk.top());
tempStk.pop();
}
}
}

void LevelOrderUnrec() {
queue<Tree*> que;
que.push(this);
while(!que.empty()) {
Tree *tempTree = que.front();
que.pop();
(*Visit)(tempTree->data);
ChildTree *tempChild = tempTree->child;
for( ; tempChild != NULL; tempChild = tempChild->next)
que.push(tempChild->tree);
}
}

BinaryTree *ToBinaryTree() {
BinaryTree *head = new BinaryTree(data);
stack<BinaryTree**> bStk;
stack<ChildTree*> tStk;
bStk.push(&head->lchild);
tStk.push(child);
while(!tStk.empty()) {
BinaryTree **bTemp = bStk.top();
bStk.pop();
ChildTree *tTemp = tStk.top();
tStk.pop();
for( ; tTemp != NULL; tTemp = tTemp->next, bTemp = &(*bTemp)->rchild) {
*bTemp = new BinaryTree(tTemp->tree->data);
bStk.push(&(*bTemp)->lchild);
tStk.push(tTemp->tree->child);
}
}
return head;
}
};

void Visit(char d)
{
cout << d << " ";
}

void PreOrder(BinaryTree *head)
{
if(head != NULL) {
Visit(head->data);
PreOrder(head->lchild);
PreOrder(head->rchild);
}
}

int main(void)
{
Tree t;
// 一层一层输 每个结点以@结束 #作为总的结束符
t.Create("-@+/@a*@ef@@b-@@@@cd@@@#");
t.SetVisitFun(Visit);
t.PreOrder();
cout << endl;
t.PreOrderUnrec();
cout << endl;
t.PostOrder();
cout << endl;
t.LevelOrderUnrec();
cout << endl;
BinaryTree *head = t.ToBinaryTree();
PreOrder(head);
getchar();
return 0;
}
1.先序遍历非递归算法
void PreOrderUnrec(Bitree *t)
{
    Stack s;
    StackInit(s);
    Bitree *p=t;
    
    while (p!=NULL || !StackEmpty(s))
    {
        while (p!=NULL)             //遍历左子树
        {
            visite(p->data);
            push(s,p);
            p=p->lchild;  
        }
        
        if (!StackEmpty(s))         //通过下一次循环中的内嵌while实现右子树遍历
        {
            p=pop(s);
            p=p->rchild;        
        }//endif
                
    }//endwhile 
}
去csdn发发帖子吧 问问里的牛人太少了  www.csdn.net  我以前就问过 等了N天都没有答案的  前车之鉴啊去csdn发帖子吧 问问里的牛人太少了 我以前也问过 一直到问题过期都没答案  www.csdn.net2.中序遍历非递归算法
void InOrderUnrec(Bitree *t)
{
    Stack s;
    StackInit(s);
    Bitree *p=t;

    while (p!=NULL || !StackEmpty(s))
    {
        while (p!=NULL)             //遍历左子树
        {
            push(s,p);
            p=p->lchild;
        }
        
        if (!StackEmpty(s))
        {
            p=pop(s);
            visite(p->data);        //访问根结点
            p=p->rchild;            //通过下一次循环实现右子树遍历
        }//endif   
    
    }//endwhile
}
3.后序遍历非递归算法
typedef enum{L,R} tagtype;
typedef struct 
{
    Bitree ptr;
    tagtype tag;
}stacknode;

typedef struct
{
    stacknode Elem[maxsize];
    int top;
}SqStack;

void PostOrderUnrec(Bitree t)
{
    SqStack s;
    stacknode x;
    StackInit(s);
    p=t;
    
    do 
    {
        while (p!=null)        //遍历左子树
        {
            x.ptr = p; 
            x.tag = L;         //标记为左子树
            push(s,x);
            p=p->lchild;
        }
    
        while (!StackEmpty(s) && s.Elem[s.top].tag==R)  
        {
            x = pop(s);
            p = x.ptr;
            visite(p->data);   //tag为R，表示右子树访问完毕，故访问根结点       
        }
        
        if (!StackEmpty(s))
        {
            s.Elem[s.top].tag =R;     //遍历右子树
            p=s.Elem[s.top].ptr->rchild;        
        }    
    }while (!StackEmpty(s));
}//PostOrderUnrec
前序最简洁算法
void PreOrderUnrec(Bitree *t)
{
   Bitree *p;
   Stack s;
   s.push(t);

   while (!s.IsEmpty())
   {
      s.pop(p);
      visit(p->data);
      if (p->rchild != NULL) s.push(p->rchild);
      if (p->lchild != NULL) s.push(p->lchild);
   }
}
后序算法之二
void BT_PostOrderNoRec(pTreeT root) 
{ 
stack<treeT *> s; 
pTreeT pre=NULL; 

while ((NULL != root) || !s.empty()) 
{ 
if (NULL != root) 
{ 
s.push(root); 
root = root->left; 
} 
else 
{ 
root = s.top(); 
if (root->right!=NULL && pre!=root->right){ 
root=root->right; 
} 
else{ 
root=pre=s.top(); 
visit(root); 
s.pop(); 
root=NULL; 
} 
} 
} 
}
先序遍历:
void PreOrder(BiTree root) //先序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针
{
if (root!=NULL)
{
Visit(root->data);//访问根结点
PreOrder(root->LChild); //先序遍历左子树
PreOrder(root->RChild);//先序遍历右子树
}
}

中序遍历:
void InOrder(BiTree root)//中序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针
{
上一个：C++编程问题~
下一个：跪求C++编程。
更多图片编程知识:
Fibnacci序列（递归方法）

Windows Sockets：带存档的套接字的工作方式

POJ 3461(模式匹配数&覆盖函数）

Muduo网络编程示例之八：用 Timing wheel 踢掉空闲连接

一个C++多继承带来的游戏开发陷阱

带姓名的成绩单