二叉树和排序二叉树

灰太狼 2023-08-17 16:53 228阅读 0赞

## 二叉树 ##

> 相关名词
> 
> 根节点
> 
> 左叶子节点
> 
> 右叶子节点
> 
> 子树
> 
> 高度

> 二叉树的排序方式：
> 
> 　　- 广度遍历（层级遍历）
> 
> 　　- 深度遍历
> 
> 　　　　- 前序（根左右）：在前序遍历中，我们首先访问根节点，然后递归地做左侧子树的前序遍历，随后是右侧子树的递归前序遍历。
> 
> 　　　　- 中序（左根右）：在一个中序遍历中，我们递归地对左子树进行一次遍历，访问根节点，最后递归遍历右子树。
> 
> 　　　　- 后序（左右根）：在后序遍历中，我们递归地对左子树和右子树进行后序遍历，然后访问根节点。

class Node():
        # 初始化节点
        def __init__(self, item):
            self.item = item
            self.left = None
            self.right = None
    
    
    class Tree():
        # 建一个空树
        def __init__(self):
            self.root = None
    
        # 增加节点
        def addNode(self, item):
            node = Node(item)
            # 如果树为空
            if self.root == None:
                self.root = node
                return
            # 如果树不为空
            cur = self.root
            # q遵循队列先进先出，这里使用列表，默认有个根节点
            q = [cur]
    
            # 这里死循环也可以
            while q:
                # 取出第一个位置的节点进行子节点的判断
                n = q.pop(0)
    
                # 分别判断左右节点是否为空，为空则新增节点，不为空加入到q列表中做循环。
                if n.left == None:
                    n.left = node
                    break
                else:
                    q.append(n.left)
    
                if n.right == None:
                    n.right = node
                    break
                else:
                    q.append(n.right)
    
        # 遍历树
        def travel(self):
            cur = self.root
            q = [cur]
    
            while q:
                n = q.pop(0)
                print(n.item)
                if n.left != None:
                    q.append(n.left)
                if n.right != None:
                    q.append(n.right)
    
        # 前序
        def fontTravel(self, root):
            # 根左右
            if root == None:
                return
            print(root.item)
            self.fontTravel(root.left)
            self.fontTravel(root.right)
    
        # 中序
        def midTravel(self, root):
            # 左根右
            # 递归的结束条件
            if root == None:
                return
            self.midTravel(root.left)
            print(root.item)
            self.midTravel(root.right)
    
        # 后序
        def afterTravel(self, root):
            # 左右根
            # 递归的结束条件
            if root == None:
                return
            self.afterTravel(root.left)
            self.afterTravel(root.right)
            print(root.item)
    
    
    
    tree = Tree()
    tree.addNode(1)
    tree.addNode(2)
    tree.addNode(3)
    tree.addNode(4)
    tree.addNode(5)
    # tree.travel()
    # tree.fontTravel(tree.root)
    # tree.midTravel(tree.root)
    tree.afterTravel(tree.root)

## 排序二叉树 ##

> 排序二叉树，基于中序，经过测试，中序顺序是正确的
> 
> 插入节点的准则：首先插入根节点。当插入其他节点的时候，需要和根节点做比较，比根节点小的节点插入树的左侧，大的插入树的右侧

class Node():
        # 初始化节点
        def __init__(self, item):
            self.item = item
            self.left = None
            self.right = None
    
    
    class sortTree():
    
        def __init__(self):
            self.root = None
    
        def midTravel(self, root):
            # 左根右
            # 递归的结束条件
            if root == None:
                return
            self.midTravel(root.left)
            print(root.item)
            self.midTravel(root.right)
    
        def insertNode(self, item):
            node = Node(item)
            cur = self.root
            # 树为空
            if self.root == None:
                self.root = node
                return
            # 树不为空
            while True:
                # 当节点参数小于根节点参数，放在左边节点位置
                if cur.item > node.item:
                    # 如果左节点为空，则增加到该节点位置
                    if cur.left == None:
                        cur.left = node
                        break
                    # 否则当做根节点继续循环
                    else:
                        cur = cur.left
                else:
                    if cur.right == None:
                        cur.right = node
                        break
                    else:
                        cur = cur.right
    
    
    tree = sortTree()
    tree.insertNode(8)
    tree.insertNode(6)
    tree.insertNode(5)
    tree.insertNode(3)
    tree.insertNode(2)
    tree.midTravel(tree.root)

转载于:https://www.cnblogs.com/biao-wu/articles/11366630.html