二叉树及排序二叉树

二叉树

• 根节点
• 左叶子节点
• 右叶子节点
• 子树
• 高度

二叉树的遍历

• 广度遍历：逐层遍历
• 深度遍历
  • 前序：根左右
  • 中序：左根右
  • 后序：左右根

#封装一个节点对象
class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None


class Tree():
    def __init__(self):#构造出一颗空的二叉树
        self.root = None #root指向第一个节点的地址，如果root指向了None，则意味着该二叉树为空
    #向二叉树中插入节点
    def addNode(self,item):
        node = Node(item)
        if self.root == None:
            #addNode如果第一次被调用则意味着：向空树中插入第一个节点，该节点一定是该树的根节点
            self.root = node
            return
        #如果上面的if不执行则树为非空，下面就执行向一个非空的树中插入节点的操作
        cur = self.root
        queue = [cur]
        while queue:
            n = queue.pop(0)
            if n.left != None:
                queue.append(n.left)
            else:
                n.left = node
                break
            if n.right != None:
                queue.append(n.right)
            else:
                n.right = node
                break
    def travel(self):
        #如果是为空则
        if self.root == None:
            print('空！')
            return
        #树为非空
        cur = self.root
        queue = [cur]
        while queue:
            n = queue.pop(0)
            print(n.item)
            if n.left != None:
                queue.append(n.left)
            if n.right != None:
                queue.append(n.right)
            
    def forward(self,root):
        if root == None:
            return
        print(root.item)
        self.forward(root.left)
        self.forward(root.right)
        
    def middle(self,root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
    def back(self,root):
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)




tree = Tree()
tree.addNode(1)
tree.addNode(2)
tree.addNode(3)
tree.addNode(4)
tree.addNode(5)
tree.addNode(6)
tree.addNode(7)
# tree.travel()
# tree.forward(tree.root)
# tree.middle(tree.root)
tree.back(tree.root)
#前序：1，2，4，5，3，6，7
#中序：4，2，5，1，6，3，7
#后续：4，5，2，6，7，3，1

排序二叉树¶

• 插入节点的时候一定要遵从：比根节点小的节点同一插入在树的左侧，比根节点大的节点同一插在数据的右侧

class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None


class SortTree():
    def __init__(self):
        self.root = None
        
    def insertNode(self,item):
        node = Node(item)
        #向空树中插入第一个节点的情况
        if self.root == None:
            self.root = node
            return
        #树为非空的情况
        cur = self.root
        
        while True:
            if node.item > cur.item:#往右插
                if cur.right == None:
                    cur.right = node
                    break

                else:
                    cur = cur.right
            else:#往左插
                if cur.left == None:
                    cur.left = node
                    break
                else:
                    cur = cur.left
             
    def forward(self,root):
        if root == None:
            return
        print(root.item)
        self.forward(root.left)
        self.forward(root.right)
        
    def middle(self,root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
    def back(self,root):
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)


tree = SortTree()
tree.insertNode(3)
tree.insertNode(8)
tree.insertNode(5)
tree.insertNode(7)
tree.insertNode(6)
tree.insertNode(2)

tree.middle(tree.root)