二叉树

二叉树实现(Python)

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.lchild = None
        self.rchild = None

class BinTree:
    def __init__(self):
        self.root = None

    def is_empty(self):
        return self.root == None

    def add(self,val):
        node = TreeNode(val)
        if self.root == None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur = queue.pop(0)
            if cur.lchild == None:
                cur.lchild = node
                return
            if cur.rchild == None:
                cur.rchild = node
                return
            queue.append(cur.lchild)
            queue.append(cur.rchild)
        return

    def preorder(self,root):
        if root == None:
            return
        print(root.val,end=',')
        self.preorder(root.lchild)
        self.preorder(root.rchild)
        return

    def inorder(self,root):
        if root == None:
            return
        self.inorder(root.lchild)
        print(root.val,end=',')
        self.inorder(root.rchild)
        return

    def postorder(self,root):
        if root == None:
            return
        self.postorder(root.lchild)
        self.postorder(root.rchild)
        print(root.val,end=',')
        return

    def breath_travel(self,root):
        if root == None:
            return
        queue = [root]
        while queue:
            cur = queue.pop(0)
            print(cur.val,end=',')
            if cur.lchild != None:
                queue.append(cur.lchild)
            if cur.rchild != None:
                queue.append(cur.rchild)

    def leaf(self,root):
        if root == None: return
        if (root.lchild == None) and (root.rchild == None):
            print(root.val,end=',')
        self.leaf(root.lchild)
        self.leaf(root.rchild)
        return

    def maxheight(self,root):
        if root == None: return 0
        L = self.maxheight(root.lchild) + 1
        R = self.maxheight(root.rchild) + 1
        if L > R:
            return L
        else:
            return R


b = BinTree()
for i in range(10):
    b.add(i)

print('\n前序遍历')
b.preorder(b.root)
print('\n中序遍历')
b.inorder(b.root)
print('\n后序遍历')
b.postorder(b.root)
print('\n层次遍历')
b.breath_travel(b.root)
print('\n 叶子')
b.leaf(b.root)
print('\n最大深度')
print(b.maxheight(b.root))