标签: binary-tree

简而言之,我想学习/开发一种优雅的方法来将二叉树保存到磁盘(一般树,不一定是BST).这是我的问题的描述:

我正在实施一个"20个问题"的游戏.我写了一个二叉树,其内部节点是问题,叶子是答案.如果有人对你当前的问题回答"是",那么节点的左子节点就是你要遵循的路径,而正确的孩子则是"否"的答案.请注意,这不是二叉搜索树,只是一个二叉树,其左子节点为"是",右侧为"否".

如果通过要求用户将她的答案与计算机所考虑的答案区分开来,该程序遇到一个空的叶子,该程序会向树中添加一个节点.

这很简洁,因为树会在用户播放时自行构建.什么不整洁是我没有一个很好的方法将树保存到磁盘.

我已经考虑过将树保存为数组表示(对于节点i,左边的子节点是2i + 1,右边是2i + 2,父节点是(i-1)/ 2),但它不干净,我最终得到了浪费了很多空间.

有关将稀疏二叉树保存到磁盘的优雅解决方案的任何想法？

如果仅给出后序列表,我怎样才能找到树的预订列表,反之亦然.此外,在树中,每个非叶节点都有两个子节点(即每个节点有两个或零个子节点.)

编辑:另一个给定的假设是每个节点的标签是唯一的,并且有一个字段,将其标识为内部节点或叶子.我认为应该摆脱单个预订单或后序的模糊性能够唯一地识别树.

通过一些练习来磨练我的二叉树技能,我决定实现一个splay树,如维基百科:Splay树中所述.

我没有得到的一件事是关于插入的部分.

它说:

首先,我们在splay树中搜索x.如果x尚不存在,那么我们将找不到它,而是它的父节点y.其次,我们对y执行一个splay操作,它将y移动到splay树的根.第三,我们以适当的方式将新节点x作为root插入.以这种方式,y是新根x的左或右子.

我的问题是:与文章中的其他例子相比,上述文字似乎过于简洁,为什么会这样？似乎这里遗漏了一些问题.例如,在将y节点向上扩展到根之后,我不能盲目地用x替换root,并将x作为左或右子进行处理.

我们假设树中不存在该值.

我有这棵树:

           10
          /  \
         5    15
        / \    \
       1   6    20

我想插入8.通过上面的描述,我将找到6节点,并且在普通的二叉树中,8将被添加为6节点的右子节点,但是在这里我首先必须展开6节点到root:

            6
           / \
          5   10
         /     \
        1       15
                 \
                  20

那么这两个中的任何一个都是明显错误的:

          8                                  8
           \                                /
            6                              6
           / \                            / \
          5   10                         5   10
         /     \                        /     \
        1       15                     1       15
                 \                              \
                  20                             20

    6 is not greater than 8          10 is not less than 8

在我看来,首先进行splaying,然后以root身份正确添加新值的唯一方法意味着我必须检查以下条件(将splayed节点添加为新root的左子节点):

1. 显示到根的节点小于新根节点(6 <8)
2. 我向根发布的节点中最右边的子节点也小于新根节点(20 8)

但是,如果我要拆分我显示的节点,通过选择正确的子节点并将其作为新节点的右子节点附加,我会得到:

                        8
                       / \ …

当我有一个包含100个元素的数组列表时,如何制作BST {3,2,6,7,...,99}？

我正在阅读一本关于数据结构的书,它说左侧平衡二叉树是一棵树,其中叶子只占据最后一级的最左边位置.

这对我来说似乎有点模糊.这是否意味着叶子只在根的左侧,并且分布在整个水平,或者只留在整个树的左侧.究竟什么构成左平衡？

我不确定我的猜测是否涵盖了任何答案,所以如果有人可以提供帮助,我们将非常感激:-).

我正在阅读二叉树教程.
而且我在使用递归函数方面略有困难.比方说,我需要计算树中的节点数

int countNodes( TreeNode *root )    
{   
       // Count the nodes in the binary tree to which  
       // root points, and return the answer.  
    if ( root == NULL )  
       return 0;  // The tree is empty.  It contains no nodes.  
    else
   {  
       int count = 1;   // Start by counting the root.  
       count += countNodes(root->left);  // Add the number of nodes   
                                        //     in the left subtree.   
       count += countNodes(root->right); // Add the number of nodes   
                                        //    in the …

我需要计算二叉树中的节点总数.当我执行此代码时,问题就出现了,它为节点总数提供了垃圾值.我的程序输出就像993814.应该是7.

如何解决这个问题？

#include<stdlib.h>
#include<stdio.h>

struct binarytree
{
    int data;
    struct binarytree * right, * left;
};

typedef struct binarytree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left); …

我有这个代码:

node* free_tree(node *root){

  if(root != NULL){

    free_tree(root->left);
    free_tree(root->right);

    free(root->name);
    free(root);
  }
  return NULL;
}

我知道这不正确,正确的版本是:

root -> left = free_tree(root->left);
root -> right = free_tree(root->right);

我不明白的是,为什么这有效？当我从free_tree(root->left)NULL 返回 时,我的函数需要一些 node*接收NULL值,这不是这里的情况,所以我不明白,为什么这个工作？为什么这不是编译错误？

我的朋友在接受采访时被问到这个问题:

生成一个有限但任意大的二叉树O(1).该方法generate()应返回一个二进制树,其大小无限但有限.

在采访之后我们都对它进行了很长时间的考虑,但我们最多只能提出O(n)解决方案.

我们将如何产生O(1)？它甚至可能吗？还有更多的东西吗？

在"对Haskell的温和介绍"中,我们有Tree类型的声明:

data Tree a = Leaf a | Branch (Tree a) (Tree a)
     deriving (Eq,Ord,Show,Read)

让我们来做一些这种类型的值:

a1 = Leaf 1
a2 = Leaf 2
a3 = Leaf 3
a4 = a1 `Branch` a2
a5 = a2 `Branch` a3
a6 = a4 `Branch` a5

在ghci:

*Main> :t a6
a6 :: Tree Integer

但a6根本不是树,请参阅:

      a6
     / \
   a4   a5
  / \  /  \
a1   a2    a3

这个图表中有一个循环!怎么了？树的类型定义是否正确？或许,我不能在理解这个例子时遇到一些错误......