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

Question

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$
  最后一行是测试数据