2 u010109298 u010109298 于 2014.06.02 16:08 提问

从叶子节点到根节点的全路径

void Path(treeNode* root){//叶节点到根节点的路径
if(root->left==NULL&&root->right==NULL)
{printf("%d ",root->val.opnd);printf("\n");return ;}
else if(root->left!=NULL&&root->right!=NULL)
{
printf("%c ",root->val.optr);
Path(root->left);
Path(root->right);
}
}

全部代码如下,可以跑的
#include
#include
#include
#include
#include
using namespace std;

typedef struct nodeTag{ /* 表达式二叉树结点类型 */
union{
int opnd;
char optr;
}val;
struct nodeTag *left;
struct nodeTag *right;
}treeNode;

typedef struct pTag{ /* 优先表结点类型 /
char op;
int f;
int g;
}Prior;
struct node{/
队列节点*/
treeNode T;
struct node
next;
};
//全局变量
Prior pList[] = { /* 优先表 /
'+', 2, 1,
'-', 2, 1,
'
', 4, 3,
'/', 4, 3,
'^', 4, 5,
'(', 0, 5,
')', 6, 0,
'$', 0, 0
};
stack OptrStack; /* 操作符栈 /
stack<treeNode
> ExprStack; /* 表达式栈 /
const int NUM = 256;
const int OPTR = 257;
int tokenval; /
下一输入值 */

/**************************************************************************

  • descr :比较栈顶运算符与下一输入运算符优先关系
  • param :top 栈顶运算符
  • param :ch 下一输入运算符
  • return :关系'>', '=', '<' **************************************************************************/ char Precede(char top, char ch) { int op1=-1,op2=-1; for (int i=0; i < 8; i++) { if (pList[i].op == top) op1 = pList[i].f; if (pList[i].op == ch) op2 = pList[i].g; } if (op1 == -1 || op2 == -1) { cout<<"operator error!"< op2) return '>'; else if (op1 == op2) return '='; else return '<'; }

/**************************************************************************

  • descr :
  • return : **************************************************************************/ int lexan() { int t; while(1) { t = getchar(); if (t == ' ' || t == '/t' || t == '/n') ; //去掉空白字符 else if (isdigit(t)) { ungetc(t, stdin);//把一个字符退回到输入流中 cin>>tokenval; return NUM; } else { return t; } } } /**************************************************************************
  • descr : 建立二叉树数结点(叶结点)
  • param : num 操作数
  • return : 二叉树叶结点指针 treeNode* **************************************************************************/ treeNode* mkleaf(int num) { treeNode *tmpTreeNode = new treeNode; if (tmpTreeNode == NULL) { cout<<"Memory allot failed!"<left = NULL; tmpTreeNode->right = NULL; tmpTreeNode->val.opnd = num; return tmpTreeNode; }

/**************************************************************************

  • descr : 建立二叉树运算符结点(内结点)
  • param : op运算符
  • param : left左子树指针
  • param : right右子树指针
  • return : 二叉树内结点指针 treeNode* **************************************************************************/ treeNode* mknode(char op, treeNode* left,treeNode* right) { treeNode *tmpTreeNode = new treeNode; if (tmpTreeNode == NULL) { cout<<"Memory allot failed!"<left = left; tmpTreeNode->right = right; tmpTreeNode->val.optr = op; return tmpTreeNode; }

treeNode* CreateBinaryTree()
{
int lookahead;
char op;
treeNode opnd1, *opnd2;
OptrStack.push('$');
lookahead = lexan();
while ( lookahead != '$' || OptrStack.top() != '$')
{
if (lookahead == NUM )
{
ExprStack.push( mkleaf(tokenval));
lookahead = lexan();
}
else
{
switch (Precede(OptrStack.top(), lookahead))
{
case '<':
OptrStack.push(lookahead);
lookahead = lexan();
break;
case '=':
OptrStack.pop();
lookahead = lexan();
break;
case '>':
opnd2 =ExprStack.top();ExprStack.pop();
opnd1 =ExprStack.top();ExprStack.pop();
op =OptrStack.top();OptrStack.pop();
ExprStack.push(mknode(op,opnd1,opnd2));
break;
}
}
}
return ExprStack.top();
}///////////////////////////////////////////////////////////////////////
void EnQueue(struct node *&head,treeNode *node){//////////////////入队
struct node *p=head,*p1=NULL;
p1=(struct node
)malloc(sizeof(struct node));
p1->T=node;
if(p==NULL)
{head=p1;p1->next=NULL;}
else
{
while(p->next)
p=p->next;
p->next=p1;
p1->next=NULL;
}
}
void DeQueue(struct node &head,treeNode *&node){////////////////出队
if(head==NULL)
printf("队空\n");
else {
node=head->T;
head=head->next;
}
}
bool QueueEmpty(struct node
head){
if(head==NULL) return true;
return false;
}
//////////////////////////////////////////////////////////////////////////
/**************************************************************************

  • descr : 输出前缀表达式
  • param :
  • return : **************************************************************************/ int PreOrderTraverse(treeNode* T) { if ( T == NULL) return 1; if(T->left != NULL) { cout<val.optr<<" "; if (PreOrderTraverse(T->left)) if (PreOrderTraverse(T->right)) return 1; return 0; } else { cout<val.opnd<<" "; return 1; } }

/**************************************************************************

  • descr : 输出后缀表达式
  • param :
  • return :
    **************************************************************************/
    int FollowOrderTraverse(treeNode* T)
    {
    if ( T == NULL)
    return 1;
    if ( T->left !=NULL)
    {
    if (FollowOrderTraverse(T->left))
    if (FollowOrderTraverse(T->right))
    {
    cout<val.optr<<" ";
    return 1;
    }
    return 0;

    }
    else
    {
    cout<val.opnd<<" ";
    return 1;
    }
    }
    void Leaf(treeNode* root)//先序遍历输出二叉树的叶子节点//
    {
    if(root!=NULL)
    {
    if(root->left==NULL&&root->right==NULL)
    printf("%d ",root->val.opnd);
    Leaf(root->left);
    Leaf(root->right);
    }
    }
    void Leaf_(treeNode* root)//非递归层次遍历输出叶节点
    {
    struct node Q=NULL;
    treeNode *p=root;
    EnQueue(Q,p);
    while(!QueueEmpty(Q)){
    DeQueue(Q,p); if(p->val.opnd>=0&&p->val.opnd<=9) printf("%d ",p->val.opnd);
    if(p->left!=NULL) EnQueue(Q,p->left);
    if(p->right!=NULL) EnQueue(Q,p->right);
    }
    }
    void Path(treeNode
    root){//叶节点到根节点的路径
    if(root->left==NULL&&root->right==NULL)
    {printf("%d ",root->val.opnd);printf("\n");return ;}
    else if(root->left!=NULL&&root->right!=NULL)
    {
    printf("%c ",root->val.optr);
    Path(root->left);
    Path(root->right);
    }
    }
    // 主程序
    void main()
    {

    treeNode ExprTree;
    ExprTree = CreateBinaryTree();
    cout<<"前缀:";
    PreOrderTraverse(ExprTree);
    cout<<endl;
    cout<<"后缀:";
    FollowOrderTraverse(ExprTree);
    cout<<endl;
    cout<<"先序递归输出叶子节点:";
    Leaf(ExprTree);
    cout<<"\n";
    cout<<"层次非递归输出叶子节点:";
    Leaf_(ExprTree);
    cout<<"\n";
    cout<<"从叶节点到根节点的路径:"<<"\n";
    Path(ExprTree);
    }
    //1+2
    (3-1)+5/2$
    最后一行是测试数据

Csdn user default icon
上传中...
上传图片
插入图片