数据结构 树

数据结构-线索二叉树

线索二叉树

Posted by Hzy on November 22, 2019

1.今天学习了下线索二叉树:按照一定的规则遍历二叉树，用线索来代替空指针。

  • 线索二叉树是在二叉树的基础上增加了两个指针域，用来表示前驱节点和后继节点。
  • 好处:充分利用二叉树中的指针域，同时方便我们找到节点的前驱节点和后继节点。
  • 操作线索化后的二叉树就像操作双向链表一样，我们可以在这个基础上添加一个头结点，让尾部和头部串起来，这样就能构成一个环，从哪一边都能遍历！

1.1 前驱节点和后继节点

  • 前驱节点：有左孩子，指针则跟原来一样，没有左孩子，指针则指向上一个节点(preNode)。
  • 后继节点：有右孩子，指针的跟原来一样，没有右孩子，上一个的节点右孩子为当前节点。
  • 前驱节点有两种情况，我们用一个标签(ltag)来区分，0:当前节点有左孩子，1:当前节点没有左孩子
  • 后继节点有两种情况，我们用一个标签(rtag)来去分,，0:当前节点有右孩子，1:当前节点没有右孩子

我一开始不太理解，什么是前驱节点和后继节点，多看几次就懂啦。

2.1 先序遍历 二叉树线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 先序遍历 二叉树线索化
    def PreBinarySearchTree(self,tree=None):
        if tree:
            if not tree.left:
                tree.left  = self.preNode
                tree.ltag = 1
            if self.preNode!=None and not  self.preNode.right:
                self.preNode.right = tree
                self.preNode.rtag = 1
            print("上一个节点:", self.preNode.data if self.preNode else 'none', "当前节点:", tree.data)
            self.preNode = tree
            if tree.ltag ==0:
                self.PreBinarySearchTree(tree.left)
            if tree.rtag==0:
                self.PreBinarySearchTree(tree.right)

2.2 中序遍历 二叉树线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 中序遍历 二叉树线索化
    def MiddleBinarySearchTree(self,tree=None):
        if tree:
            self.MiddleBinarySearchTree(tree.left)
            if not tree.left:
                tree.ltag = 1  # 标记
                tree.left = self.preNode  # 当前节点的左孩子为上一个节点
            if self.preNode != None and not self.preNode.right:
                self.preNode.rtag = 1  # 标记
                self.preNode.right = tree  # 上一个节点的右孩子为当前节点
            print("上一个节点:", self.preNode.data if self.preNode else 'none', "当前节点:", tree.data)
            self.preNode = tree  # 定义当前节点 为 下一次循环中的上一个节点
            self.MiddleBinarySearchTree(tree.right)
        return

2.3 后序遍历，二叉树线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 后序遍历，二叉树线索化
    def LastBinarySearchTree(self,tree=None):
        if tree:
            if tree.ltag==0:
                self.LastBinarySearchTree(tree.left)
            if tree.rtag==0:
                self.LastBinarySearchTree(tree.right)
            if not tree.left:
                tree.left = self.preNode
                tree.ltag =1
            if self.preNode!=None and  not self.preNode.right:
                self.preNode.right=tree
                self.preNode.rtag = 1
            print("上一个节点:", self.preNode.data if self.preNode else 'none', "当前节点:", tree.data)
            self.preNode = tree

3.1 线索二叉树的先序遍历

  • xxx
  • xxx 1 1 1 1 1
1
2
3
4
5
6
7
8
9
10
11
12

# 先序线索二叉树，遍历
    def printPreBinarySearchTree(self):
        tree = self.root  # 树的根节点
        while tree:  # 从最左边的孩子开始 循环
            print(tree.data)
            if tree.rtag == 1:  # 找到其后继节点，然后指针指向后继节点
                tree = tree.right
            else:  # 如果不是后继节点，是其右孩子
                if tree.left and tree.ltag!=1:
                    tree = tree.left
                else:
                    tree = tree.right

3.2 线索二叉树的中序遍历

  • 线索化后的二叉树，遍历时，不需要栈和递归
  • 我们只要先找到二叉树的最左边的节点
  • 从最左边的节点开始遍历，有后继节点则指向其后继节点
  • 没有后继节点，则指向其右子树中最左边的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 线索化二叉树遍历
    def printBinarySearchTree(self):
        tree = self.root # 树的根节点
        while tree.left: # 先找树的最左边的孩子
            tree = tree.left
        while tree: # 从最左边的孩子开始 循环
            print(tree.data)
            if tree.rtag ==1: #找到其后继节点，然后指针指向后继节点
                tree = tree.right
            else: # 如果不是后继节点，是其右孩子
                tree = tree.right # 则指针指向其右孩子
                if tree:
                    while tree.ltag == 0: # 循环当前右孩子树中的最左边的节点
                        tree = tree.left
FEATURED TAGS
Python 数据结构