Go-实现简单二叉树数据结构

叁歲伎倆 2022-09-09 09:26 114阅读 0赞

代码片段如下：

/*
     *                    .::::.
     *                  .::::::::.
     *                 :::::::::::
     *             ..:::::::::::'
     *           '::::::::::::'
     *             .::::::::::
     *        '::::::::::::::..
     *             ..::::::::::::.		Utils:二叉树
     *           ``::::::::::::::::		Author:崔金朋
     *            ::::``:::::::::'        .:::.
     *           ::::'   ':::::'       .::::::::.
     *         .::::'      ::::     .:::::::'::::.
     *        .:::'       :::::  .:::::::::' ':::::.
     *       .::'        :::::.:::::::::'      ':::::.
     *      .::'         ::::::::::::::'         ``::::.
     *  ...:::           ::::::::::::'              ``::.
     * ```` ':.          ':::::::::'                  ::::..
     *  		           '.:::::'          			':'````..
     */
    
    package main
    
    import (
    	"fmt"
    )
    
    type Tree struct {
    	Value     interface{}
    	LeftNode  *Tree
    	RightNode *Tree
    }
    
    // 打印节点的值
    func (t *Tree) PrintNodeValue() {
    	fmt.Printf("%d", t.Value)
    }
    
    // 设置节点的值
    func (t *Tree) SetNodeValue(val interface{}) {
    	t.Value = val
    }
    
    // 创建节点
    func CreateNodeValue(val interface{}) *Tree {
    	return &Tree{val, nil, nil}
    }
    
    // 查找节点，利用递归进行查找
    func (t *Tree) SearchNodeValue(node *Tree, val interface{}) *Tree {
    	if node == nil {
    		return nil
    	} else if node.Value == val {
    		return node
    	} else {
    		tree := node.SearchNodeValue(node.LeftNode, val)
    		if tree != nil {
    			return tree
    		}
    
    		return node.SearchNodeValue(node.RightNode, val)
    	}
    }
    
    // 树的高度
    func (t *Tree) GetTreeHigh(node *Tree) int {
    	if node == nil {
    		return 0
    	} else {
    		leftHigh := node.GetTreeHigh(node.LeftNode)
    		rightHigh := node.GetTreeHigh(node.RightNode)
    		if leftHigh > rightHigh {
    			return leftHigh + 1
    		} else {
    			return rightHigh + 1
    		}
    	}
    }
    
    // 递归前序遍历二叉树
    func (t *Tree) PreOrder(node *Tree) {
    	if node != nil {
    		fmt.Printf("%d", node.Value)
    		node.PreOrder(node.LeftNode)
    		node.PreOrder(node.RightNode)
    	}
    }
    
    // 递归前序遍历二叉树
    func (t *Tree) PreOrderUnRecursive(node *Tree) {
    	if node != nil {
    		stack := new(CommonStack)
    		stack.CommonPush(node)
    		for stack.CommonLen() > 0 {
    			nodePop, _ := stack.CommonPop()
    			node = nodePop.(*Tree)
    			fmt.Println(node.Value)
    			if node.RightNode != nil {
    				stack.CommonPush(node.RightNode)
    			}
    
    			if node.LeftNode != nil {
    				stack.CommonPush(node.LeftNode)
    			}
    		}
    	}
    }
    
    // 递归中序遍历二叉树
    func (t *Tree) InOrder(node *Tree) {
    	if node != nil {
    		node.InOrder(node.LeftNode)
    		fmt.Printf("%d", node.Value)
    		node.InOrder(node.RightNode)
    	}
    }
    
    // 递归后序遍历二叉树
    func (t *Tree) PostOrder(node *Tree) {
    	if node != nil {
    		node.PostOrder(node.LeftNode)
    		node.PostOrder(node.RightNode)
    		fmt.Printf("%d", node.Value)
    	}
    }
    
    // 打印所有的叶子节点
    func (t *Tree) GetLeafNode(node *Tree) {
    	if node != nil {
    		if node.LeftNode == nil || node.RightNode == nil {
    			fmt.Printf("%d", node.Value)
    		}
    
    		node.GetLeafNode(node.LeftNode)
    		node.GetLeafNode(node.RightNode)
    	}
    }
    
    // 打印所有的叶子节点
    func GenerateTree(ary []int) *Tree {
    	return Generate(ary, 0, len(ary)-1)
    }
    
    func Generate(ary []int, start, end int) *Tree {
    	if start > end {
    		return nil
    	}
    
    	middle := (start + end) / 2
    	head := CreateNodeValue(ary[middle])
    	fmt.Println(head)
    	head.LeftNode = Generate(ary, start, middle-1)
    	head.RightNode = Generate(ary, middle+1, end)
    	return head
    }