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

问题描述

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

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

时间： 2024-04-26 13:55:25

从叶子节点到根节点的全路径的相关文章

计算某节点离根节点的距离

问题描述 计算某节点离根节点的距离即从根节点数起位于第几层 解决方案 递归下去,如该节点为根节点则返回1,否则,该节点的层数 = 该节点的父节点层数 + 1解决方案二:你解析或者循环的时候 那个变量 记录下 就OK 嘛!

easyui中combotree循环获取父节点至根节点并输出路径实现方法_jquery

前台页面: <pre name="code" class="html"><td style="height: 35px" colspan="7"> <input id="fm_AEType" class="easyui-combotree" style="width: 240px" /> <label id="fm_

oracleCONNECTBYPRIOR叶子节点查找根节点

  SELECT TRANS_ID FROM TRANS_INST WHERE connect_by_isleaf=1 START WITH TRANS_ID =480242 CONNECT BY PRIOR UP_TRANS_ID = TRANS_ID; 说明: 表TRANS_INST(TRANS_ID,UP_TRANS_ID) 480242表示树的任何一个节点 TRANS_ID子节点 UP_TRANS_ID父节点

ASP 递归调用 已知节点查找根节点的函数_应用技巧

复制代码 代码如下: Function getTreeRootId(pNodeId) getSQL = "select note_id,parent_id from [T_tree_demo] where note_id='"& pNodeId &"'" Set getRs = db.Execute(getSQL) If Not getRs.eof Then If Trim(getRs("parent_id")) = "

ASP 递归调用 已知节点查找根节点的函数

复制代码 代码如下: Function getTreeRootId(pNodeId) getSQL = "select note_id,parent_id from [T_tree_demo] where note_id='"& pNodeId &"'" Set getRs = db.Execute(getSQL) If Not getRs.eof Then If Trim(getRs("parent_id")) = "

数据结构例程——从根节点到每个叶子节点的路径之逆

本文是数据结构基础系列(6):树和二叉树中第11课时二叉树遍历非递归算法和第12课时层次遍历算法的例程. 问题:设计算法输出从根节点到每个叶子节点的路径之逆. 解法1:利用二叉树后序遍历非递归算法中,每一个叶子节点出现时,栈中从栈顶到栈底,正好是叶子节点到根节点的逆序的性质编写. ［参考解答］(btreee.h见算法库) #include <stdio.h> #include "btree.h" void AllPath1(BTNode *b) { BTNode *St[M

TreeViewer如何获取根节点名称

问题描述 TreeViewer控件下选择一个节点时,如何获取其根节点的名称啊? 解决方案 解决方案二:该回复于2010-07-21 14:59:47被版主删除解决方案三:我也正在寻求答案解决方案四:节点对象没有获取父节点的方法吗?解决方案五:引用3楼qunhao的回复: 节点对象没有获取父节点的方法吗? 获取父节点的方法比较简单,节点本身就有这样的属性.楼主的问题已经解决,当前节点的根节点,可以通过获取当前节点的全部路径来获取--节点本身具有获取当前全部路径的属性.PrivateFunction

设置-ext js tree 根节点选中不了与只显示根节点和二级节点

问题描述 ext js tree 根节点选中不了与只显示根节点和二级节点 最近在做一个项目,需要在一个分组树中,选中根节点.但是这边一直设置选中不了.哪位能帮帮忙呢,指导指导. 解决方案 参考http://dev.sencha.com/deploy/ext-4.1.0-gpl/examples/tree/check-tree.html

extjs grid 中读取树状映射的根节点如何处理？

问题描述 hibernate中的一个树状映射是一个与自身相关联的表,但是根节点的parent是null,这样通过jason转换处理的parent就为null,但该行是在ext的grid的column中做了映射的,那么读取该行该如何处理?