标签: binary-tree

我正在尝试遍历C中的二叉树.我的树包含一个AST节点(编译器的抽象语法树节点).ASTnode保留nodetype,它指定给定节点的类型(即INT OP或CHAR和TYPE,我们不需要关注其他类型),其他成员是左右指针,最后我们存储.

这是遍历的代码:

    void traverse(struct ASTNode *root)
    {
        if(root->nodeType == OP){
            printf("OP \n");
            if(root->left != NULL){
              printf("left - ");
              traverse(root->left);
            }
            if(root->right != NULL){
              printf("right - ");
              traverse(root->right);
            }
            return;
        }
        else{
            if(root != NULL && root->nodeType == INT)
            {
              printf("INT - ");
              printf("INT: %d\n",root->value);
            }
            if(root != NULL && root->nodeType == CHAR)
            {
              printf("CHAR - ");
              printf("CHAR: %c\n",root->chValue);
            }
            return;
        }
    }

此外,我们不能将左值或右值分配给CONSTANT节点,因为在AST中,常量值不包含任何额外值.

更新:

问题出在我的主要电话中:

    int main()
    {
        struct ASTNode *node1 = makeCharNode('a');
        struct ASTNode *node2 = makeCharNode('b');
        struct …

我多次访问二叉树的最小元素.什么实现允许我在恒定时间内访问最小元素,而不是O(log n)？

准备考试.这不是功课问题.

我认为最坏的情况是O(N ^ 2)来构建BST.(每次插入req N-1比较,你总和所有的比较0 + 1 + ... + N-1~N ^ 2).这是倾斜的BST的情况.

(平衡)BST的插入是O(log N),那么为什么最好的情况是O(N logN)来构造树？

我猜最好的猜测 - 因为单个插入是log N,而不是总结所有插入以某种方式给我们N log.

谢谢 !

我理解树遍历和实现背后的想法,但这是问题.为什么我们都需要它们？

现在我只知道在解析数学表达式时使用了前序遍历.从维基百科我也读到:

• 序遍历是特别常见使用一个序遍历上的二叉搜索树,因为这将从底层集合,以根据该设置的二叉查找树(因此得名)比较返回值,.预订遍历
• 在将值插入新树时预先遍历树是制作二叉搜索树的完整副本的常用方法.也可以使用preorder遍历从表达式树中获取前缀表达式(波兰表示法):预先遍历表达式树.(我已经说过了)

但这些例子相当含糊.任何人都可以更深入地描述这一点.特别是举例.

就C编程而言,我几乎都是一个菜鸟.

尝试了几天从表单的表达式创建二叉树:

A(B,C(D,$))

每个字母都是节点.

'(' 在我的树下(向右)下降.

',' 去我树的左侧分支

'$' 插入一个NULL节点.

')' 意味着上升到一个水平.

这是我在编码2-3天后想出来的:

#define SUCCESS 0

typedef struct BinaryTree
{
char info;
BinaryTree *left,*right,*father;
}BinaryTree;



int create(BinaryTree*nodeBT, const char *expression)
{   
    nodeBT *aux;
    nodeBT *root;
    nodeBT *parent;
    nodeBT=(BinaryTree*) malloc (sizeof(BinaryTree));         
        nodeBT->info=*expression;
    nodeBT->right=nodeBT->left=NULL;
    nodeBT->father = NULL;

    ++expression;   
    parent=nodeBT;                                                 
    root=nodeBT;

    while (*expression)
        {if (isalpha (*expression))
            {aux=(BinaryTree*) malloc (sizeof(BinaryTree));
             aux->info=*expression;
             aux->dr=nodeBT->st=NULL;
             aux->father= parent;
             nodeBT=aux;}

        if (*expression== '(')
            {parent=nodeBT;
            nodeBT=nodeBT->dr;}

        if (*expression== ',')
            {nodeBT=nodeBT->father;
            nodeBT=nodeBT->dr;}

        if (*expression== ')')
            {nodeBT=nodeBT->father;
            parent= nodeBT->nodeBT;}

        if (*expression== '$') …

二叉搜索树的有序遍历会按递增顺序生成节点。但是在任何二叉树上进行预顺序和后顺序遍历有什么优势？

编辑：我的意思是优点：“任何适合应用前序或后序遍历的情况”。

如何使用级别顺序遍历序列构造二叉树,例如从序列{1,2,3,#,#,4,#,#,5},我们可以构造如下的二叉树:

     1
    / \
   2   3
      /
     4
      \
       5

其中'#'表示下面没有节点的路径终结符.

最后,我用c ++实现了Pham Trung的算法

struct TreeNode
{
    TreeNode *left;
    TreeNode *right;
    int val;

    TreeNode(int x): left(NULL), right(NULL), val(x) {}
};
TreeNode *build_tree(char nodes[], int n)
{
    TreeNode *root = new TreeNode(nodes[0] - '0'); 
    queue<TreeNode*> q;
    bool is_left = true;
    TreeNode *cur = NULL;
    q.push(root);

    for (int i = 1; i < n; i++) {
        TreeNode *node = NULL;
        if (nodes[i] != '#') {
            node = new TreeNode(nodes[i] - '0');
            q.push(node); …

我回到了我实现二叉树的旧C++学校作业之一.我有一个文件(Tree.cpp),其中包含插入,查找,删除等节点的功能.在顶部,我有"using namespace std;".我得到的警告是由另一个文件SymTab.hpp引起的,如下所示:

#ifndef SYMTAB_H
#define SYMTAB_H

#include <iostream>
#include "Tree.hpp"
using namespace std;

template <class Whatever>
class SymTab : private Tree<Whatever> {
public:
        Tree<Whatever> :: Insert;
        Tree<Whatever> :: Lookup;
        Tree<Whatever> :: Remove;
        Tree<Whatever> :: Write;
        Tree<Whatever> :: Set_Debug_On;
        Tree<Whatever> :: Set_Debug_Off;
};

#endif

每条线后public:都会发出警告:

"SymTab.hpp:11:9:警告:不推荐使用访问声明,而使用声明;建议:添加'using'关键字[-Wdeprecated] Tree :: Insert;",其中"Insert被每个相应的函数替换名称.

关于命名空间的任何建议以及如何摆脱这些警告？

我在二叉树中找到最后一个元素(最右边的孩子)时遇到了一些麻烦.

这是我到目前为止:

public Node findLastElement(Node root) {
  Node x = root;
  if (x != null)
      findLastElement(x.right);
  return x;
}

如果我打印元素,打印的最后一个元素是最后一个元素,但我似乎无法"获得"该元素.当我尝试在循环后返回x时,我得到一个nullpointer.如何保存最后一个元素并将其返回？

  data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
             deriving Show
  data RoseTree a = RoseNode a [RoseTree a]
     deriving Show
  binaryTreeToRose :: BinaryTree a -> RoseTree a
         binaryTreeToRose btree = case btree of
         Node Null a Null -> RoseNode a []
         Node left a Null -> RoseNode a [binaryTreeToRose left]
         Node Null a right -> RoseNode a [binaryTreeToRose right]
         Node left a right -> RoseNode a [binaryTreeToRose left]++[binaryTreeToRose right]

I try to write a function to …