1. #! /usr/bin/env python
    2. #coding:utf-8
    4. class Node:
    5.     """
    6.     二叉树左右枝
    7.     """
    8.     def __init__(self, data):
    9.         """
    10.         节点结构
    12.         """
    13.         self.left = None
    14.         self.right = None
    15.         self.data = data
    17.     def insert(self, data):
    18.         """
    19.         插入节点数据
    20.         """
    21.         if data < self.data:
    22.             if self.left is None:
    23.                 self.left = Node(data)
    24.             else:
    25.                 self.left.insert(data)
    26.         elif data > self.data:
    27.             if self.right is None:
    28.                 self.right = Node(data)
    29.             else:
    30.                 self.right.insert(data)
    32.     def lookup(self, data, parent=None):
    33.         """
    34.         遍历二叉树
    35.         """
    36.         if data < self.data:
    37.             if self.left is None:
    38.                 return None, None
    39.             return self.left.lookup(data, self)
    40.         elif data > self.data:
    41.             if self.right is None:
    42.                 return None, None
    43.             return self.right.lookup(data, self)
    44.         else:
    45.             return self, parent
    47.     def delete(self, data):
    48.         """
    49.         删除节点
    50.         """
    51.         node, parent = self.lookup(data)        #已有节点
    52.         if node is not None:
    53.             children_count = node.children_count()      #判断子节点数
    54.             if children_count == 0:
    55.                 # 如果该节点下没有子节点，即可删除
    56.                 if parent.left is node:
    57.                     parent.left = None
    58.                 else:
    59.                     parent.right = None
    60.                 del node
    61.             elif children_count == 1:
    62.                 # 如果有一个子节点，则让子节点上移替换该节点（该节点消失)
    63.                 if node.left:
    64.                     n = node.left
    65.                 else:
    66.                     n = node.right
    67.                 if parent:
    68.                     if parent.left is node:
    69.                         parent.left = n
    70.                     else:
    71.                         parent.right = n
    72.                 del node
    73.             else:
    74.                 # 如果有两个子节点，则要判断节点下所有叶子
    75.                 parent = node
    76.                 successor = node.right
    77.                 while successor.left:
    78.                     parent = successor
    79.                     successor = successor.left
    80.                 node.data = successor.data
    81.                 if parent.left == successor:
    82.                     parent.left = successor.right
    83.                 else:
    84.                     parent.right = successor.right
    86.     def compare_trees(self, node):
    87.         """
    88.         比较两棵树
    89.         """
    90.         if node is None:
    91.             return False
    92.         if self.data != node.data:
    93.             return False
    94.         res = True
    95.         if self.left is None:
    96.             if node.left:
    97.                 return False
    98.         else:
    99.             res = self.left.compare_trees(node.left)
    100.         if res is False:
    101.             return False
    102.         if self.right is None:
    103.             if node.right:
    104.                 return False
    105.         else:
    106.             res = self.right.compare_trees(node.right)
    107.         return res
    109.     def print_tree(self):
    110.         """
    111.         按顺序打印数的内容
    112.         """
    113.         if self.left:
    114.             self.left.print_tree()
    115.         print self.data,
    116.         if self.right:
    117.             self.right.print_tree()
    119.     def tree_data(self):
    120.         """
    121.         二叉树数据结构
    122.         """
    123.         stack = []
    124.         node = self
    125.         while stack or node: 
    126.             if node:
    127.                 stack.append(node)
    128.                 node = node.left
    129.             else: 
    130.                 node = stack.pop()
    131.                 yield node.data
    132.                 node = node.right
    134.     def children_count(self):
    135.         """
    136.         子节点个数
    137.         """
    138.         cnt = 0
    139.         if self.left:
    140.             cnt += 1
    141.         if self.right:
    142.             cnt += 1
    143.         return cnt