如何验证二叉树？

Question

我一直在围绕二叉树和二叉源树进行一些挖掘。运行进入这个非常基本的树 (BT) 问题，并挑战要证明的二叉树的属性。

问题：给定一个节点（根），检查这是否是一个有效的二叉树。不要求验证给定的 BT 是否是 BST，而只是要求检查下面是否是 BT。

Valid:
  X1
 /  \
X4   X5
 \    \
  X3   X7

Invalid:
  X1
 /  \
X4   X5
 \  /  \
  X3   X7


# A Python class that represents an individual node in a BT
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key 

    def isNotBinaryTree(root):
        # code here

if isNotBinaryTree(root):
   print "True"
else: 
   print "False"

我知道这不是一棵二叉树（事实上，根据其定义和属性，这甚至都不是一棵树）。事情是......我如何证明或验证这一点？或者我如何验证这不是 x4 和 x5 -> x3（多个父节点（节点）指向同一个子节点）的 BT？***未提供数据！如果我是，algorithm/logic 会是什么样子解决这个问题？（Python x.x 首选）

Answer 1

鉴于您的数据结构，获取一个节点并递归地查看是否存在具有简单函数的循环应该非常容易，例如：

def hasCycle(node, seen = set()):
    if node in seen: return True
    seen.add(node)
    if node.left and hasCycle(node.left, seen): 
        return True
    if node.right and hasCycle(node.right, seen): 
        return True
    return False

这只是进行深度优先搜索并保留一组已访问的节点。如果你看到一个节点两次，那就是一个循环。

Answer 2

按照下面的 link 获得关于 BT/BST 的更深入的描述： https://en.wikipedia.org/wiki/Tree_traversal

def nodes_visited(root, key):
    if root.next:
        if root.next in key: 
            return True
        key.append(root)
        return nodes_visited(root.next, key)
    return False

def has_cycle(head):
    return nodes_visited(root=head, key=[])

如何验证二叉树？

How to validate a Binary Tree?

tree

binary-tree

binary-search-tree

binary-search

b-tree