精华内容
下载资源
问答
  • 2020-03-12 20:45:31

    要实现二叉树结构的Python实现:

    1. 首先定义树的抽象基类,以通过继承该基类生成更多的具体类。
    2. 定义二叉树的抽象基类
    3. 定义链式二叉树

    定义树的抽象基类

    通过定义树的抽象基类,支持如下方法:

    方法解释
    p.element()返回位置p的元素
    T.root()返回树的根节点位置
    T.is_root( p )判断p是否为根节点
    T.parent( p )返回p的父节点位置
    T.children( p )返回p节点的孩子节点位置
    T.num_children( p )生成p节点孩子节点的迭代器
    T.is_leaf( p )判断p节点是否为叶节点
    T.is_empty()判断树是否是空树
    T.positions()用来迭代生成树的所有节点即遍历方法
    len(T)返回树所包含的元素数量
    iter(T)迭代生成储存在树中的所有元素
    T.height(p )返回p节点的高度
    T.depth( p)返回p节点的深度
    class Tree:
        '''树结构的抽象基类'''
    
        #----------------返回节点位置的基类---------------
        class Position:
            def element(self):
                """Return the element stored at this Position"""
                raise NotImplementedError("Must be implemente the subclass")
    
            def __eq__(self, other):
                """Return True or False"""
                raise NotImplementedError("Must be implemente the subclass")
    
            def __ne__(self, other):
                """Return True or False"""
                return not(self==other)
    
        #--------------------抽象方法------------------------
        def root(self):
            """返回树根节点的位置,如果为空树返回None"""
            raise NotImplementedError("Must be implemente the subclass")
    
        def parent(self,p):
            """返回节点p的父节点,若为根节点返回None"""
            raise NotImplementedError("Must be implemente the subclass")
    
        def children(self,p):
            raise NotImplementedError("Must be implemente the subclass")
    
        def num_children(self,p):
            """返回p节点的孩子节点的迭代位置"""
            raise NotImplementedError("Must be implemente the subclass")
    
        def __len__(self):
            """返回树种所有节点的个数"""
            raise NotImplementedError("Must be implemente the subclass")
    
        #------------------------抽象类的一些具体方法-------------------------------
        def is_root(self,p):
            """若是根节点返回True"""
            return self.root() == p
    
        def is_lesf(self,p):
            return self.num_children(p)==0
    
        def is_empty(self):
            return len(self)==0
    
        def depth(self,p):
            """返回p节点的深度,采用迭代的方法 根节点深度为0 时间复杂度O(dp+1)"""
            if self.is_root(p):
                return 0
            else:
                return 1 + self.depth(self.parent(p))
    
        def _higth2(self):
            if self.is_lesf(p):
                return 0
            else:
                return 1 + max(self._higth2(c) for c in self.children(p))
    
        def hight(self,p=None):
            if p is None:
                p=self.root()
            return self._higth2(p)
    

    定义二叉树的抽象基类

    定义二叉树的抽象基类,在继承树的抽象基类的基础上,加入leftrightslibing方法,并重写了children方法。

    class BinaryTree(Tree):
        """ 二叉树的抽象基类 """
    
        #----------------其他的抽象方法--------------------
        def left(self,p):
            raise NotImplementedError("Must be implemente the subclass")
    
        def right(self,p):
            raise NotImplementedError("Must be implemente the subclass")
    
        def slibling(self,p):
            """返回p节点的兄弟节点的位置"""
            parent=self.parent(p)
            if parent is None:
                return None
            else:
                if p==self.left(parent):
                    return self.right(parent)
                else:
                    return self.left(parent)
    
        def children(self,p):
            if self.left(p) is not None:
                yield self.left(p)
            if self.right(p) is not None:
                yield self.right(p)
    

    定义链式二叉树

    (1) 初始化

    定义非公开的_Node类表示一个节点
    在定义一个Position类封装该节点
    _validate用来判断实例的有效性
    _make_position 用来将实例进行封装

    class LinkedBinaryTree(BinaryTree):
    
        class _Node:
            __slots__ = "_element","_parent","_left",'_right'  # 对类的实例属性进行限制定义
            def __init__(self,element,parent=None,left=None,right=None):
                self._element=element
                self._parent=parent
                self._left=left
                self._right=right
    
        class Position(BinaryTree.Position):
            def __init__(self,container,node):
                self._container=container
                self._node=node
    
            def element(self):
                return self._node._element
    
            def __eq__(self, other):
                return type(other) is type(self) and other._node is self._node
    
        def _validata(self,p):
            if not isinstance(p,self.Position): # 判断一个对象是否是一个已知的类型,类似 type()但是type函数不会考虑继承关系
                raise TypeError('p must be a proper type')
            if p._container is not self:
                raise ValueError('p does not belong to this container')
            return p._node
        
        def _make_position(self,node):
            return self.Position(self,node) if node is not None else None
    

    (2)类的公开访问方法的定义:操作树现有方法的定义

        def __init__(self):
            self._root=None
            self._size=0
    
        def __len__(self):
            return self._size
    
        def root(self):
            return self._make_position(self._root)
    
        def parent(self,p):
            node=self._validata(p)
            return self._make_position(node._parent)
    
        def left(self,p):
            node=self._validata(p)
            return self._make_position(node._left)
    
        def right(self,p):
            node=self._validata(p)
            return self._make_position(node._right)
    
        def num_children(self,p):
            node=self._validata(p)
            count=0
            if node._left is not None:
                count+=1
            if node._right is not None:
                count+=1
            return count
    

    (3)更新二叉树的操作

    方法功能
    T.add_root(e)为空树创建根节点,存储e
    T.add_left(p,e)创建新节点,存储e 位于p的左孩子
    T.add_right(p,e)创新新节点 存储e 位于p的右孩子
    T.replace(p,e)用e取代节点p处的元素 返回之前的元素
    T.delete( p )删除掉p节点
    T.attach(p,T1,T2)将子树连接到p节点
    更多相关内容
  • 连式存储二叉树结构图: 代码实现: //-----------------------------------------创建二叉树以及添加根节点测试类----------------------------------------------- package day0504; /** * @author Czw * @...

    连式存储的二叉树结构图:
    在这里插入图片描述
    代码实现

    //-----------------------------------------创建二叉树以及添加根节点测试类-----------------------------------------------
    package day0504;
    
    /**
     * @author Czw
     * @Description 创建一棵链式二叉树
     * @Date 2019/5/4 0004 上午 10:58
     */
    public class TestBinaryTree {
        public static void main ( String [] args){
            //创建一棵二叉树
            BinaryTree binTree=new BinaryTree();
            //创建一个根节点
            TreeNode root=new TreeNode(1);
            //为根节点创建左节点
            TreeNode leftNode=new TreeNode(2);
            //为根节点创建右节点
            TreeNode rightNode=new TreeNode(3);
            //为根节点赋左右节点值
            root.setLeftNode(leftNode);
            root.setRightNode(rightNode);
            //赋给树
            binTree.setRoot(root);
    
        }
    }
    //-------------------------------------链式存储的二叉树类-------------------------------------------------
    package day0504;
    
    
    /**
     * @author Czw
     * @Description 链式存储的二叉树
     * @Date 2019/5/4 0004 上午 10:59
     */
    public class BinaryTree {
        //树的根节点
        TreeNode root;
    
    
        public void setRoot(TreeNode root) {
            this.root = root;
        }
    }
    //-----------------------------------------代表每个节点对象的类-----------------------------------------------
    package day0504;
    
    /**
     * @author Czw
     * @Description 链式存储二叉树的节点内容
     * @Date 2019/5/4 0004 上午 11:05
     */
    public class TreeNode {
        //节点的权
        int value;
        //左儿子
        TreeNode leftNode;
        //右儿子
        TreeNode rightNode;
        public TreeNode(int value){
            this.value=value;
        }
    
        public void setLeftNode(TreeNode leftNode) {
            this.leftNode = leftNode;
        }
    
        public void setRightNode(TreeNode rightNode) {
            this.rightNode = rightNode;
        }
    }
    
    
    

    二叉树的遍历分为前、中、后三种遍历方式
    在这里插入图片描述
    前序遍历:A B D E C F G(先取自己再去子节点,子节点若有节点同样如此)
    中序遍历:D B E A F C G (先取左边子节点再自己然后右节点,若子节点有节点则同样如此)
    后序遍历:D E B F G C A (先取左节点再取右节点再取自己,若有子节点则同样如此)
    代码实现

    package day0504;
    
    /**
     * @author Czw
     * @Description 测试创建一棵链式二叉树
     * @Date 2019/5/4 0004 上午 10:58
     */
    public class TestBinaryTree {
        public static void main ( String [] args){
            //创建一棵二叉树
            BinaryTree binTree=new BinaryTree();
            //创建一个根节点
            TreeNode root=new TreeNode(1);
            //赋给树
            binTree.setRoot(root);
            //为根节点创建左节点
            TreeNode leftNode=new TreeNode(2);
            //为根节点创建右节点
            TreeNode rightNode=new TreeNode(3);
            //为根节点赋左右节点值
            root.setLeftNode(leftNode);
            root.setRightNode(rightNode);
    
            //为第二层左节点创建两个子节点
            leftNode.setLeftNode(new TreeNode(4));
            leftNode.setRightNode(new TreeNode(5));
            //为第二层右节点创建两个子节点
            rightNode.setLeftNode(new TreeNode(6));
            rightNode.setRightNode(new TreeNode(7));
    
            //前序遍历
            binTree.frontShow();//结果:1 2 4 5 3 6 7
            System.out.println("");
            //中序遍历
            binTree.middleShow();//结果:4 2 5 1 6 3 7
            System.out.println("");
            //后序遍历
            binTree.afterShow();//结果:
    
        }
    }
    ------------------------------------------------------------------
    package day0504;
    
    
    /**
     * @author Czw
     * @Description 链式存储的二叉树
     * @Date 2019/5/4 0004 上午 10:59
     */
    public class BinaryTree {
        //树的根节点
        TreeNode root;
    
    
        public void setRoot(TreeNode root) {
            this.root = root;
        }
    
        public void frontShow() {
            root.frontShow();
        }
    
        public void middleShow() {
            root.middleShow();
        }
    
        public void afterShow() {
            root.afterShow();
        }
    }
    ---------------------------------------------
    package day0504;
    
    /**
     * @author Czw
     * @Description 链式存储二叉树的节点内容
     * @Date 2019/5/4 0004 上午 11:05
     */
    public class TreeNode {
        //节点的权
        int value;
        //左儿子
        TreeNode leftNode;
        //右儿子
        TreeNode rightNode;
        public TreeNode(int value){
            this.value=value;
        }
    
        //前遍历
        public void frontShow(){
            System.out.print(value+" ");
            if (leftNode!=null){
                leftNode.frontShow();
            }
            if (rightNode!=null){
                rightNode.frontShow();
            }
    
        }
    
    
    
    
        public void setLeftNode(TreeNode leftNode) {
            this.leftNode = leftNode;
        }
    
        public void setRightNode(TreeNode rightNode) {
            this.rightNode = rightNode;
        }
    
    
        public void middleShow() {
            if (leftNode!=null){
                leftNode.middleShow();
            }
            System.out.print(value+" ");
            if (rightNode!=null){
                rightNode.middleShow();
            }
    
    
        }
    
        public void afterShow() {
            if (leftNode!=null){
                leftNode.afterShow();
            }
            if (rightNode!=null){
                rightNode.afterShow();
            }
            System.out.print(value +" ");
        }
    }
    
    
    
    

    查找value值相同的节点
    实现代码

    package day0504;
    
    /**
     * @author Czw
     * @Description 测试创建一棵链式二叉树
     * @Date 2019/5/4 0004 上午 10:58
     */
    public class TestBinaryTree {
        public static void main ( String [] args){
            //创建一棵二叉树
            BinaryTree binTree=new BinaryTree();
            //创建一个根节点
            TreeNode root=new TreeNode(1);
            //赋给树
            binTree.setRoot(root);
            //为根节点创建左节点
            TreeNode leftNode=new TreeNode(2);
            //为根节点创建右节点
            TreeNode rightNode=new TreeNode(3);
            //为根节点赋左右节点值
            root.setLeftNode(leftNode);
            root.setRightNode(rightNode);
    
            //为第二层左节点创建两个子节点
            leftNode.setLeftNode(new TreeNode(4));
            leftNode.setRightNode(new TreeNode(5));
            //为第二层右节点创建两个子节点
            rightNode.setLeftNode(new TreeNode(6));
            rightNode.setRightNode(new TreeNode(7));
    
            //前序遍历
            binTree.frontShow();//结果:1 2 4 5 3 6 7
            System.out.println("");
            //中序遍历
            binTree.middleShow();//结果:4 2 5 1 6 3 7
            System.out.println("");
            //后序遍历
            binTree.afterShow();//结果:4 5 2 6 7 3 1
            System.out.println();
            //查找指定元素
            TreeNode result=binTree.frontSearch(5);
            System.out.println(result);
    
        }
    }
    
    -------------------------------------------------------------------------------------------
    package day0504;
    
    
    /**
     * @author Czw
     * @Description 链式存储的二叉树
     * @Date 2019/5/4 0004 上午 10:59
     */
    public class BinaryTree {
        //树的根节点
        TreeNode root;
    
    
        public void setRoot(TreeNode root) {
            this.root = root;
        }
    
        public void frontShow() {
            root.frontShow();
        }
    
        public void middleShow() {
            root.middleShow();
        }
    
        public void afterShow() {
            root.afterShow();
        }
    
        public TreeNode frontSearch(int i) {
            return root.frontSearch(i);
        }
    }
    
    --------------------------------------------------------------------------------------
    package day0504;
    
    
    /**
     * @author Czw
     * @Description 链式存储的二叉树
     * @Date 2019/5/4 0004 上午 10:59
     */
    public class BinaryTree {
        //树的根节点
        TreeNode root;
    
    
        public void setRoot(TreeNode root) {
            this.root = root;
        }
    
        public void frontShow() {
            root.frontShow();
        }
    
        public void middleShow() {
            root.middleShow();
        }
    
        public void afterShow() {
            root.afterShow();
        }
    
        public TreeNode frontSearch(int i) {
            return root.frontSearch(i);
        }
    }
    
    
    展开全文
  • 采用链式结构存放二叉树实现二叉数的创建,实现二叉数的遍历(前序,后序,中序层次遍历),分别求二叉树的叶子结点和结点的数目,二叉树查找二叉树的深度。
  • 文章目录二叉树的遍历前序遍历中序遍历:后序遍历节点个数及高度等求二叉树节点个数求二叉树叶子节点个数求二叉树第k层节点个数求二叉树深度/高度查找值为x的节点二叉树基础oj练习单值二叉树二叉树的前序遍历 二叉树...

    二叉树的遍历

    为了先了解二叉树的结构,此处先手动快速创建一棵简单的二叉树:
    在这里插入图片描述

    typedef char BTDataType;
    typedef struct BinaryTreeNode
    {
    	BTDataType _data;
    	struct BinaryTreeNode* _left;
    	struct BinaryTreeNode* _right;
    }BTNode;
    
    BTNode* BuyNode(BTDataType x)
    {
    	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    	node->_data = x;
    	node->_left = NULL;
    	node->_right = NULL;
    }
    
    BTNode* CreatBinaryTree()
    {
    	BTNode* node1 = BuyNode('A');
    	BTNode* node2 = BuyNode('B');
    	BTNode* node3 = BuyNode('C');
    	BTNode* node4 = BuyNode('D');
    	BTNode* node5 = BuyNode('E');
    	BTNode* node6 = BuyNode('F');
    	BTNode* node7 = BuyNode('G');
    
    	node1->_left = node2;
    	node1->_right = node3;
    	node2->_left = node4;
    	node3->_left = node5;
    	node3->_right = node6;
    	node4->_left = node7;
    	return node1;
    }
    

    按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

    前序遍历

    void PreOrder(BTNode* root)
    {
    	if (root == NULL)
    	{
    		printf("NULL ");
    		return;
    	}
    
    	printf("%c ", root->_data);
    	PreOrder(root->_left);
    	PreOrder(root->_right);
    }
    

    前序遍历递归图解:
    在这里插入图片描述

    中序遍历:

    void InOrder(BTNode* root)
    {
    	if (root == NULL)
    	{
    		printf("NULL ");
    		return;
    	}
    
    	InOrder(root->_left);
    	printf("%c ", root->_data);
    	InOrder(root->_right);
    }
    

    后序遍历

    void PostOrder(BTNode* root)
    {
    	if (root == NULL) {
    		printf("NULL ");
    		return;
    	}
    
    	PostOrder(root->left);
    	PostOrder(root->right);
    	printf("%c ", root->data);
    }
    

    测试结果:
    在这里插入图片描述

    节点个数及高度等

    求二叉树节点个数

    核心思想:节点个数=1+左子树节点个数+右子树节点个数

    int BinaryTreeSize(BTNode* root)
    {
    	return root==NULL?0:1
    		+BinaryTreeSize(root->_left)
    		+ BinaryTreeSize(root->_right);
    }
    

    求二叉树叶子节点个数

    int BinaryTreeLeafSize(BTNode* root)
    {
    	if (root == NULL)
    		return 0;
    	else if (root->_left == NULL && root->_right == NULL)
    		return 1;
    	else
    		return BinaryTreeLeafSize(root->_left)
    		+ BinaryTreeLeafSize(root->_right);
    }
    

    求二叉树第k层节点个数

    核心思路:当前树的第k层节点个数=当前树的左子树的第k-1层个数+当前树的右子树的第k-1层个数

    int BinaryTreeLeavelKSize(BTNode* root, int k)
    {
    	if (root == NULL)
    		return 0;
    	else if (k == 1)
    		return 1;
    	else
    		return BinaryTreeLeavelKSize(root->_left,k-1)
    		+ BinaryTreeLeavelKSize(root->_right,k-1);
    }
    

    求二叉树深度/高度

    核心思想:当前树的深度=max(左子树深度,右子树深度)+1

    int BinaryTreeDepth(BTNode* root)
    {
    	if (root == NULL)
    		return 0;
    	
    	//先给两个变量存储结果,若直接放到return就得算两次
    	int leftDepth = BinaryTreeDepth(root->_left);
    	int rightDepth = BinaryTreeDepth(root->_right);
    
    	return leftDepth > rightDepth?leftDepth+1:rightDepth+1;
    }
    

    查找值为x的节点

    1. 先判断是不是当前节点,是就返回
    2. 不是就先去左树找,找到了就返回
    3. 左树没找到,再去右树找。
    BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
    {
    	if (root == NULL)
    		return NULL;
    
    	if (root->_data == x)
    		return root;
    
    	BTNode* left = BinaryTreeFind(root->_left, x);
    	if (left)
    		return left;
    	BTNode* right = BinaryTreeFind(root->_right, x);
    	if(right)
    	return right;
    
    	return NULL;
    }
    

    二叉树基础oj练习

    分治:大问题分成小问题,小问题再继续分,直到分割成不可再分割的子问题。

    单值二叉树

    题目描述:如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回true,否则返回false
    在这里插入图片描述

    思路:

    1. ==具有传递性
    2. a == b && a == c
    3. b == e && b == f
    4. 即a跟e和f相等。
    bool isUnivalTree(struct TreeNode* root){
        if(root==NULL)
            return true;
        if(root->left && root->val != root->left->val)
            return false;
        if(root->right && root->val != root->right->val)
            return false;
        
        return isUnivalTree(root->left) 
        && isUnivalTree(root->right);
    }
    

    其中if(root->left && root->val != root->left->val) &&两边不能调换,否则如果root->left为空,但却已经进行了两个值的比较,会报错。

    二叉树的前序遍历

    题目描述:给你二叉树的根节点root,返回它节点值的前序遍历

    /**
     * Note: The returned array must be malloced, assume caller calls free().
     */
    int TreeSize(struct TreeNode* root)
    {
        if(root==NULL)
            return 0;
        return 1+TreeSize(root->left)+TreeSize(root->right);
    }
    
    void _preorderTraversal(struct TreeNode* root,int* arr,int* pi)
    {
        if(root==NULL)
            return;
    
        arr[(*pi)++]=root->val;
        _preorderTraversal(root->left,arr,pi);
        _preorderTraversal(root->right,arr,pi);
    }
    
    int* preorderTraversal(struct TreeNode* root, int* returnSize){
        *returnSize=TreeSize(root);
        int* arr=(int*)malloc(sizeof(int)* *returnSize);
        int i=0;
        _preorderTraversal(root,arr,&i);
        return arr;
    }
    

    注意:void _preorderTraversal中,最后一个参数要传的是指针。每个递归调用栈帧中都有一个i,下一层++i,不会对上一次影响。但是我们想要的是只有一个i作为下标++

    相同的树

    题目描述:给你两棵二叉树的根节点p和q,编写一个函数来检验这两棵树是否相同。如果两个数在结构上相同,并且节点具有相同的值,则认为它们是相同的。
    在这里插入图片描述

    要比较两棵树是否相同,就要比较两棵树的根节点和各自的左子树和右子树是否相同。

    bool isSameTree(struct TreeNode* p, struct TreeNode* q)
    {
        if(p==NULL && q==NULL)
            return true;
        if(p==NULL || q==NULL)
            return false;
        if(p->val!=q->val)
            return false;
            
        return isSameTree(p->left,q->left)
            && isSameTree(p->right,q->right);
    }
    
    • 时间复杂度:O(N)
    • 空间复杂度:O(h)-> 最坏情况 O(N) 完全二叉树或满二叉树h=logN

    对称二叉树

    题目描述:给定一个二叉树,检查它是否是镜像对称的。
    在这里插入图片描述

    要判断是否对称,首先判断根节点是否为空,再判断根节点的左右子树是否对称,递归。

    bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
    {
        if(p==NULL && q==NULL)
            return true;
        if(p==NULL || q==NULL)
            return false;
        if(p->val!=q->val)
            return false;
            
        return _isSymmetric(p->left,q->right)
            && _isSymmetric(p->right,q->left);
    }
    
    bool isSymmetric(struct TreeNode* root){
        if(root==NULL)
            return true;
        
        return _isSymmetric(root->left,root->right);      
    }
    

    另一棵树的子树

    题目描述:给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
    二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
    在这里插入图片描述

    bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
    {
        if(root==NULL)
            return false;
        if(isSameTree(root,subRoot))
            return true;
        return isSubtree(root->left,subRoot)
            || isSubtree(root->right,subRoot);
    }
    

    二叉树的创建和销毁

    通过前序遍历的数组构建二叉树

    问题描述:编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
    在这里插入图片描述

    struct TreeNode
    {
        char val;
        struct TreeNode* left;
        struct TreeNode* right;
    };
    
    struct TreeNode* CreatTree(char* str,int* pi)
    {
        if(str[*pi]=='#')
        {
            (*pi)++;
            return NULL;
        }
        
        struct TreeNode* root=(struct TreeNode*)
            malloc(sizeof(struct TreeNode));
        root->val=str[(*pi)++];
        root->left=CreatTree(str, pi);
        root->right=CreatTree(str, pi);
        
        return root;
    }
    
    void InOrder(struct TreeNode* root)
    {
        if(root==NULL)
            return;
        InOrder(root->left);
        printf("%c ",root->val);
        InOrder(root->right);
    }
    int main()
    {
        char str[100];
        scanf("%s",str);
        int i=0;
        struct TreeNode* root=CreatTree(str, &i);
        InOrder(root);
        return 0;
    }
    

    二叉树销毁

    //二叉树销毁
    void BinaryTreeDestroy(BTNode* root)
    {
    	if (root == NULL)
    		return;
    
    	BinaryTreeDestroy(root->_left);
    	BinaryTreeDestroy(root->_right);
    	free(root);
    }
    

    层序遍历

    用队列实现二叉树的层序遍历。先把第一次(根)放入队列。上一层出队,带入下一层。

    //层序遍历
    void BinaryTreeLevelOrder(BTNode* root)
    {
    	Queue q;
    	QueueInit(&q);
    	if (root)
    	{
    		QueuePush(&q, root);
    	}
    	while (!QueueEmpty(&q))
    	{
    		BTNode* front = QueueFront(&q);
    		QueuePop(&q);
    		printf("%c ", front->_data);
    		if (front->_left)
    		{
    			QueuePush(&q,front->_left);
    		}
    		if (front->_right)
    		{
    			QueuePush(&q, front->_right);
    		}
    	}
    	printf("\n");
    	QueueDestroy(&q);
    }
    

    以此树为例:
    在这里插入图片描述

    测试结果:
    在这里插入图片描述

    判断是否是完全二叉树

    核心思路: 层序遍历,把空的节点也入队列。如果是完全二叉树,非空节点是连续的,空也是连续的。如果不是完全二叉树,非空节点不连续,空也不连续。

    bool BinaryTreeComplete(BTNode* root)
    {
    	Queue q;
    	QueueInit(&q);
    	if (root)
    	{
    		QueuePush(&q, root);
    	}
    	while (!QueueEmpty(&q))
    	{
    		BTNode* front = QueueFront(&q);
    		QueuePop(&q);
    		if (front==NULL)
    		{
    			break;
    		}
    		QueuePush(&q, front->_left);
    		QueuePush(&q, front->_right);
    	}
    	//找到空后,队列中全是空,就是完全二叉树
    	//还有非空,就不是完全二叉树
    	while (!QueueEmpty(&q))
    	{
    		BTNode* front = QueueFront(&q);
    		QueuePop(&q);
    		if (front)
    		{
    			QueueDestroy(&q);
    			return false;
    		}
    	}
    	QueueDestroy(&q);
    	return true;
    }
    

    测试结果:
    在这里插入图片描述

    展开全文
  • 二叉树链式存储二叉树各种遍历的算法实现 书是一种一对多的逻辑结构,在使用链式存储的时候,经常使用的是二叉链表(三个域:左孩子指针域,数据域,右孩子指针域),三叉链表(左孩子域,数据域,双亲域,右孩子...

    二叉树链式存储及二叉树各种遍历的算法实现

    书是一种一对多的逻辑结构,在使用链式存储的时候,经常使用的是二叉链表(三个域:左孩子指针域,数据域,右孩子指针域),三叉链表(左孩子域,数据域,双亲域,右孩子域),这里使用的是二叉链表完成了几个最基本的二叉树的操作。

    #include <iostream>
    using namespace std;
    
    
    typedef struct BiTNode
    {
    	char data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    //1.创建树
    struct BiTNode* CreateBiTree(char data)
    {
    	struct BiTNode* T = (struct BiTNode*)malloc(sizeof(struct BiTNode));
    	T->data = data;
    	T->lchild = NULL;
    	T->rchild = NULL;
    	return T;
    }
    void insertNode(struct BiTNode* curNode, struct BiTNode* lefNode, struct BiTNode* rigNode)
    {
    	curNode->lchild = lefNode;
    	curNode->rchild = rigNode;
    }
    
    void printData(struct BiTNode* curNode)
    {
    	cout << curNode->data;
    }
    
    void preorder(struct BiTNode* tree) //递归前序
    {
    	if (tree != NULL)
    	{
    		printData(tree);
    		preorder(tree->lchild);
    		preorder(tree->rchild);
    
    	}
    }
    
    void midorder(struct BiTNode* tree) //递归中序
    {
    	if (tree != NULL)
    	{
    		midorder(tree->lchild);
    		printData(tree);
    		midorder(tree->rchild);
    
    	}
    }
    
    void postorder(struct BiTNode* tree)  //递归后序
    {
    	if (tree != NULL)
    	{
    		postorder(tree->lchild);
    		postorder(tree->rchild);
    		printData(tree);
    	}
    }
    
    void midorderbystack(struct BiTNode* tree)   //非递归中序遍历
    {
    	if (tree == NULL)
    		return;
    	struct BiTNode* stack[10];
    	int stacktop = -1;
    	struct BiTNode* pmove = tree;
    	while (stacktop != -1 || pmove)
    	{
    		while (pmove)
    		{
    			stack[++stacktop] = pmove;
    			pmove = pmove->lchild;
    		}
    		if (stacktop != -1)
    		{
    			pmove = stack[stacktop--];
    			cout << pmove->data;
    			pmove = pmove->rchild;
    		}
    	}
    }
    
    void preorderbystack(struct BiTNode* tree)   //非递归前序遍历
    {
    	if (tree == NULL)
    		return;
    	struct BiTNode* stack[10];
    	int stacktop = -1;
    	struct BiTNode* pmove = tree;
    	stack[++stacktop] = pmove;
    	while (stacktop != -1)
    	{
    		pmove = stack[stacktop--];
    		cout << pmove->data;
    		if (pmove->rchild != NULL)
    			stack[++stacktop] = pmove->rchild;
    		if (pmove->lchild != NULL)
    			stack[++stacktop] = pmove->lchild;
    	}
    }
    
    void postorderbystack(struct BiTNode* tree)   //非递归后序遍历
    {
    	if (tree == NULL)
    		return;
    	struct BiTNode* stack[10];
    	int stacktop = -1;
    	struct BiTNode* p = tree; //移动节点
    	struct BiTNode* q = NULL; //标记结点
    	while (p != NULL)
    	{
    		while (p->lchild != NULL)
    		{
    			stack[++stacktop] = p;
    			p = p->lchild;
    		}
    		while (p != NULL && (p->rchild == NULL || p->rchild == q))
    		{
    			cout << p->data;
    			q = p;
    			if (stacktop == -1)
    			{
    				return;
    			}
    			p = stack[stacktop--];
    		}
    		stack[++stacktop] = p;
    		p = p->rchild;
    	}
    
    }
    
    void levelorderbyqueue(struct BiTNode* tree)
    {
    	if (tree == NULL)
    	{
    		return;
    	}
    	struct BiTNode* queue[10];
    	int front, rear;
    	front = rear = 0;
    	struct BiTNode* p = tree;
    	rear = (rear + 1) % 10;
    	queue[rear] = p;
    	while (front != rear)
    	{
    		front = (front + 1) % 10;
    		p = queue[front];
    		cout << p->data;
    		if (p->lchild != NULL){ rear = (rear + 1) % 10; queue[rear] = p->lchild; }
    		if (p->rchild != NULL){ rear = (rear + 1) % 10; queue[rear] = p->rchild; }
    	}
    }
    
    
    void main()
    {
    	struct BiTNode* A = CreateBiTree('A');
    	struct BiTNode* B = CreateBiTree('B');
    	struct BiTNode* C = CreateBiTree('C');
    	struct BiTNode* D = CreateBiTree('D');
    	struct BiTNode* E = CreateBiTree('E');
    	struct BiTNode* F = CreateBiTree('F');
    	struct BiTNode* G = CreateBiTree('G');
    
    	insertNode(A, B, C);
    	insertNode(B, D, E);
    	insertNode(D, F, NULL);
    	insertNode(E, NULL, G);
    
    	cout << "递归先序遍历:"; preorder(A); cout << "\n";
    	cout << "递归中序遍历:"; midorder(A); cout << "\n";
    	cout << "递归后序遍历:"; postorder(A); cout << "\n";
    	cout << "非递归先序遍历:"; preorderbystack(A); cout << "\n";
    	cout << "非递归中序遍历:"; midorderbystack(A); cout << "\n";
    	cout << "非递归后序遍历:"; postorderbystack(A); cout << "\n";
    	cout << "层次遍历:"; levelorderbyqueue(A); cout << "\n";
    	system("pause");
    }
    

    二叉树如下:

    简单讲一下二叉树非递归的三种遍历方法:
    1.非递归先序遍历:非递归先序遍历使用的是栈结构来实现的。大致思路是,首先将根节点入栈,只要栈不为空就出栈一个元素,然后将这个元素的右孩子和左孩子分别入栈,重复以上操作,知道栈中元素为空时,结束遍历。

    2.非递归中序遍历:非递归中序遍历的方法也是栈结构来实现的。大致思路是,创建一个移动的结构体指针,如果结点不为空,则入栈,然后结构体指针指向自己的左孩子(p = p -> lchild),直到p为空为止,这时候 判断栈是否为空,如果不为空,则出栈一个元素,p指向这个出栈元素,输出这个元素,移动的结构体指针p在指向这个元素的右孩子(p = p -> rchild),重复这部分操作,直到栈中元素为空时,结束。

    3.非递归后序遍历:非递归中序遍历的方法也是栈结构来实现的。大致思路是,创建一个移动的结构体指针 p 和一个用来做标记的结构体指针 q ,首先将根节点入栈,然后将根节点的左孩子入栈,只要入栈结点的左孩子不为空时,则将元素一直入栈,当入栈元素的左孩子为空时,这时候判断 p 指向的元素的右孩子是否为空或者是否指向标记的指针,如果这个条件不满足(有右孩子),则将这个结点入栈,移动的结构体指针指向入栈元素的右孩子(p = p -> rchild),这时候重复上面的过程,当满足入栈元素的右孩子是否为空或者是否指向标记的指针时,这时候打印这个元素 p 指向的元素,然后让 q = p; 标记这个元素结点被标记(已经被遍历过了),然后出现一个元素让 p 指向这个出栈的元素。重复上述过程,当栈为空是,遍历结束。

    4.层次遍历:层次遍历二叉树的方法使用队列来实现的。大致思路是,首先将根节点入队,如多队列不为空就出队一个元素,再将这个出队元素的左右孩子分别入队,重复上述步骤,如果队列为空,则层次遍历结束。

    二叉树的非递归遍历需要好好理解,大家可以看我上面写的大致思路,参考代码来领悟。有不解得可以发评论或者私信。

    展开全文
  • 实现链式存储二叉树构建完成查找、求树高度、中序遍历、先遍历、后序遍历和层序遍历的程序,并用相关数据进行测试。给出算法的时间和空间复杂度。
  • 二叉树 创建树: ABC$$DE$G$$F$$$ 代码先放这,有空写注释 #include<bits/stdc++.h> #include<cstdio> using namespace std; #define OK 1 #define ERROR 0 #define MAX_TREE_SIZE 100 #define STACK_...
  • 二叉树链式存储的前中后递归和非递归遍历实现 1. 二叉树链式存储结构 #define ElementType char typedef struct BTNode{ ElementType data; struct BTNode *left,*right; }BTNode,*BinTree; 2. 二叉树的前序、...
  • 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树、FP-树。另外可以用来提高编码效率,如哈弗曼树。 用 Python 实现树的构造和几种遍历算法。实现功能...
  • 本文以链表的方式实现二叉树的创建,遍历,拷贝,求深度,删除子树,删除结点,插入结点等操作。
  • C语言二叉树实现及遍历(前序,中序,后序) 案例树 源代码 #include "string.h" #include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #...
  • 实现链式存储二叉树构建完成查找、求树高度、中序遍历、先序遍历、后序遍历和层序遍历的程序,并用相关数据进行测试。给出算法的时间和空间复杂度。
  • 二叉树 链式存储结构 结构定义: template<typename ElemType> struct BiNode { ElemType data; struct BiNode* lchild, * rchild; }; template<typename ElemType> using BiTree = BiNode<...
  • 二叉树链式结构的实现

    千次阅读 多人点赞 2021-11-29 17:38:49
    4、查找二叉树中值为x的节点 5、求二叉树的深度or高度 6、判断一棵树是否是完全二叉树 7、二叉树的销毁 四、二叉树的OJ题 1、单值二叉树 2、二叉树的前序遍历变型 3、相同的树 4、对称二叉树 5、另一颗子树 6、...
  • 二叉树存储方式三、二叉树的基本操作1.树的创建—向二叉树插入节点2.二叉树的遍历2.1 深度优先遍历2.1.1 前序遍历2.1.2 中序遍历2.1.3 后序遍历2.1.4 总结2.2 广度优先遍历2.3 全部代码3.推导遍历结果 引言   树...
  • 二叉树链式存储实现 1、树的概念及结构 1.1、树的结构 树是一种非线性结构,它由n(n>=0)个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树,也就是说它是一颗根朝上,叶朝...
  • int Btdepth(Bitreee T){ if(!T) return 0; //如果是空树,则高度为1; int front =-1,rear=-1; //定义顺序队列,队列元素是二叉树结点指针,用于层序访问链式二叉树; BiTree Q[MaxSize]; ...
  • 二叉树链式存储 先慢慢介绍一下链式存储的节点结构!!! 图 2 普通二叉树示意图 如上图 2 所示,若将其采用链式存储,则只需从树的根节点开始,将各个节点及其左右孩子使用链表存储 因
  • from collections import deque class BTNode: #二叉链中结点类 def init(self,d=None): #构造方法 self.data=d #结点值 self.lchild=None #左hai子指针 self.rchild=None #右hai子指针 class BTree: #二叉树类 def ...
  • #include<stdio.h> #include<stdlib.h> typedef struct BinaryTreeNode{ char data; struct BinaryTreeNode *lchild,*rchild; }BinaryTreeNode,*BinTree; void PreCreateBT(BinTree *t){ ... else{
  • 二叉树链式存储)—— C++实现

    千次阅读 2019-12-21 13:07:29
    二叉树链式存储) 非线性 物理上不连在一起 树型结构 直接开撸,首先需要我们的头文件与命名空间: #include <iostream> #include <deque> // 下面的层级遍历的算法需要用到队列 ...
  • 数据结构-链式二叉树 1、前言 2、n遍历 (1)前序遍历 它是树结构插入、删除、修改、查找和排序运算的前提,是二叉树一切运算的基础和核心。 遍历二叉树----从根结点出发,按照某种次序依次访问二叉树中...
  • 二叉树链式存储实现及遍历

    千次阅读 2017-11-18 21:38:59
    关于二叉树链式存储和遍历
  • 查找某一个节点 二叉树的销毁 前言 之前我们介绍了二叉树的顺序存储结构, 顺序存储相对特殊, 适用范围相对较窄, 仅适用于完全二叉树的存储, 而链式存储较之有所不同, 它的适用范围更广, 它可适用于所有二叉树的存储;...
  • class Node(object): """定义树节点""" def __init__(self,item): self.elem = item self.left = None self.right = None class Tree(object): def __init__(self): self.root = None def add(self,item): ...
  • 本节我们学习二叉树链式存储结构。 正文 图 1 普通二叉树示意图 如图 1 所示,此为一棵普通的二叉树,若将其采用链式存储,则只需从树的根节点开始,将各个节点及其左右孩子使用链表存储即可。因此,图 1 对应的...
  • 由于顺序存储二叉树的空间利用率较低,因此二叉树一般都采用链式存储结构,用链表结点来存储二叉树中的每个结点。在二叉树中,结点结构通过包括若干数据域和若干指针域,二叉链表至少包含3个域:数据域 data、左指针...
  • 二叉树——链式存储

    2021-08-28 16:33:48
    一、二叉树结构定义 二叉树的节点定义: typedef char ElemType; typedef struct ...手动构建一个如图所示的二叉树。 // 生成新节点 BitNode *newBitNode(ElemType data) { BitNode *bitNode = (BitNode *)ma
  • 链式二叉树的基本操作(建议收藏!!!)

    千次阅读 多人点赞 2021-05-04 16:45:06
    文章目录二叉树的深度优先遍历前序遍历中序遍历后序遍历二叉树的广度优先遍历层序遍历结点的个数叶子结点的个数第k层结点的个数值为x的结点树的最大深度判断二叉树是否是完全二叉树判断二叉树是否是单值二叉树判断...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,500
精华内容 3,000
关键字:

实现链式存储二叉树构建完成查找程序