精华内容
下载资源
问答
  • 数据结构之二叉树

    千次阅读 2019-09-07 10:56:12
    数据结构之二叉树 emmmmmm复习一下二叉树的知识 基本知识 一、树的定义 树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。 树具有的特点有: (1)每个结点有零个或多个子结点 (2)...

    数据结构之二叉树

    emmmmmm复习一下二叉树的知识

    • 基本知识

    一、树的定义

    树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。
    在这里插入图片描述

    树具有的特点有:

    (1)每个结点有零个或多个子结点

    (2)没有父节点的结点称为根节点

    (3)每一个非根结点有且只有一个父节点

    (4)除了根结点外,每个子结点可以分为多个不相交的子树。

    树的基本术语有:

    若一个结点有子树,那么该结点称为子树根的“双亲”,子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。

    结点的度:结点拥有的子树的数目

    叶子结点:度为0的结点

    分支结点:度不为0的结点

    树的度:树中结点的最大的度

    层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1

    树的高度:树中结点的最大层次

    森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。

    这些都是书上的基本概念

    二、二叉树

    1、二叉树的定义

    二叉树是每个结点最多有两个子树的树结构。

    五种基本形态:二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。
    在这里插入图片描述

    2、二叉树的性质

    • 性质1:二叉树第i层上的结点数目最多为2i-1(i>=1)
    • 性质2:深度为k的二叉树至多有2k-1个结点(k>=1)
    • 性质3:包含n个结点的二叉树的高度至少为(log2n)+1
    • 性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1

    三、满二叉树、完全二叉树和二叉查找树

    1、满二叉树

    定义:高度为h,并且由2h-1个结点组成的二叉树,称为满二叉树

    在这里插入图片描述
    2、完全二叉树

    定义:一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下层的叶结点集中在靠左的若干位置上,这样的二叉树称为完全二叉树。

    特点:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树。

    在这里插入图片描述

    3、二叉查找树

    定义:二叉查找树又被称为二叉搜索树。设x为二叉查找树中的一个结点,x结点包含关键字key,结点x的key值计为key[x]。如果y是x的左子树中的一个结点,则key[y]<=key[x];如果y是x的右子树的一个结点,则key[y]>=key[x]

    在这里插入图片描述
    二叉查找树的基本性质:

    1. 若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值。
    2. 任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
    3. 任意结点的左、右子树也分别为二叉查找树。
    4. 没有键值相等的结点。
    • 代码实现

    Node:

    package priv.qcy.tree;
    
    public class Node {
    	public int value;// 数据域
    	public Node left, right;
    
    	public Node(Node left, Node right, int value) {
    		super();
    		this.value = value;
    		this.left = left;
    		this.right = right;
    	}
    
    	public Node() {
    	}
    
    	public Node(int value) {
    		this(null, null, value);
    	}
    
    	public int getValue() {
    		return value;
    	}
    
    	public void setValue(int value) {
    		this.value = value;
    	}
    
    	public Node getLeft() {
    		return left;
    	}
    
    	public void setLeft(Node left) {
    		this.left = left;
    	}
    
    	public Node getRight() {
    		return right;
    	}
    
    	public void setRight(Node right) {
    		this.right = right;
    	}
    
    }
    
    

    BinarySortTree:

    package priv.qcy.tree;
    
    import java.util.Stack;
    
    public class BinarySortTree {
    
    	private Node root = null;
    
    	/** 查找二叉排序树中是否有key值 */
    	public boolean searchBST(int key) {
    		Node pNode = root;
    		while (pNode != null) {
    			if (key == pNode.getValue()) {
    				return true;
    
    			} else if (key < pNode.getValue()) {
    				pNode = pNode.getLeft();
    
    			} else {
    				pNode = pNode.getRight();
    			}
    
    		}
    		return false;
    
    	}
    
    	/** 向二叉排序树中插入结点 */
    	public void insertBST(int key) {
    		Node pNode = root;
    		Node prev = null;
    		while (pNode != null) {
    			prev = pNode;
    			if (key < pNode.getValue()) {
    				pNode = pNode.getLeft();
    			} else if (key > pNode.getValue()) {
    				pNode = pNode.getRight();
    			} else {
    				return;
    			}
    		}
    
    		if (root == null) {
    			root = new Node(key);
    
    		} else if (key < prev.getValue()) {
    			prev.setLeft(new Node(key));
    
    		} else {
    			prev.setRight(new Node(key));
    		}
    
    	}
    
    	/**
    	 * 删除二叉排序树中的结点 分为三种情况:(删除结点为*p ,其父结点为*f) (1)要删除的*p结点是叶子结点,只需要修改它的双亲结点的指针为空
    	 * (2)若*p只有左子树或者只有右子树,直接让左子树/右子树代替*p (3)若*p既有左子树,又有右子树
    	 * 用p左子树中最大的那个值(即最右端S)代替P,删除s,重接其左子树
    	 */
    	public void deleteBST(int key) {
    		deleteBST(root, key);
    	}
    
    	private boolean deleteBST(Node node, int key) {
    		if (node == null)
    			return false;
    		else {
    			if (key == node.getValue()) {
    				return delete(node);
    			} else if (key < node.getValue()) {
    				return deleteBST(node.getLeft(), key);
    			} else {
    				return deleteBST(node.getRight(), key);
    			}
    		}
    	}
    
    	private boolean delete(Node node) {
    		Node temp = null;
    		/**
    		 * 右子树空,只需要重接它的左子树 如果是叶子结点,在这里也把叶子结点删除了
    		 */
    		if (node.getRight() == null) {
    			temp = node;
    			node = node.getLeft();
    		}
    		/** 左子树空, 重接它的右子树 */
    		else if (node.getLeft() == null) {
    			temp = node;
    			node = node.getRight();
    		}
    		/** 左右子树均不为空 */
    		else {
    			temp = node;
    			Node s = node;
    			/** 转向左子树,然后向右走到“尽头” */
    			s = s.getLeft();
    			while (s.getRight() != null) {
    				temp = s;
    				s = s.getRight();
    			}
    			node.setValue(s.getValue());
    			if (temp != node) {
    				temp.setRight(s.getLeft());
    			} else {
    				temp.setLeft(s.getLeft());
    			}
    		}
    		return true;
    	}
    
    	/**
    	 * 中序非递归遍历二叉树 获得有序序列
    	 */
    
    	public void dlrTraverse() {
    
    		Stack<Node> stack = new Stack<Node>();
    		Node node = root;
    		while (node != null || !stack.isEmpty()) {
    			while (node != null) {
    
    				stack.push(node);
    				node = node.getLeft();
    
    			}
    			node = stack.pop();
    			System.out.print(node.getValue() + "  ");
    			node = node.getRight();
    
    		}
    		System.out.println();
    
    	}
    
    	public static void main(String[] args) {
    		BinarySortTree bst = new BinarySortTree();
    		/** 构建的二叉树没有相同元素 */
    		int[] num = { 45, 12, 37, 24, 3, 53, 100, 61, 55, 90, 78 };
    
    		for (int i = 0; i < num.length; i++) {
    			bst.insertBST(num[i]);
    		}
    
    		bst.dlrTraverse();
    		System.out.println(bst.searchBST(37));
    
    		System.out.println("-------------------------------");
    		bst.deleteBST(12);
    		bst.dlrTraverse();
    		System.out.println(bst.searchBST(12));
    	}
    
    }
    

    作为个人学习复习记录,方便复习!!

    展开全文
  • 数据结构之二叉树 一种非线性数据结构 树(森林) 四种表示方法 树形表示法 嵌套集合表示法 凹入表表示法 广义表表示法 二叉树 五种基本形态 空二叉树 单结点的二叉树 右子树为空的...

    数据结构之二叉树

    • 一种非线性数据结构
    1. 树(森林)
      1. 四种表示方法
        1. 树形表示法
        2. 嵌套集合表示法
        3. 凹入表表示法
        4. 广义表表示法
    2. 二叉树
      1. 五种基本形态
        1. 空二叉树
        2. 单结点的二叉树
        3. 右子树为空的二叉树
        4. 左子树为空的二叉树
        5. 左右子树均非空的二叉树
      2. 两种特殊的二叉树
        1. 满二叉树:一颗二叉树的深度为k,则其有2^k-1个节点。
        2. 完全二叉树:先把前面的节点填满才能填后面的。满二叉树是完全二叉树的特例。
      3. 遍历二叉树
    3. 树形结构的存储方式:链式存储和顺序存储
    4. 线索二叉树
      1. 堆的构造
      2. 堆的插入与删除
    5. 哈夫曼树:一类带权路径长度最短的树。

    几种树的名称:多叉树、二叉树、二叉排序树、完全二叉树、完全二叉排序树、平衡二叉树、平衡二叉排序树(AVL树)

    满二叉树是完全二叉树中的一种特殊情况;堆是完全二叉树中的一种特殊情况。完全二叉树是平衡二叉树中的一种。

    二叉树的性质:

    1. 在二叉树第i层上至多有2^(i-1)个节点(i>=1)
    2. 深度为k的二叉树至多有2^k-1个节点
    3. 对任何一棵二叉树T,设n_0、n_2分别是叶节点的个数和度为2的节点的个数,则有n_0=n_2+1。
    4. 具有n个节点的完全二叉树的深度为「log2(n)」+1。(向下取整)
    5. 对于一棵有n个节点的完全二叉树,其任何一个编号为i的节点(1<=i<=n),都有以下结果:
      1. 关于父节点:
        1. 若i=1,则节点i是根节点,无父节点;
        2. 若i>i,则节点i的父节点是节点「i/2」。
      2. 对于左子节点:
        1. 若2i<n,则节点 i 的左子节点是2i;
        2. 若2i>n,则节点 i 无左子节点。
      3. 对于右子节点:
        1. 若2i+1<n,则节点 i 的右子节点是2i+1;
        2. 若2i+1>n,则节点 i 无右子节点。

    二叉树的存储方式:

    • 顺序存储结构:适合完全二叉树;完全二叉树可用一维数组依次存储它的各节点。
    • 链式存储结构:对于一般二叉树(非完全二叉树),比较适合使用一种二叉链表结构(非线性链表)来存储;在这种链表中,每个节点至少包含3个域:数据域和左、右指针域。

    二叉树的遍历

    1. 前序:即先根遍历(整棵树的根节点在最前面),遍历顺序为:根—左子树—右子树;按照这种顺序遍历,直至没有子节点为止。
    2. 中序:即中根遍历,遍历顺序为:左子树—根—右子树;
    3. 后序:即后根遍历(整棵树的根节点在最后面),遍历顺序为:左子树—右子树—根

    在编程实现时,前三种遍历需要借助递归实现。

    1. 按层遍历:从根节点开始逐层向下遍历,直至最后一层。对于同一层的节点,由左向右遍历。

    树的存储结构:

    1. 父节点表示法:除根节点外每个节点都有一个指向其父节点的指针,而不要求每个节点具有指向子节点的指针。这种表示法只需要用一维数组来存储树的有关信息。
    2. 子节点表示法
    3. 树的子节点-父节点表示法
    4. 子节点-兄弟表示法:又称为二叉链表表示法,以二叉链表的形式作为树的存储结构。

    二叉排序树:见百度百科

    二叉排序树或者是一棵空树,或者是具有下列性质的二叉树

    1. 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    2. 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    3. 左、右子树也分别为二叉排序树;
    4. 没有键值相等的节点。

    几种特殊的二叉树:

    • AVL树,即(严格)平衡二叉排序树,满足以下性质:
    1. 它的左子树和右子树的深度之差的绝对值不超过1
    2. 它的左、右子树都是平衡二叉排序树。
    1. 堆中某个节点的值总是不大于或不小于其父节点的值;

    2. 堆总是一棵完全二叉树。

    根节点(堆顶元素)最大的堆叫做最大(值)堆或最大根堆,根节点最小的堆叫做最小(值)堆或最小根堆。

    B-树:多叉平衡查找树,适合在外存(如磁盘文件)进行数据存储和查找。

     

     

    展开全文
  • 数据结构之二叉树的创建

    万次阅读 多人点赞 2018-02-24 15:43:59
    创建二叉树 二叉树不仅比通用树结构简练,而且同时拥有通用树相同的操作。要想创建二叉树,首先就得了解一下二叉树的存储结构。已知二叉树的存储结构分为顺序存储结构和链式存储结构。其中链式存储结构又分为二叉...

    文章开头首先要感谢一下国嵌嵌入式教育的工作者们。

    创建二叉树 

    二叉树不仅比通用树结构简练,而且同时拥有通用树相同的操作。要想创建二叉树,首先就得了解一下二叉树的存储结构。已知二叉树的存储结构分为顺序存储结构和链式存储结构。其中链式存储结构又分为二叉链表和三叉链表。

    1. 顺序存储结构:

    按照顺序存储结构的定义,在此约定用一组地址连续的存储单元一次自上而下、自左至右存储完全二叉树上的节点元素,即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。如下表1所示为图1所示的完全二叉树的顺序存储结构:

      图1

    表1

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    对于一般二叉树,则将其每一个结点与完全二叉树的结点相对照,存储在一维数组的相应分量中,如下表2所示图2所示的非完全二叉树的顺序存储结构::

      图2

    表2

    1

    2

    3

    4

    5

    0

    6

    0

    7

    8

    图中“0”表示不存在此结点。由此可见顺序存储结构仅适用于完全二叉树。因为,在最坏的情况下,一个深度为k且只有k个结点的单枝树(树中不存在度为2的结点)却需要长度为2k-1的一维数组。造成存储内存的浪费。

    链式存储结构:

    设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义得知,二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成,则表示二叉树的链表中的结点至少包含3个域:数据域和左、右指针域。如下所示:

    Lchid

    Data

    Rchild

    有时,为了便于找到结点的双亲,则还可在结点结构中增加一个指向其双亲结点的指针域,如下所示:

    Lchild

    Data

    Parent

    Rchild

    利用这两种结点结构所得的二叉树的存储结构分别称之为二叉链表三叉链表。链表的头指针指向二叉树的根结点。因此,我们可知在含有n个节点的二叉链表中有n+1个空链域用于存放二叉树结点。到此,我们应该明白可以通过单链表的实现思想来创建二叉树。单链表内容参考单链表C语言实现

    我们接下来讲一下如何通过二叉链表链式存储结构对二叉树进行操作,其重点就是如何在二叉树中定位结点的位置?那么如何定位呢?

    现实生活中我们总会遇到问路的情况,指路的人一般都会说直走、到哪个路口左拐,到哪个路口右拐。这就让我们联想到二叉树的结点是否可以类比成现实中的路口,它的两个子树是否可以当做左拐或右拐呢?

    因此,前辈们想出了指路法定位结点:


    指路法通过根结点与目标结点的相对位置进行定位,指路法可以避开二叉树递归的性质线性定位。

    思想:在C语言中可以利用bit位进行指路。。。



    用结构体来定义二叉树中的指针域,二叉树的头结点与数据域也可以用结构体实现。

    二叉树的重点操作是定位,下面我们看一下定位操作:


    位的关键技巧:

    1.利用二进制中的0和1分别表示left和right;

    2.位运算是实现指路法的基础。

    至此,我们就可以来实现二叉树的相关操作了,上代码。

    首先定义相关结构体及其他变量

    #define BT_LEFT 0            //  左边
    #define BT_RIGHT 1           //  右边
    // 定义新数据类型,用于封装函数
    typedef void BTree;
    typedef unsigned long long BTPos;
    // 定义二叉树左右指针结构体
    typedef struct _tag_BTreeNode BTreeNode;
    struct _tag_BTreeNode
    {
        BTreeNode* left;         // 二叉树左结点指针
        BTreeNode* right;        // 二叉树右结点指针
    };
    
    // 定义二叉树根结点结构体
    typedef struct _tag_BTree TBTree;
    struct _tag_BTree
    {
        int count;                // 记录二叉树结点个数
        BTreeNode* root;          // 二叉树结点指针结构体,指向根结点
    };
    1.创建二叉树
    // 创建二叉树
    BTree* BTree_Create() // O(1)
    {
        // 定义二叉树结点结构体变量,并申请内存
        TBTree* ret = (TBTree*)malloc(sizeof(TBTree));
        // 申请成功,初始化二叉树为空树
        if( ret != NULL )
        {
            ret->count = 0;
            ret->root = NULL;
        }
        
        return ret;
    }

    创建二叉树比较简单,等同于简单的单链表创建方法。所以销毁和清空二叉树也会单链表的操作雷同。

    2.销毁与清空单链表

    // 销毁二叉树
    void BTree_Destroy(BTree* tree) // O(1)
    {
        free(tree);       // 释放内存
    }
    // 清空二叉树
    void BTree_Clear(BTree* tree) // O(1)
    {
        // 定义二叉树结点结构体变量,强制转换入口参数
        TBTree* btree = (TBTree*)tree;
        // 参数合法性OK,将二叉树置为空树
        if( btree != NULL )
        {
            btree->count = 0;
            btree->root = NULL;
        }
    }

    3.插入结点

    插入结点是二叉树操作的重点,代码如下:

    // 在二叉树指定位置pos插入结点node
    // pos:定位的方向,二进制:0表示左,1表示右
    // count:定位次数,移动指针次数
    // flag:插入方向 BT_LEFT or BT_RIGHT
    int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag) // O(n) 
    {
        // 定义二叉树结点结构体变量,强制转换入口参数
        TBTree* btree = (TBTree*)tree;    
        // 入口参数合法性检查,插入的二叉树不为空,插入的结点不为空,插入方向正确
        int ret = (btree != NULL) && (node != NULL) && ((flag == BT_LEFT) || (flag == BT_RIGHT));
        int bit = 0;
        // 入口参数合法性ok
        if( ret )
        {
        	// 定义二叉树左右指针结构体临时变量
            BTreeNode* parent = NULL;
        	// 定义二叉树左右指针结构体变量,存放当前结点地址
            BTreeNode* current = btree->root;
            // 初始化插入结点的左右指针地址,默认为NULL
            node->left = NULL;
            node->right = NULL;
            // 开始定位  定位次数不为零,插入的位置不是根结点
            while( (count > 0) && (current != NULL) )
            {
                // 取定位方向参数最右边bit位用于判断左右
                bit = pos & 1;
                pos = pos >> 1;
                // 临时变量更新当前指针,保存插入结点位置的双亲指针
                parent = current;
                // 左边,向左移动指针
                if( bit == BT_LEFT )
                {
                    current = current->left;        // 将当前结点指针指向左边子结点指针
                }
                // 右边,向右移动指针
                else if( bit == BT_RIGHT )
                {
                    current = current->right;       // 将当前结点指针指向右边子结点指针
                }
                // 定位次数减1
                count--;
            }
            // 定位完成后,判断待插入结点的插入位置
            // 左边
            if( flag == BT_LEFT )
            {
                node->left = current;           // 将带插入结点的左指针指向当前结点
            }
            // 右边
            else if( flag == BT_RIGHT )
            {
                node->right = current;          // 将待插入结点的右指针指向当前结点
            }
            // 当前结点指针不为空,即不是根结点
            if( parent != NULL )
            {
                // 左边
                if( bit == BT_LEFT )
                {
                    parent->left = node;         // 将插入结点位置的双亲指针的左指针指向待插入结点
                }
                // 右边
                else if( bit == BT_RIGHT )
                {
                    parent->right = node;        // 将插入结点位置的双亲指针的右指针指向待插入结点
                }
            }
            // 插入的是首结点,即根结点
            else
            {
                btree->root = node;              // 将根结点指向待插入结点
            }
            // 二叉树结点个数加1
            btree->count++;
        }
        
        return ret;
    }

    通过上面的代码,我们发现二叉树的插入与单链表的参入操作实现方式基本雷同,不同的就是二叉树指针分左右,双指针操作,而单链表操作的指针只有一个next。插入的重点是先根据参数定好位置同时时刻更新找到的新位置,然后根据插入的方向将找到的位置的左或右左右指针指向要插入的结点地址,将要插入的结点地址的左右指针指向相对应的原来位置的左右指针位置。

    4.显示二叉树

    插入的二叉树,就要验证一下插入的是否正确,所以我们通过二叉树的显示函数来显示二叉树的元素,来验证插入的正确性。代码如下:

    // 显示二叉树
    void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div) // O(n)
    {
    	  // 定义二叉树结点结构体变量,强制转换入口参数
        TBTree* btree = (TBTree*)tree;
        // 合法性检查OK,调用显示递归函数
        if( btree != NULL )
        {
            recursive_display(btree->root, pFunc, 0, gap, div);
        }
    }

    同通用树一样,二叉树的显示函数也需要递归来实现,递归实现代码如下:

    // 显示递归函数
    static void recursive_display(BTreeNode* node, BTree_Printf* pFunc, int format, int gap, char div) // O(n)
    {
        int i = 0;
        // 合法性检查OK
        if( (node != NULL) && (pFunc != NULL) )
        {
        	// 打印格式符
            for(i=0; i<format; i++)
            {
                printf("%c", div);
            }
            // 打印内容
            pFunc(node);
            
            printf("\n");
            // 存在左子树结点或存在右子树结点
            if( (node->left != NULL) || (node->right != NULL) )
            {
     
                recursive_display(node->left, pFunc, format + gap, gap, div);      // 调用递归函数打印左子树结点
                recursive_display(node->right, pFunc, format + gap, gap, div);     // 调用递归函数打印右子树结点
            }
        }
        // 根结点为空
        else
        {    	  
        	  // 打印格式符
            for(i=0; i<format; i++)
            {
                printf("%c", div);
            }
            printf("\n");
        }
    }

    与通用树不同的地方就是二叉树需要分左右显示。

    5.删除指定结点

    // 删除指定位置的结点
    BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count) // O(n)
    {
        // 定义二叉树结点结构体变量,强制转换入口参数
        TBTree* btree = (TBTree*)tree;
        // 定义返回变量
        BTreeNode* ret = NULL; 
        int bit = 0;    
    	  // 入口参数合法性检查ok
        if( btree != NULL )
        {
        	  // 定义二叉树左右指针结构体临时变量
            BTreeNode* parent = NULL;
        	  // 定义二叉树左右指针结构体变量,存放当前结点地址
            BTreeNode* current = btree->root;        
            // 开始定位  定位次数不为零,删除的位置不是根结点
            while( (count > 0) && (current != NULL) )
            {
                // 取定位方向参数最右边bit位用于判断左右
                bit = pos & 1;
                pos = pos >> 1;
                
                // 临时变量更新当前指针,保存删除结点位置的双亲指针
                parent = current;            
                // 左边,向左移动指针
                if( bit == BT_LEFT )
                {
                    current = current->left;         // 将删除结点位置的双亲指针的左指针指向待删除结点
                }
                // 右边,向右移动指针
                else if( bit == BT_RIGHT )
                {
                    current = current->right;        // 将删除结点位置的双亲指针的右指针指向待删除结点
                }
                // 定位次数减1             
                count--;
            }        
            // 当前结点指针不为空,即不是根结点
            if( parent != NULL )
            {
                // 左边
                if( bit == BT_LEFT )
                {
                    parent->left = NULL;         // 将结点左子树位置指向空指针,即删除左结点
                }
                // 右边
                else if( bit == BT_RIGHT )
                {
                    parent->right = NULL;        // 将结点右子树位置指向空指针,即删除右结点
                }
            }
            // 删除的是首结点,即根结点
            else
            {
                btree->root = NULL;              // 将根结点指向空指针,即删除所有结点
            }
            // 返回删除元素结点
            ret = current;
            // 更新二叉树结点个数,结点个数减去删除的结点个数
            btree->count = btree->count - recursive_count(ret);
        }
        
        return ret;
    }

    删除结点的操作重点和插入一样,首先通过参数定位到要删除的结点,然后根据要删除的方向将该结点的左或右指针指向NULL即可。需要主要的是二叉树的数量更新不是单单的减1就行的,这得需要根据删除的结点来计算出该结点相应子树下的所有结点个数,然后减去这个个数才行btree->count = btree->count - recursive_count(ret);
    ,所以我们同个一个递归函数求结点个数。递归函数代码如下:

    // 求二叉树结点子树结点个数
    static int recursive_count(BTreeNode* root) // O(n)
    {
        int ret = 0;
        // 合法性检查ok
        if( root != NULL )
        {
            ret = recursive_count(root->left) + 1 + recursive_count(root->right);    // 调用递归函数计算个数
        }
        // 返回个数
        return ret;
    }

    6.获取指定结点

    // 获取指定位置的结点
    BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count) // O(n)
    {
        // 定义二叉树结点结构体变量,强制转换入口参数
        TBTree* btree = (TBTree*)tree;
        // 定义返回变量
        BTreeNode* ret = NULL; 
        int bit = 0;
        
        // 入口参数合法性检查ok
        if( btree != NULL )
        {
        	// 定义二叉树左右指针结构体变量,存放当前结点地址
            BTreeNode* current = btree->root;        
            // 开始定位  定位次数不为零,删除的位置不是根结点
            while( (count > 0) && (current != NULL) )
            {
                // 取定位方向参数最右边bit位用于判断左右
                bit = pos & 1;
                pos = pos >> 1;
                
                // 左边,向左移动指针
                if( bit == BT_LEFT )
                {
                    current = current->left;
                }
                // 右边,向右移动指针
                else if( bit == BT_RIGHT )
                {
                    current = current->right;
                }
                
                // 定位次数减1   
                count--;
            }
            
            ret = current;
        }
        
        return ret;
    }

    获取指定位置的结点,首先就是定位置到要获取的位置,然后返回该结点的地址即可。

    7.获取根结点

    // 获取根结点
    BTreeNode* BTree_Root(BTree* tree) // O(1)
    {
        // 定义二叉树结点结构体变量,强制转换入口参数
        TBTree* btree = (TBTree*)tree;
        // 定义返回变量
        BTreeNode* ret = NULL;
        // 入口参数合法性检查ok,返回根结点地址
        if( btree != NULL )
        {
            ret = btree->root;
        }
        
        return ret;
    }

    获取根结点就是获取二叉树的头结点,直接返回头结点地址即可。

    8.获取二叉树的高度(深度)

    // 获取二叉树高度
    int BTree_Height(BTree* tree) // O(n)
    {
        // 定义二叉树结点结构体变量,强制转换入口参数
        TBTree* btree = (TBTree*)tree;
        // 定义返回变量
        int ret = 0;    
        // 入口参数合法性检查ok,调用递归函数求二叉树高度
        if( btree != NULL )
        {
            ret = recursive_height(btree->root);
        }
        // 返回二叉树高度
        return ret;
    }

    和通用树一样,二叉树的高度获取也需要递归来实现,递归函数代码如下:

    // 求二叉树高度递归函数
    static int recursive_height(BTreeNode* root) // O(n)
    {
        // 定义返回值变量
        int ret = 0;
        // 入口参数合法性检查OK
        if( root != NULL )
        {
            int lh = recursive_height(root->left);       // 求左子树高度
            int rh = recursive_height(root->right);      // 求右子树高度
            // 求左右子树高度最大值
            ret = ((lh > rh) ? lh : rh) + 1;
        }
        // 返回二叉树高度
        return ret;
    }

    分别求左右子树的高度,然后比较出最大值返回。

    9.获取二叉树的度

    // 获取二叉树度
    int BTree_Degree(BTree* tree) // O(n)
    {
    	  // 定义二叉树结点结构体变量,强制转换入口参数
        TBTree* btree = (TBTree*)tree;
        // 定义返回变量
        int ret = 0;    
    	  // 入口参数合法性检查ok,调用求二叉树度递归函数
        if( btree != NULL )
        {
            ret = recursive_degree(btree->root);
        }
        // 返回二叉树的度
        return ret;
    }
    和通用树一样,二叉树的度获取也需要递归来实现,递归函数代码如下:
    // 求二叉树度递归函数,最大度为2
    static int recursive_degree(BTreeNode* root) // O(n)
    {
    	  // 定义返回值变量
        int ret = 0;    
        // 入口参数合法性检查OK
        if( root != NULL )
        {
        	  // 左子树结点不为空,度加1
            if( root->left != NULL )
            {
                ret++;
            }        
        	  // 右子树结点不为空,度加1
            if( root->right != NULL )
            {
                ret++;
            }
            // 度为1,调用递归函数求其他结点度
            if( ret == 1 )
            {
                int ld = recursive_degree(root->left);       // 求左子树结点的度
                int rd = recursive_degree(root->right);      // 求右子树结点的度
                // 求左子树结点度的最大值
                if( ret < ld )
                {
                    ret = ld;
                }            
                // 求右子树结点度的最大值
                if( ret < rd )
                {
                    ret = rd;
                }
            }
        }
        // 返回度
        return ret;
    }

    因为二叉树的度最大也就是2,所以只有在当前求得度为1时才需要调用递归函数来求其他子树结点的度。

    验证代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include "BTree.h"
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    // 定义二叉树数据域结构体
    struct Node
    {
        BTreeNode header;
        char v;
    };
    // 定义打印内容函数
    void printf_data(BTreeNode* node)
    {
        if( node != NULL )
        {
            printf("%c", ((struct Node*)node)->v);
        }
    }
    
    int main(int argc, char *argv[])
    {
    	  // 创建二叉树
        BTree* tree = BTree_Create();
        // 定义要插入结点元素
        struct Node n1 = {{NULL, NULL}, 'A'};
        struct Node n2 = {{NULL, NULL}, 'B'};
        struct Node n3 = {{NULL, NULL}, 'C'};
        struct Node n4 = {{NULL, NULL}, 'D'};
        struct Node n5 = {{NULL, NULL}, 'E'};
        struct Node n6 = {{NULL, NULL}, 'F'};    
        // 插入结点元素
        BTree_Insert(tree, (BTreeNode*)&n1, 0, 0, 0);
        BTree_Insert(tree, (BTreeNode*)&n2, 0x00, 1, 0);
        BTree_Insert(tree, (BTreeNode*)&n3, 0x01, 1, 0);
        BTree_Insert(tree, (BTreeNode*)&n4, 0x00, 2, 0);
        BTree_Insert(tree, (BTreeNode*)&n5, 0x02, 2, 0);
        BTree_Insert(tree, (BTreeNode*)&n6, 0x02, 3, 0);
        // 打印相应提示内容
        printf("Height: %d\n", BTree_Height(tree));
        printf("Degree: %d\n", BTree_Degree(tree));
        printf("Count: %d\n", BTree_Count(tree));
        printf("Position At (0x02, 2): %c\n", ((struct Node*)BTree_Get(tree, 0x02, 2))->v);
        printf("Full Tree: \n");
        // 显示二叉树
        BTree_Display(tree, printf_data, 4, '-');
        // 测试删除结点功能
        BTree_Delete(tree, 0x00, 1);   
        // 打印相应提示内容
        printf("After Delete B: \n");
        printf("Height: %d\n", BTree_Height(tree));
        printf("Degree: %d\n", BTree_Degree(tree));
        printf("Count: %d\n", BTree_Count(tree));
        printf("Full Tree: \n");    
        // 显示删除结点后的二叉树
        BTree_Display(tree, printf_data, 4, '-');
        
        // 测试清空二叉树功能
        BTree_Clear(tree);    
        // 打印相应提示内容
        printf("After Clear: \n");
        printf("Height: %d\n", BTree_Height(tree));
        printf("Degree: %d\n", BTree_Degree(tree));
        printf("Count: %d\n", BTree_Count(tree));    
        // 显示清空后的二叉树
        BTree_Display(tree, printf_data, 4, '-');
        // 销毁二叉树
        BTree_Destroy(tree);
        
    	return 0;
    }
    

    通过理解相关实现代码,我们发现通过指路法可以方便的定位二叉树中的结点,基于指路法的二叉树在插入,删除和获取操作的实现细节上与单链表相似。

    整体实现代码:二叉树C语言实现代码
    展开全文
  • 数据结构之二叉树排序算法】

    千次阅读 2020-08-24 11:50:42
    数据结构之二叉树二叉树是一个非常重要的树形结构,它的存储结构和运算都较为简单,而树也很容易转换成二叉树,本文主要探讨二叉树的遍历,一共分为前序、中序和后序三种遍历方式,使用递归进行遍历代码简介...

    二叉树是一个非常重要的树形结构,它的存储结构和运算都较为简单,而树也很容易转换成二叉树,本文主要探讨二叉树的遍历,一共分为前序、中序和后序三种遍历方式,使用递归进行遍历代码简介易懂。下面先介绍递归前序遍历及非递归方式的中序和后序遍历。

    二叉树遍历的定义

    1. 先序遍历。
      如果二叉树为空,则空操作;否则依次执行以下操作。
    • 访问根结点
    • 先序遍历根结点的左子树
    • 先序遍历根结点的右子树
    1. 中序遍历
      如果二叉树为空,则空操作;否则依次执行以下操作。
    • 中序遍历根结点的左子树
    • 访问根结点
    • 中序遍历根结点的右子树
    1. 后序遍历
      如果二叉树为空,则空操作;否则依次执行以下操作。
    • 后序遍历根结点的左子树
    • 后序遍历根结点的右子树
    • 访问根节点

    二叉树例图
    与本文定义类型不符。

    二叉树的类型描述

    typedef struct BTNode
    {
    	int elem;
    	struct BTNode *left,*right;
    }*BinTree;
    

    【先序遍历】

    void PreOrder(BinTree root)
    {
    	if(root!=NULL)
    	{
    		printf("%4d",root->elem);  /*访问根结点*/
    		PreOrder(root->left);      /*先序遍历根结点的左子树*/
    		PreOrder(root->right);     /*先序遍历根结点的右子树*/
    	}
    }
    

    中序遍历和后续递归遍历
    在此不做过多的介绍,那就开始上非递归遍历吧。

    【非递归中序遍历】
    二叉树中序遍历的非递归算法的主要思想是令变量root为指向根节点的指针,从根结点开始遍历。显然,第一次遇到根结点并不进行访问,而是入栈,因为此时root所指根结点及其右子树尚未被访问,必须将root保存在栈中,以便在访问完左子树后,从栈中取出root,对其所指根结点及其右子树进行访问。在root进栈后,就中序遍历它的左子树,即把root的左孩子赋给root,沿左链走下去,直到左链为空,左子树遍历完毕,此时节点出站,把栈定元素赋给root,这是第二次遇到该节点,此时其左子树已经访问完毕,按照中序遍历的定义,访问根结点(打印该节点的信息),随后中序遍历其右子树,即把root的右孩子赋给root,重复上述过程,直至root为空栈则结束。
    其大致概括为:

    1. 入栈后检测左边。出栈后检测右边。
    2. 非递归中序遍历的特点是先进栈根节点,然后在判断有没有左节点
    3. 如果有继续进栈,如果为空,出栈,出栈后判断有没有右节点
    4. 如果有右节点进栈。然后以此类推。进栈的动作是连续的(只要有左节点就一直进栈),而出栈
      的动作只有一次。因为出栈后会判断有没有右节点,如果有且该节点不为空会重复上述过程,否继续出栈。

    定义栈

    #define MaxSize
    typedef struct
    {
    	BinTree elem[MaxSize];
    	int top;
    }SeqStack;
    

    中序遍历非递归实现算法描述:

    void InOrder(BinTree root)
    {
    	SeqStack s;
    	s.top=-1;
    	do
    	{
    		while(root!=NULL)
    		{
    			s.top++;
    			if(s.top>=MaxSize-1)
    			{
    				printf("栈已经满了!\n");
    				return ;
    			}
    			else
    			{
    				s.elem[s.top]=root;
    				root=root->left;
    			}
    		}
    		if(s.top!=-1)
    		{
    			root=s.elem[s.top];
    			s.top--;
    			printf("\n%4d",root->elem);
    			root=root->right;
    		}
    	}while((s.top!=-1)||(root!=NULL));
    	
    }
    

    【非递归后续遍历】

    1. 设置栈顶为-1,当根节点不为空时,进栈并设置该节点的访问次数为零,再次判断有没有左元素,如果有继续进栈。(左元素为空结束)
    2. 出栈,退出之后判断栈是否为空,不为空时取出栈顶元素。判断是否有右孩子或者被访问的次数是否为零。
    3. 如果没有右孩子且被访问次数为1时出栈。否则(也就是说有右孩子并且访问次数为零时)设置该节点的被访问次数为1.再把右孩子地址赋值给该节点。
    4. 判断该节点是否为空。不为空时进栈并设置该节点的访问次数为零。访问左元素。依次循环(结合代码)
    void PostOrder(BinTree root)
    {
    	SeqStack s;
    	s.top=-1;
    	while(root!=NULL)
    	{
    		s.top++;
    		if(s.top==MaxSize-1)
    		{
    			printf("栈已经满了!\n");
    			printf("Error");
    		}
    		else
    		{
    			root->count=0;
    			s.elem[s.top]=root;
    			root=root->left;
    		}
    	}
    	while(s.top!=-1)
    	{
    		root=s.elem[s.top];
    		if(root->right==NULL||root->count==1)
    		{
    			printf("\n%c",root->elem);
    			s.top--;
    		}
    		else if(root->right!=NULL&&root->count!=1)
    		{
    			root->count=1;
    			root=root->right;
    			while(root!=NULL)
    			{
    				s.top++;
    				s.elem[s.top]=root;
    				root->count=0;
    				root=root->left;
    			}
    		}
    	}
    }
    

    前序遍历:A B D E C F
    中序遍历:D B E A F C
    后序遍历:D E B F C A

    展开全文
  • 数据结构实验之二叉树二:遍历二叉树 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 已知二叉树的一个按先序遍历输入的字符序列,如abc,,de,g,,f,,, (其中,表示空结点)。请...
  • 数据结构之 二叉树(C语言实现)

    万次阅读 多人点赞 2017-03-28 20:31:29
    数据结构之 二叉树(C语言实现)1. 二叉树的定义==二叉树(Binary Tree)是n(n ≥ 0)个节点有限集合。==当n=0时,称为空二叉树,当n>0时,该集合有一个根节点及互不可交的,分别被称为左子树和右子树的二叉树组成...
  • 数据结构之二叉树(C++)(一)

    千次阅读 2016-09-22 14:32:41
    数据结构之二叉树(一)目录 (Table of Contents)数据结构之二叉树一 树的简单介绍 树和二叉树的术语 树的特点 树的种类 二叉树 二叉树和树的根本区别 二叉树的简单创建 二叉树的遍历 前序遍历 中序遍历 后序遍历 层序...
  • Python数据结构之二叉树

    千次阅读 2013-09-12 22:33:21
    Python数据结构系列之二叉树
  • 每天一点数据结构之二叉树的插入与创建 二叉树的插入: 1.判断树是否为空,如果为空则直接插入当前结点成为根结点 2.若根不为空,则判断是否小于根 3.小于根插入左子树 4.大于根插入右子树 5.以此循环下去,...
  • 二叉树定义及其逻辑表示定义逻辑表示性质 定义及其逻辑表示 定义 一个二叉树是一个又穷的结点集合。...如图所示,写斜二叉树也称为退化二叉树,斜二叉树结构最差,深度达到最大N,它已退化为线性表。在一棵二叉...
  • 数据结构之二叉树及Java实现

    千次阅读 2018-04-18 15:34:34
    链表、栈以及队列都是线性的数据结构,元素存储起来较为简单,元素只存在一个对一个的关系,而树则是一种更为复杂的数据结构,这种结构元素存在一个对多个的关系,一个父节点可以包括多个子节点。二叉树是一种特殊的...
  • 数据结构之二叉树链表

    千次阅读 2015-10-22 13:08:02
     二叉树是n个结点的有限集合,该集合或者为空集(称为空二叉树),或者有一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成  特点:  ①每个结点最多有两棵子树,所以二叉树中不存在度 ...
  • 数据结构之二叉数深度计算原理代码 原理 本质上就是二叉树的遍历过程 分别遍历左右子树,取大的即可 二叉数树深度 = max(左子树深度,右子树深度) + 1 代码 //二叉数深度计算 int treeDepth(BiTree T){ if(T == ...
  • Java数据结构之二叉树的实现

    千次阅读 2016-05-15 10:14:54
    树(Tree)是一种重要的非线性的数据结构,直观的看,它是数据元素(在树中称为节点)按分支关系组织起来的结构。 二叉树(Binary Tree)是每个节点最多有两个子树的有序树。通常子树被称作“左子树”和“右子树...
  • 数据结构之二叉树的代码实现 C语言版

    千次阅读 多人点赞 2019-08-20 11:06:18
    二叉树的创建,三种遍历,求叶子结点树,深度,结点数
  • 二叉树数据结构这门课程中非常重要的知识点,也是最基本的一种树形结构。在二叉树的遍历又是这部分内容的重中重,那么今天就这部分内容和大家做一个分享。所谓二叉树遍历,就是按照某种特定的次序,遍访整个...
  • 数据结构之二叉树建立

    千次阅读 2014-09-23 13:54:47
    typedef struct BiTNode /* 结点结构 */ { TElemType data; /* 结点数据 */ struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree; /* 构造空二叉树T */ Status InitBiTree(BiTree *T) { *T=...
  • 数据结构之二叉树基础(C语言)

    千次阅读 热门讨论 2018-12-20 23:52:11
    树:(Tree) 性质: 子树是不相交的 除了根节点之外,每个节点有且仅有一个节结点 一颗N个结点的树有N-1条边 概念: 结点的度:结点的子树个数 树的度:树的所有结点中最大的...种类:完全二叉树,满二叉树 几个重要...
  • 数据结构之二叉树的遍历

    千次阅读 2018-03-27 20:19:57
    二叉树的遍历:先序遍历: 先访问根节点 再遍历左子树 再遍历右子树中序遍历:中序遍历左子树 再访问根节点 中序遍历右子树后序遍历:中序遍历左子树 中序遍历右子树 ...
  • 数据结构之二叉树深度的求解

    千次阅读 2016-11-10 14:18:22
    题目:二叉树用二叉链表表示,编写求二叉树深度的算法。 答案是: int height(Bitree T) {  if (T==NULL) return 0;  u=height(T->lchild);  v=height(T->rchild);  if (u>n) return
  • 数据结构之二叉树(C语言实现)

    千次阅读 多人点赞 2020-03-29 22:12:19
    此次介绍的二叉树虽是非线性结构的树形结构分支,但在其各个结点遍历的实现上,使用到了栈和队列的特性。 二叉树是一种特殊的线性结构,每个结点最多只有两个分支,称左孩子结点和右孩子结点。更多关于二叉树的特性...
  • 数据结构之二叉树的定义和性质

    千次阅读 2018-02-17 21:26:06
    通过上一节讲解,我们知道通用树结构是采用双亲孩子表示法模型建立的。每个结点都有一个指向其双亲的指针,每个结点都有若干个指向其孩子的指针。如下图:整体实现起来比较复杂,今天我们来讲一下另一种树结构模型:...
  • 在计算机科学中,树(英语:tree)是一种抽象资料型别(ADT)或是实作这种抽象资料型别的数据结构,用来模拟具树状结构性质的资料集合。它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为...
  • 数据结构之二叉树(概念)

    千次阅读 2015-07-19 17:10:54
    树的定义: 树是n个结点的有限集。 n = 0 称为空树。如果n>0,则: (1)有一个特定的称为根的结点,它只有直接后继,但没有直接前驱。...节点:表示树中的元素,包括数据元素的内容及其指向其子树的分支
  • 数据结构之二叉树基础知识总结

    千次阅读 2014-06-02 21:41:09
    树不是线性表,是一种描述非线性层次关系的数据结构。是N个数据结点的集合。   2、基本特征—— 有且仅有一个结点没有直接前驱,那就是根节点; 除了根结点外,其他结点有且仅有一个直接前驱; 每个结点可以...
  • 先序遍历顺序: 先访问根结点,再访问左子树,最后访问右子树 先序序列的排序也是如此,根结点 左子树 右子树   1.结构体   struct BitNode { char data;...2.二叉树先序方式创造     Bi...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 210,837
精华内容 84,334
关键字:

数据结构之二叉树

数据结构 订阅