精华内容
下载资源
问答
  • 树结构大全

    万次阅读 多人点赞 2018-11-10 10:58:38
    文章目录说明树结构的一些基本定义树结构的性质二叉树二叉树的定义满二叉树与完全二叉树二叉树的性质结点定义二叉树的创建二叉树的遍历基于深度遍历二叉树基于层次遍历二叉树(方法一)基于层次遍历二叉树(方法二)...

    说明


    • 主要讲解二叉树及其相关内容
    • 次要说明其他树结构
    • 以后会进行不定期更新

    主要参考以下书籍

    • 程序员面试笔记
    • 慕课网:数据算法与结构
    • 其他…

    树结构的一些基本定义


    示意图

    树

    • 结点的度:结点拥有的子树的数目。eg:结点 A 的度为3
    • 树的度:树种各结点度的最大值。eg:树的度为3
    • 叶子结点:度为 0 的结点。g:E、F、C、G 为叶子结点
    • 孩子结点:一个结点的子树的根节点。eg:B、C、D 为 A 的子结点
    • 双亲结点:B 为 A 的子结点,那么 A 为 B 的双亲结点
    • 兄弟结点:一个双亲结点结点的孩子互为兄弟结点。eg:B、C、D 为兄弟结点
    • 结点的层次:根节点为第一层,子结点为第二层,依次向下递推…eg:E、F、G 的层次均为 3
    • 树的深度:树种结点的最大深度。eg:该树的深度为 3
    • 森林:m 棵互不相交的树称为森林

    树结构的性质


    1. 非空树的结点总数等于树种所有结点的度之和加 1
    2. 度为 K 的非空树的第 i 层最多有 ki-1 个结点(i >= 1)
    3. 深度为 h 的 k 叉树最多有(kh - 1)/(k - 1)个结点
    4. 具有 n 个结点的 k 叉树的最小深度为 logk(n(k-1)+1))

    二叉树(Binary-Tree)


    二叉树的定义

    二叉树是一种特殊的树:它或者为空,或者由一个根节点加上根节点的左子树和右子树组成,这里要求左子树和右子树互不相交,且同为二叉树,很显然,这个定义是递归形式的。

    满二叉树与完全二叉树

    满二叉树: 如果一棵二叉树的任意一个结点或者是叶子结点,或者有两棵子树,同时叶子结点都集中在二叉树的最下面一层上,这样的二叉树称为满二叉树

    完全二叉树: 若二叉树中最多只有最下面两层结点的度小于 2 ,并且最下面一层的结点(叶子结点)都依次排列在该层最左边的位置上,具有这样结构特点的树结构称为完全二叉树。

    在这里插入图片描述

    二叉树的性质

    1. 在二叉树中第 i 层上至多有 2i-1 个结点(i >=1)
    2. 深度为 k 的二叉树至多有 2k-1 个结点(k >=1)
    3. 对于任何一棵二叉树,如果其叶子结点数为 n0 ,度为 2 的结点数为 n2 ,那么 n0 = n2 + 1
    4. 具有 n 个结点的完全二叉树的深度为 log2n + 1

    结点定义

    typedef struct BiTNode{
    	ElemType data;
    	struct BiTNode * lchild, * rchild;
    } BiTNode, *BiTree;
    

    二叉树的创建

    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T) {
        char c;
        scanf("%c", &c);
        if(c == ' ') *T = NULL;
        else {
            *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = c;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    

    二叉树的遍历

    基于深度遍历二叉树

    分为先序(DLR)、中序(LDR)、后序遍历(LRD)

    #include "stdio.h"
    #include "malloc.h"
    
    typedef struct BiTNode {
        char data;   /*结点的数据域*/
        struct BiTNode *lchild, *rchild;   /*指向左孩子和右孩子*/
    } BiTNode, *BiTree;
    
    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T) {
        char c;
        scanf("%c", &c);
        if(c == ' ') *T = NULL;
        else {
            *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = c;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    
    /*前序遍历二叉树*/
    void PreOrderTraverse(BiTree T ) {
        if(T) {  /*递归结束条件,T为空*/
            printf("%3c", T->data); /*访问根结点,将根结点内容输出*/
            PreOrderTraverse(T->lchild);  /*先序遍历T的左子树*/
            PreOrderTraverse(T->rchild);  /*先序遍历T的右子数*/
        }
    }
    
    /*中序遍历二叉树*/
    void InOrderTraverse(BiTree T) {
        if(T) {  /*如果二叉树为空,递归遍历结束*/
            InOrderTraverse(T->lchild);  /*中序遍历T的左子树*/
            printf("%3c", T->data);      /*访问根结点*/
            InOrderTraverse(T->rchild);  /*中序遍历T的右子数*/
        }
    }
    
    /*后序遍历二叉树*/
    void PosOrderTraverse(BiTree T) {
        if(T) {  /*如果二叉树为空,递归遍历结束*/
            PosOrderTraverse(T->lchild);  /*后序遍历T的左子树*/
            PosOrderTraverse(T->rchild);  /*后序遍历T的右子数*/
            printf("%3c", T->data);       /*访问根结点*/
        }
    }
    
    
    int main() {
        BiTree T = NULL;  /*最开始T指向空*/
        printf("Input some characters to create a binary tree\n");
        CreatBiTree(&T);  /*创建二叉树*/
        printf("The squence of preorder traversaling binary tree\n");
        PreOrderTraverse(T); /*先序遍历二叉树*/
        printf("\nThe squence of inorder traversaling binary tree\n");
        InOrderTraverse(T);  /*中序遍历二叉树*/
        printf("\nThe squence of posorder traversaling binary tree\n");
        PosOrderTraverse(T); /*后序遍历二叉树*/
        getchar();
        getchar();
    }
    

    基于层次遍历二叉树

    方法一

    #include "stdio.h"
    
    typedef struct BiTNode {
       char data;   /*结点的数据域*/
       struct BiTNode *lchild, *rchild;   /*指向左孩子和右孩子*/
    } BiTNode, *BiTree;
    
    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T) {
       char c;
       scanf("%c", &c);
       if(c == ' ') *T = NULL;
       else {
          *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
          (*T)->data = c;    /*向根结点中输入数据*/
          CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
          CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
       }
    }
    
    /*遍历二叉树*/
    void PreOrderTraverse(BiTree T ) {
       if(T) {  /*递归结束条件,T为空*/
          printf("%3c", T->data); /*访问根结点,将根结点内容输出*/
          PreOrderTraverse(T->lchild);  /*先序遍历T的左子树*/
          PreOrderTraverse(T->rchild);  /*先序遍历T的右子数*/
       }
    }
    
    void visit(BiTree p) {
       printf("%3c", p->data);
    }
    
    void layerOrderTraverse(BiTree T) {
       BiTree queue[20], p;
       int front, rear;
       if(T != NULL) {
          queue[0] = T;       /*将根结点的指针(地址)入队列*/
          front = -1;
          rear = 0;
          while(front < rear) {   /*当队列不为空时进入循环*/
             p = queue[++front]; /*取出队头元素*/
             visit(p);       /*访问p指向的结点元素*/
             if(p->lchild != NULL) /*将p结点的左孩子结点指针入队列*/
                queue[++rear] = p->lchild;
             if(p->rchild != NULL) /*将p结点的右孩子结点指针入队列*/
                queue[++rear] = p->rchild;
          }
       }
    }
    
    main() {
       BiTree T = NULL;  /*最开始T指向空*/
       printf("Input some characters to create a binary tree\n");
       CreatBiTree(&T);  /*创建二叉树*/
    
       printf("\nThe squence of layerorder traversaling binary tree\n");
       layerOrderTraverse(T);
       getchar();
       getchar();
    }
    

    方法二

    void layerOrderTraverse(BiTree T){
    	BiTree p;
    	queue<BiTree> q;
    	if(T != NULL){
    		q.push(T);
    		while(!q.empty()){
    			p = q.front();
    			q.pop();
    			visit(p);  // 自定义访问操作
    			if(p->lchild != NULL)
    				q.push(p->lchild);
    			if(p->rchild != NULL)
    				q.push(p->rchild);
    		}
    	}
    }
    

    二叉树的深度

    方法一

    #include "stdio.h"
    #include "malloc.h"
    
    typedef struct BiTNode{
        char data;   /*结点的数据域*/
        struct BiTNode *lchild , *rchild;  /*指向左孩子和右孩子*/
    } BiTNode , *BiTree;
    
    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T)
    {
        char c;
        scanf("%c",&c);
        if(c == ' ') *T = NULL;
        else{
           *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = c;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    
    /*计算二叉树的深度*/
    void getDepth(BiTree T,int n,int *level)
    {
       if(T!=NULL)
       {
            if(n> *level)
            {
                *level = n;
            }
            getDepth(T->lchild,n+1,level);
            getDepth(T->rchild,n+1,level);
       }
    }
    
    int getBitreeDepth(BiTree T)
    {
        int level = 0;
        int n = 1;
        getDepth(T,n,&level);
        return level ;
    }
    
    main()
    {
        BiTree T = NULL;    /*最开始T指向空*/
        printf("Input some characters to create a binary tree \n");
        CreatBiTree(&T);    /*创建二叉树*/
        printf("\nThe depth of the binary tree is %d\n",getBitreeDepth(T));
        getchar() ;
    	getchar() ;
    }
    

    方法二

    int getBitreeDepth(BiTree T){
    	int leftHeight, rightHeight, maxHeight;
    	if(T != NULL){
    		leftHeight = getBitreeDepth(T->lchild);  // 计算左子树的深度
    		rightHeight = getBitreeDepth(T->rchild);  // 计算右子树的深度
    		maxHeight = leftHeight > rightHeight ? leftHeight : rightHeight;  // 比较左右子树的深度
    		return maxHeight + 1;  // 返回二叉树的深度
    	else{
    		return 0;
    	}
    }
    

    二叉树叶子结点个数

    #include "string.h" 
    #include "stdio.h" 
    #include "malloc.h"
    
    typedef struct BiTNode{
        char data;   /*结点的数据域*/
        struct BiTNode *lchild , *rchild;  /*指向左孩子和右孩子*/
    } BiTNode , *BiTree;
    
    void CreatBiTree(BiTree *T){
        char c;
        scanf("%c",&c);
        if(c == ' ') *T = NULL;
        else{
           *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = c;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    
    void getLeavesConut (BiTree T,int *count){
        if(T!=NULL && T->lchild==NULL && T->rchild==NULL){   /*访问到叶结点*/
            *count = *count + 1;
        }
        if(T){
            getLeavesConut (T->lchild,count);  /*先序遍历T的左子树*/
            getLeavesConut (T->rchild,count);  /*先序遍历T的右子数*/
        }
    }
    
    int getBiTreeLeavesCount(BiTree T) {
    	int count = 0;				/*在主调函数中定义变量count,初始值为0*/
    	getLeavesConut(T, &count);	/*调用递归函数getLeavesConut计算叶子结点个数*/
    	return count;				/*返回叶子结点个数*/
    }
    
    main()
    {
       BiTree T = NULL;				/*初始化T */
       int count = 0;
       printf("Input some characters to create a binary tree \n");
       CreatBiTree(&T);				/*创建一棵二叉树*/
       getLeavesConut (T,&count);	/*计算二叉树中叶子结点的个数 */
       printf("The number of leaves of BTree are %d\n",count);
       getchar();
       getchar();
    }
    

    二叉排序树(Binary-Sort-Tree)


    什么是二叉排序树

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

    1. 若它的左子树不为空,则左子树上的所有结点的值均小于根结点的值
    2. 若它的右子树不为空,则右子树上的所有结点的值均大于根节点的值
    3. 二叉排序树的左右子树也都是二叉排序树

    在这里插入图片描述

    二叉排序树的查找

    BiTree SearchBST(BiTree T, dataTYpe){
    	if(T == NULL)
    		return NULL;
    	if(T->data == key)
    		return T;
    	if(key < T->data)
    		return SearchBST(T-> lchild, key);
    	else
    		return SearchBST(T-> rchild, key);
    }
    

    最低公共祖先

    在这里插入图片描述

    分析

    从整棵二又排序树的根结点出发,
    当访间的当前结点同时大于给定的两个结点时、沿左指前进;
    当访间的当前结点同时小于給定的两个结点时,沿右指针前进;
    当第一次访问到介于给定的两个结点值之间的那个结点时即是它们的最低公共祖先结点

    然鹅,这个算法并不完善,因为这个算法适用的前提是给定的两个结点分别位于二叉排序树中某个结点的左右子树上

    假设给定的两个结点分别为a和b,并且 a 是 b 的祖先,那么结点 a 和 b 的最低公共祖先就是 a 的父结点,因为 a 的父结点一定也是 b 的祖先,同时该结点也必然是 a 和 b 的最低公共祖先。

    另外,如果给定的 a 或 b 其中一个为根结点的值,那么这种情况是不存在公共最低祖先的,因为根结点没有祖先,所以也应把这种情况考虑进去。

    #include "stdio.h"
    #include "malloc.h"
    #include "string.h"
    
    typedef struct BiTNode{
        int data;   /*结点的数据域*/
        struct BiTNode *lchild;
        struct BiTNode *rchild;  /*指向左孩子和右孩子*/
    } BiTNode , *BiTree;
    
    int findLowestCommonAncestor(BiTree T,int value1, int value2) {
    	BiTree curNode = T;  /*curNode为当前访问结点,初始化为T*/
    	if(T->data == value1 || T->data == value2) {
    		return -1;    /*value1和value2有一个为根结点,因此没有公共祖先,返回-1*/
    	}
    	while(curNode != NULL){
    		if (curNode->data > value1 &&
    			curNode->data > value2 && curNode->lchild->data != value1 &&
    			curNode->lchild->data != value2) {
    /*当前结点的值同时大于value1和value2,且不是value1和value2的父结点*/
    				curNode = curNode->lchild;  
    		} else if (curNode->data < value1 &&
    			curNode->data < value2 && curNode->rchild->data != value1 &&
    			curNode->rchild->data != value2) {
    /*当前结点的值同时小于value1和value2,且不是value1和value2的父结点*/
    				curNode = curNode->rchild;
    		} else {
    			return curNode->data;	/*找到最低公共祖先*/
    		}
    	}
    }
    
    void CreatBiTree(BiTree *T){
        int d;
        scanf("%d",&d);
        if(d == 0) *T = NULL;
        else{
           *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
            (*T)->data = d;    /*向根结点中输入数据*/
            CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
            CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
        }
    }
    
    main()
    {
    	BiTree T;
    	int value1,value2;
    	int ancestorValue;
    	printf("Please create a binary sort tree\n");
    	CreatBiTree(&T);
    	printf("Input two values for searching lowest common ancestor\n");
    	scanf("%d,%d",&value1,&value2);
    	ancestorValue = findLowestCommonAncestor(T,value1,value2);
    	if (ancestorValue != -1) {
    		printf("The  lowest common ancestor is %d\n", ancestorValue);
    	} else {
    		printf("There is no ancestor\n");
    	}
    	getchar();
    }
    

    二叉排序树 VS 二叉堆(Binary-Heap)


    在这里插入图片描述

    两者的相同点与不同点

    相同点

    二叉堆也是一种树结构

    不同点

    1. 任何一个结点都不大于父亲节点(亦即左右结点均不大于父节点)
    2. 必须是一棵完全二叉树(结点必须集中在最左侧),亦即最大堆
    3. 用数组存储二叉堆,原因在于满二叉树的结点索引存在倍数关系

    在这里插入图片描述

    关系描述为:左结点是父节点的 2 倍,右结点为父节点的 2 倍 加 1(根结点的序列为 1)

    二叉堆主要表现为最大堆(Max-Heap),主要涉及以下内容

    最大堆的一些基本操作(Max-Heap)

    • 创建
    • 删除
    • 元素个数
    • 插入
    • 堆顶元素
    • 最大元素
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    template<typename Item>
    class MaxHeap{
    
    private:
        Item *data;
        int count;
        int capacity;
    
        void shiftUp(int k){
            while( k > 1 && data[k/2] < data[k] ){
                swap( data[k/2], data[k] );
                k /= 2;
            }
        }
    
        void shiftDown(int k){
            while( 2*k <= count ){
                int j = 2*k;
                if( j+1 <= count && data[j+1] > data[j] ) j ++;
                if( data[k] >= data[j] ) break;
                swap( data[k] , data[j] );
                k = j;
            }
        }
    
    public:
    
        // 构造函数, 构造一个空堆, 可容纳capacity个元素
        MaxHeap(int capacity){
            data = new Item[capacity+1];
            count = 0;
            this->capacity = capacity;
        }
    
        // 构造函数, 通过一个给定数组创建一个最大堆
        // 该构造堆的过程, 时间复杂度为O(n)
        MaxHeap(Item arr[], int n){
            data = new Item[n+1];
            capacity = n;
    
            for( int i = 0 ; i < n ; i ++ )
                data[i+1] = arr[i];
            count = n;
    
            for( int i = count/2 ; i >= 1 ; i -- )
                shiftDown(i);
        }
    
        ~MaxHeap(){
            delete[] data;
        }
    
        // 返回堆中的元素个数
        int size(){
            return count;
        }
    
        // 返回一个布尔值, 表示堆中是否为空
        bool isEmpty(){
            return count == 0;
        }
    
        // 像最大堆中插入一个新的元素 item
        void insert(Item item){
            assert( count + 1 <= capacity );
            data[count+1] = item;
            shiftUp(count+1);
            count ++;
        }
    
        // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
        Item extractMax(){
            assert( count > 0 );
            Item ret = data[1];
            swap( data[1] , data[count] );
            count --;
            shiftDown(1);
            return ret;
        }
    
        // 获取最大堆中的堆顶元素
        Item getMax(){
            assert( count > 0 );
            return data[1];
        }
    };
    

    最大索引堆(Max-Heap-Index)

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    // 最大索引堆
    template<typename Item>
    class IndexMaxHeap{
    
    private:
        Item *data;     // 最大索引堆中的数据
        int *indexes;   // 最大索引堆中的索引, indexes[x] = i 表示索引i在x的位置
        int *reverse;   // 最大索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置
    
        int count;
        int capacity;
    
        // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
        void shiftUp( int k ){
    
            while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
                swap( indexes[k/2] , indexes[k] );
                reverse[indexes[k/2]] = k/2;
                reverse[indexes[k]] = k;
                k /= 2;
            }
        }
    
        // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
        void shiftDown( int k ){
    
            while( 2*k <= count ){
                int j = 2*k;
                if( j + 1 <= count && data[indexes[j+1]] > data[indexes[j]] )
                    j += 1;
    
                if( data[indexes[k]] >= data[indexes[j]] )
                    break;
    
                swap( indexes[k] , indexes[j] );
                reverse[indexes[k]] = k;
                reverse[indexes[j]] = j;
                k = j;
            }
        }
    
    public:
        // 构造函数, 构造一个空的索引堆, 可容纳capacity个元素
        IndexMaxHeap(int capacity){
    
            data = new Item[capacity+1];
            indexes = new int[capacity+1];
            reverse = new int[capacity+1];
            for( int i = 0 ; i <= capacity ; i ++ )
                reverse[i] = 0;
    
            count = 0;
            this->capacity = capacity;
        }
    
        ~IndexMaxHeap(){
            delete[] data;
            delete[] indexes;
            delete[] reverse;
        }
    
        // 返回索引堆中的元素个数
        int size(){
            return count;
        }
    
        // 返回一个布尔值, 表示索引堆中是否为空
        bool isEmpty(){
            return count == 0;
        }
    
        // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
        // 传入的i对用户而言,是从0索引的
        void insert(int i, Item item){
            assert( count + 1 <= capacity );
            assert( i + 1 >= 1 && i + 1 <= capacity );
    
            // 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。
            assert( !contain(i) );
    
            i += 1;
            data[i] = item;
            indexes[count+1] = i;
            reverse[i] = count+1;
            count++;
    
            shiftUp(count);
        }
    
        // 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
        Item extractMax(){
            assert( count > 0 );
    
            Item ret = data[indexes[1]];
            swap( indexes[1] , indexes[count] );
            reverse[indexes[count]] = 0;
            reverse[indexes[1]] = 1;
            count--;
            shiftDown(1);
            return ret;
        }
    
        // 从最大索引堆中取出堆顶元素的索引
        int extractMaxIndex(){
            assert( count > 0 );
    
            int ret = indexes[1] - 1;
            swap( indexes[1] , indexes[count] );
            reverse[indexes[count]] = 0;
            reverse[indexes[1]] = 1;
            count--;
            shiftDown(1);
            return ret;
        }
    
        // 获取最大索引堆中的堆顶元素
        Item getMax(){
            assert( count > 0 );
            return data[indexes[1]];
        }
    
        // 获取最大索引堆中的堆顶元素的索引
        int getMaxIndex(){
            assert( count > 0 );
            return indexes[1]-1;
        }
    
        // 看索引i所在的位置是否存在元素
        bool contain( int i ){
            assert( i + 1 >= 1 && i + 1 <= capacity );
            return reverse[i+1] != 0;
        }
    
        // 获取最大索引堆中索引为i的元素
        Item getItem( int i ){
            assert( contain(i) );
            return data[i+1];
        }
    
        // 将最大索引堆中索引为i的元素修改为newItem
        void change( int i , Item newItem ){
    
            assert( contain(i) );
            i += 1;
            data[i] = newItem;
    
            // 找到indexes[j] = i, j表示data[i]在堆中的位置
            // 之后shiftUp(j), 再shiftDown(j)
    //        for( int j = 1 ; j <= count ; j ++ )
    //            if( indexes[j] == i ){
    //                shiftUp(j);
    //                shiftDown(j);
    //                return;
    //            }
    
            // 有了 reverse 之后,
            // 我们可以非常简单的通过reverse直接定位索引i在indexes中的位置
            shiftUp( reverse[i] );
            shiftDown( reverse[i] );
        }
    };
    

    堆排序

    #include <iostream>
    #include <algorithm>
    
    // 优化的shiftDown过程, 使用赋值的方式取代不断的swap,
    // 该优化思想和我们之前对插入排序进行优化的思路是一致的
    template<typename T>
    void __shiftDown(T arr[], int n, int k){
    
        T e = arr[k];
        while( 2*k+1 < n ){
            int j = 2*k+1;
            if( j+1 < n && arr[j+1] > arr[j] )
                j += 1;
    
            if( e >= arr[j] ) break;
    
            arr[k] = arr[j];
            k = j;
        }
    
        arr[k] = e;
    }
    
    // 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序
    template<typename T>
    void heapSort(T arr[], int n){
    
        // 注意,此时我们的堆是从0开始索引的
        // 从(最后一个元素的索引-1)/2开始
        // 最后一个元素的索引 = n-1
        for( int i = (n-1-1)/2 ; i >= 0 ; i -- )
            __shiftDown2(arr, n, i);
    
        for( int i = n-1; i > 0 ; i-- ){
            swap( arr[0] , arr[i] );
            __shiftDown(arr, i, 0);
        }
    }
    

    二分搜索树(Binary-Search-Tree)


    什么是二分搜索树

    二分搜索树具有以下特点

    • 依然是一棵二叉树
    • 每个结点大与左孩子
    • 每个结点大于右孩子
    • 以左右孩子为根的子树仍然是二分搜索树
    • 不存在相同的结点
    • 不一定是完全二叉树
    • 用 Node 结点来表示

    二分搜索树的一些基本操作

    • 创建
    • 删除
    • 结点个数
    • 插入
    • 判断是否存在一个元素
    • 前序遍历
    • 中序遍历
    • 后序遍历
    • 删除最大值
    • 删除最小值
    • 删除指定值
    #include <iostream>
    #include <queue>
    #include <cassert>
    
    using namespace std;
    
    // 二分搜索树
    template <typename Key, typename Value>
    class BST{
    
    private:
        // 树中的节点为私有的结构体, 外界不需要了解二分搜索树节点的具体实现
        struct Node{
            Key key;
            Value value;
            Node *left;
            Node *right;
    
            Node(Key key, Value value){
                this->key = key;
                this->value = value;
                this->left = this->right = NULL;
            }
    
            Node(Node *node){
                this->key = node->key;
                this->value = node->value;
                this->left = node->left;
                this->right = node->right;
            }
        };
    
        Node *root; // 根节点
        int count;  // 树中的节点个数
    
    public:
        // 构造函数, 默认构造一棵空二分搜索树
        BST(){
            root = NULL;
            count = 0;
        }
    
        // 析构函数, 释放二分搜索树的所有空间
        ~BST(){
            destroy( root );
        }
    
        // 返回二分搜索树的节点个数
        int size(){
            return count;
        }
    
        // 返回二分搜索树是否为空
        bool isEmpty(){
            return count == 0;
        }
    
        // 向二分搜索树中插入一个新的(key, value)数据对
        void insert(Key key, Value value){
            root = insert(root, key, value);
        }
    
        // 查看二分搜索树中是否存在键key
        bool contain(Key key){
            return contain(root, key);
        }
    
        // 在二分搜索树中搜索键key所对应的值。如果这个值不存在, 则返回NULL
        Value* search(Key key){
            return search( root , key );
        }
    
        // 二分搜索树的前序遍历
        void preOrder(){
            preOrder(root);
        }
    
        // 二分搜索树的中序遍历
        void inOrder(){
            inOrder(root);
        }
    
        // 二分搜索树的后序遍历
        void postOrder(){
            postOrder(root);
        }
    
        // 二分搜索树的层序遍历
        void levelOrder(){
    
            queue<Node*> q;
            q.push(root);
            while( !q.empty() ){
    
                Node *node = q.front();
                q.pop();
    
                cout<<node->key<<endl;
    
                if( node->left )
                    q.push( node->left );
                if( node->right )
                    q.push( node->right );
            }
        }
    
        // 寻找二分搜索树的最小的键值
        Key minimum(){
            assert( count != 0 );
            Node* minNode = minimum( root );
            return minNode->key;
        }
    
        // 寻找二分搜索树的最大的键值
        Key maximum(){
            assert( count != 0 );
            Node* maxNode = maximum(root);
            return maxNode->key;
        }
    
        // 从二分搜索树中删除最小值所在节点
        void removeMin(){
            if( root )
                root = removeMin( root );
        }
    
        // 从二分搜索树中删除最大值所在节点
        void removeMax(){
            if( root )
                root = removeMax( root );
        }
    
        // 从二分搜索树中删除键值为key的节点
        void remove(Key key){
            root = remove(root, key);
        }
    
    private:
        // 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法
        // 返回插入新节点后的二分搜索树的根
        Node* insert(Node *node, Key key, Value value){
    
            if( node == NULL ){
                count ++;
                return new Node(key, value);
            }
    
            if( key == node->key )
                node->value = value;
            else if( key < node->key )
                node->left = insert( node->left , key, value);
            else    // key > node->key
                node->right = insert( node->right, key, value);
    
            return node;
        }
    
        // 查看以node为根的二分搜索树中是否包含键值为key的节点, 使用递归算法
        bool contain(Node* node, Key key){
    
            if( node == NULL )
                return false;
    
            if( key == node->key )
                return true;
            else if( key < node->key )
                return contain( node->left , key );
            else // key > node->key
                return contain( node->right , key );
        }
    
        // 在以node为根的二分搜索树中查找key所对应的value, 递归算法
        // 若value不存在, 则返回NULL
        Value* search(Node* node, Key key){
    
            if( node == NULL )
                return NULL;
    
            if( key == node->key )
                return &(node->value);
            else if( key < node->key )
                return search( node->left , key );
            else // key > node->key
                return search( node->right, key );
        }
    
        // 对以node为根的二分搜索树进行前序遍历, 递归算法
        void preOrder(Node* node){
    
            if( node != NULL ){
                cout<<node->key<<endl;
                preOrder(node->left);
                preOrder(node->right);
            }
        }
    
        // 对以node为根的二分搜索树进行中序遍历, 递归算法
        void inOrder(Node* node){
    
            if( node != NULL ){
                inOrder(node->left);
                cout<<node->key<<endl;
                inOrder(node->right);
            }
        }
    
        // 对以node为根的二分搜索树进行后序遍历, 递归算法
        void postOrder(Node* node){
    
            if( node != NULL ){
                postOrder(node->left);
                postOrder(node->right);
                cout<<node->key<<endl;
            }
        }
    
        // 释放以node为根的二分搜索树的所有节点
        // 采用后续遍历的递归算法
        void destroy(Node* node){
    
            if( node != NULL ){
                destroy( node->left );
                destroy( node->right );
    
                delete node;
                count --;
            }
        }
    
        // 返回以node为根的二分搜索树的最小键值所在的节点, 递归算法
        Node* minimum(Node* node){
            if( node->left == NULL )
                return node;
    
            return minimum(node->left);
        }
    
        // 返回以node为根的二分搜索树的最大键值所在的节点, 递归算法
        Node* maximum(Node* node){
            if( node->right == NULL )
                return node;
    
            return maximum(node->right);
        }
    
        // 删除掉以node为根的二分搜索树中的最小节点, 递归算法
        // 返回删除节点后新的二分搜索树的根
        Node* removeMin(Node* node){
    
            if( node->left == NULL ){
    
                Node* rightNode = node->right;
                delete node;
                count --;
                return rightNode;
            }
    
            node->left = removeMin(node->left);
            return node;
        }
    
        // 删除掉以node为根的二分搜索树中的最大节点, 递归算法
        // 返回删除节点后新的二分搜索树的根
        Node* removeMax(Node* node){
    
            if( node->right == NULL ){
    
                Node* leftNode = node->left;
                delete node;
                count --;
                return leftNode;
            }
    
            node->right = removeMax(node->right);
            return node;
        }
    
        // 删除掉以node为根的二分搜索树中键值为key的节点, 递归算法
        // 返回删除节点后新的二分搜索树的根
        Node* remove(Node* node, Key key){
    
            if( node == NULL )
                return NULL;
    
            if( key < node->key ){
                node->left = remove( node->left , key );
                return node;
            }
            else if( key > node->key ){
                node->right = remove( node->right, key );
                return node;
            }
            else{   // key == node->key
    
                if( node->left == NULL ){
                    Node *rightNode = node->right;
                    delete node;
                    count --;
                    return rightNode;
                }
    
                if( node->right == NULL ){
                    Node *leftNode = node->left;
                    delete node;
                    count--;
                    return leftNode;
                }
    
                // node->left != NULL && node->right != NULL
                Node *successor = new Node(minimum(node->right));
                count ++;
    
                successor->right = removeMin(node->right);
                successor->left = node->left;
    
                delete node;
                count --;
    
                return successor;
            }
        }
    };
    

    四叉树(Quad-Tree)


    什么是四叉树

    参考博客:四叉树空间索引原理及其实现

    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割。

    四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是GIS中常用的空间索引之一。

    常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。

    在这里插入图片描述

    四叉树的一些应用

    参考博客:一个四叉树的简单实现

    参考博客:四叉树Quadtrees在游戏领域应用

    八叉树(Octree)


    参考博客:八叉树(Octree)

    参考博客:八叉树

    参考博客:八叉树及K-D树的应用和实现

    参考博客:图像量化法——八叉树算法

    kd 树(Kd-Tree)


    参考博客:Kd-Tree算法原理简析

    参考博客:KDTree

    参考博客:KD tree

    参考博客:详解 KDTree

    红黑树(Red-Black-Tree)


    参考博客:红黑树(一)之 原理和算法详细介绍

    参考博客:红黑树(二)之 C语言的实现

    参考博客:红黑树(三)之 Linux内核中红黑树的经典实现

    参考博客:红黑树(四)之 C++的实现

    参考博客:红黑树(六)之 参考资料

    哈夫曼树(Huffman-Tree)


    定义

    具有最小带权路径长度的二叉树称为哈夫曼树。

    参考博客:哈夫曼树

    参考博客:哈夫曼树与哈夫曼编码

    参考博客:哈夫曼树

    参考博客:哈夫曼树

    展开全文
  • 图解常见树结构

    千次阅读 2021-03-04 09:39:27
    目录二叉树二叉查找退化问题平衡二叉平衡搜索(AVL )2-3 2-3-4 B 红黑左旋/右旋 保持红黑结构应用 二叉树 满足以下两个条件的就是二叉树: 本身是有序中包含的各个节点的度不能...




    1 二叉树

    满足以下两个条件的树就是二叉树:

    1. 本身是有序树。
    2. 树中包含的各个节点的度不能超过 2,即只能是 0、1、2。

    分支被称作“左子树”或“右子树”。
    在这里插入图片描述


    2 二叉查找树

    二叉查找树(英语:Binary Search Tree),也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

    1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
    2. 若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值;
    3. 任意节点的左、右子树也分别为二叉查找树。

    下图为查找值为29的节点的步骤:

    在这里插入图片描述

    1. 查看根节点 41。
    2. 因为 41>29,所以查看 41 的左孩子 20。
    3. 因为 20<29,所以查看 20 的右孩子29,发现其正好是要查看的节点。

    2.1 退化问题

    如果数据的插入顺序是从大到小,或是从小到大,会导致二叉查找树退化成单链表的形式。

    例如,插入数据依次为 {1,2,3,4,5}(从小到大),则如下图所示:
    在这里插入图片描述
    例如,插入数据依次为 {5,4,3,2,1}(从大到小),则如下图所示:
    在这里插入图片描述
    为了解决该问题,出现了一些解决方法能够使得树趋向平衡,这种自平衡的树叫做平衡树。


    3 平衡树

    平衡树(Balance Tree,BT)指的是,任意节点的子树的高度差都小于等于 1

    常见的符合平衡树的有 AVL 树(二叉平衡搜索树),B 树(多路平衡搜索树,2-3 树,2-3-4 树中的一种),红黑树等。


    3.1 二叉平衡搜索树(AVL 树)

    AVL 树是严格平衡的二叉树,任意节点的两个子树的高度差不超过 1。

    AVL 树利用自平衡能,对不符合高度差的结构进行调整,解决二叉树退化问题;

    例如,插入数据依次为 {1,2,3,4,5}(从小到大),则如下图所示:

    在这里插入图片描述


    3.2 “2-3 树”

    2-3 树,是指每个具有子节点的节点要么有两个子节点和一个数据元素,要么有三个子节点和两个数据元素的自平衡的树,它的所有叶子节点都具有相同的高度。
    在这里插入图片描述

    2 节点:包含 2 个子节点 和 1 个数据元素。
    3 节点:包含 3 个子节点 和 2 个数据元素。

    性质 1:满足二叉搜索树的性质。
    性质 2:节点可以存放一个或两个元素。
    性质 3:每个节点有两个或三个子节点。

    插入元素步骤如下:
    在这里插入图片描述
    在这里插入图片描述


    3.3 “2-3-4 树”

    2-3-4 树,它的每个非叶子节点,要么是 2 节点,要么是 3 节点,要么是 4 节点,且可以自平衡,所以称作 2-3-4 树。

    在这里插入图片描述

    2 节点:包含 2 个子节点 和 1 个数据元素。
    3 节点:包含 3 个子节点 和 2 个数据元素。
    4 节点:包含 4 个子节点 和 3 个数据元素。

    规则 1:加入新元素时,不会往空的位置添加,而是添加到最后一个叶子节点上。
    规则 2:4节点被分解为 2节点组成的树
    规则 3:分解后新树的根节点需要向上和父节点融合。

    插入元素步骤如下:
    在这里插入图片描述
    规则 1,插入节点 17 不会加入节点 [16,18,20] 的子树,而是与该节点融合。

    在这里插入图片描述
    规则 2,节点 [16,17,18,20] 是一个 4 节点,将该节点进行拆解,将 18 作为子树的根节点进行拆分。
    在这里插入图片描述
    规则三,此时树暂时失去了平衡,需要将拆分后的子树的根节点向上进行融合。

    在这里插入图片描述
    规则 2,节点 [6,10,14,18] 是一个 4 节点,将该节点进行拆解成新的树,将 14 作为子树的根节点进行拆分,完成了 2-3-4 树的构建。
    在这里插入图片描述

    2-3 树,2-3-4 树都有了,那是不是也有 2-3-4-5 树,2-3-4-5–…-n 树的存在呢?
    事实上是有的,世人把这一类树称为一个名字:B 树。


    3.4 B 树

    B 树,表示的是一类树,具有如下特性:

    1、 一个节点可以有多于两个子节点;
    2、自平衡的;

    为了更好地区分一颗 B 树到底属于哪一类树,给它一个新的属性:度(Degree):一个节点能有多少箭头指向其他节点。

    具有度为 3 的 B 树,表示一个节点最多有三个子节点,也就是 2-3 树的定义。
    具有度为 4 的 B 树,表示一个节点最多有四个子节点,也就是 2-3-4 树的定义。

    图为 4 的 B 树的示例图:
    在这里插入图片描述


    4 红黑树

    R-B Tree,全称是 Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。

    4.1 红黑树的特点

    1.结点是红色或黑色。
    2.根结点是黑色。
    3.每个叶子结点都是黑色的空结点(NIL结点)。
    4.每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
    5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

    红黑树的特点能保证 从根节点到叶子结点的最长路径不会超过最短路径的2倍。

    一个经典的红黑树,如下图所示:
    在这里插入图片描述

    将该红黑树与上文讲到的 2-3-4 树对比,可以发现,红黑树可以看做是一个 2-3-4 树的变形:
    在这里插入图片描述
    当插入或删除节点时,红黑树的5条规则可能被打破。这个时候需要利用 变色旋转 来调整红黑树使其满足5条规则(调整的情况很多,过程复杂,需要具体情况具体分析,对过程有所了解即可)。

    4.2 左旋/右旋

    左旋:

    逆时针旋转红黑树的两个结点,使得父结点被自己的右孩子取代,而自己成为自己的左孩子。
    在这里插入图片描述
    右旋:

    顺时针旋转红黑树的两个结点,使得父结点被自己的左孩子取代,而自己成为自己的右孩子。
    在这里插入图片描述

    4.3 红黑树的插入调整(了解)

    红黑树插入新节点的时候可以分为5种不同的局面,每种局面有不同的调整方法。

    局面1: 新结点(A)位于树根,没有父结点。

    空心三角形代表结点下面的子树
    在这里插入图片描述
    这种局面,直接让新结点变色为黑色,规则2得到满足。同时,黑色的根结点使得每条路径上的黑色结点数目都增加了1,所以并没有打破规则5。

    在这里插入图片描述
    局面2:新结点(B)的父结点是黑色。

    这种局面,新插入的红色结点B并没有打破红黑树的规则,所以不需要做任何调整。
    在这里插入图片描述

    局面3:新结点(D)的父结点和叔叔结点都是红色。

    在这里插入图片描述
    这种局面,两个红色结点B和D连续,违反了规则4。因此我们先让结点B变为黑色:
    在这里插入图片描述
    这样一来,结点B所在路径凭空多了一个黑色结点,打破了规则5。因此我们让结点A变为红色:
    在这里插入图片描述
    这时候,结点A和C又成为了连续的红色结点,我们再让结点C变为黑色:
    在这里插入图片描述
    经过上面的调整,这一局部重新符合了红黑树的规则。

    局面4:新结点(D)的父结点是红色,叔叔结点是黑色或者没有叔叔,且新结点是父结点的右孩子,父结点(B)是祖父结点的左孩子。
    在这里插入图片描述
    以结点B为轴,做一次左旋转,使得新结点D成为父结点,原来的父结点B成为D的左孩子:
    在这里插入图片描述
    这样一来,进入了局面5。

    局面5:新结点(D)的父结点是红色,叔叔结点是黑色或者没有叔叔,且新结点是父结点的左孩子,父结点(B)是祖父结点的左孩子。
    在这里插入图片描述
    以结点A为轴,做一次右旋转,使得结点B成为祖父结点,结点A成为结点B的右孩子:
    在这里插入图片描述
    接下来,我们让结点B变为黑色,结点A变为红色:
    在这里插入图片描述
    经过上面的调整,这一局部重新符合了红黑树的规则。

    如果局面4和局面5当中的父结点B是祖父结点A的右孩子该怎么办呢?很简单,如果局面4中的父结点B是右孩子,则成为了局面5的镜像,原本的右旋操作改为左旋;如果局面5中的父结点B是右孩子,则成为了局面4的镜像,原本的左旋操作改为右旋。


    下边给出一个实际案例

    给定下面这颗红黑树,新插入的结点是21:
    在这里插入图片描述
    显然,新结点21和它的父结点22是连续的红色结点,违背了规则4,应该如何调整呢?

    当前的情况符合局面3:“新结点的父结点和叔叔结点都是红色。”

    于是首先经过三次变色,22变为黑色,25变为红色,27变为黑色:
    在这里插入图片描述
    经过上面的调整,以结点25为根的子树符合了红黑树规则,但结点25和结点17成为了连续的红色结点,违背规则4。

    于是,我们把结点25看做一个新结点,正好符合局面5的镜像:“新结点的父结点是红色,叔叔结点是黑色或者没有叔叔,且新结点是父结点的右孩子,父结点是祖父结点的右孩子”

    于是我们以根结点13为轴进行左旋转,使得结点17成为了新的根结点:
    在这里插入图片描述
    接下来,让结点17变为黑色,结点13变为红色:
    在这里插入图片描述
    如此一来,我们的红黑树变得重新符合规则。


    4.4 红黑树的删除调整(了解)

    二叉查找树删除 操作可以分成三种情况。

    情况1,待删除的结点没有子结点:
    在这里插入图片描述
    上图中,待删除的结点12是叶子结点,没有子节点,直接删除:

    在这里插入图片描述
    情况2,待删除的结点有一个孩子:
    在这里插入图片描述
    上图中,待删除的结点13只有左孩子,让左孩子结点11取代被删除的结点,结点11以下的结点关系无需变动:
    在这里插入图片描述
    情况3,待删除的结点有两个孩子:
    在这里插入图片描述
    上图中,待删除的结点5有两个孩子,这种情况比较复杂。此时,需要选择与待删除结点最接近的结点来取代它:结点3仅小于结点5,结点6仅大于结点5,两者都是合适的选择。但习惯上选择仅大于待删除结点的结点,也就是结点6来取代节点5。

    被选中的结点6,仅大于结点5,因此一定没有左孩子。否则按照情况1或情况2的方式进一步处理。

    在这里插入图片描述


    红黑树的删除 规则需要在二叉树的删除规则上,再经过变色与旋转操作,使其满足二叉树的5条规则。

    第一步:如果待删除结点有两个非空的孩子结点,转化成待删除结点只有一个孩子(或没有孩子)的情况。
    在这里插入图片描述
    上面例子是一颗红黑树的局部,标数字的三角形代表任意形态的子树,假设结点8是待删除结点。

    根据上文讲解的二叉查找树删除流程,由于结点8有两个孩子,我们选择仅大于8的结点10复制到8的位置,结点颜色变成待删除结点的颜色:
    在这里插入图片描述
    接下来我们需要删除原结点10:
    在这里插入图片描述
    结点10能成为仅大于8的结点,必定没有左孩子结点,所以问题转换成了待删除结点只有一个右孩子(或没有孩子)的情况。接下来我们进入第二步。

    第二步:根据待删除结点和其唯一子结点的颜色,分情况处理。

    情况1:自身是红色,子结点是黑色:
    在这里插入图片描述
    这种情况最简单,按照二叉查找树的删除操作,删除结点1即可:
    在这里插入图片描述
    情况2:自身是黑色,子结点是红色:
    在这里插入图片描述
    这种情况也很简单,首先按照二叉查找树的删除操作,删除结点1:
    在这里插入图片描述
    此时,这条路径凭空减少了一个黑色结点,需要把结点2变成黑色即可:
    在这里插入图片描述
    情况3:自身是黑色,子结点也是黑色,或者子结点是空叶子结点:
    在这里插入图片描述
    这种情况最复杂,涉及到很多变化。
    首先还是按照二叉查找树的删除操作,删除结点1:
    在这里插入图片描述
    显然,这条路径上减少了一个黑色结点,而且结点2再怎么变色也解决不了。

    这时候使用下边讲的第三步,专门解决父子双黑的情况。

    第三步:遇到双黑结点,在子结点顶替父结点之后,分成6种子情况处理。

    子情况1:结点2是红黑树的根结点:
    在这里插入图片描述
    此时所有路径都减少了一个黑色结点,并未打破规则,不需要调整。

    子情况2:结点2的父亲、兄弟、侄子结点都是黑色:
    在这里插入图片描述
    此时,直接把结点2的兄弟结点B改为红色:
    这样一来,原本结点2所在的路径少了一个黑色结点,现在结点B所在的路径也少了一个黑色结点,两边“扯平”了。
    在这里插入图片描述
    可是,结点A以下的每一条路径都减少了一个黑色结点,与结点A之外的其他路径又造成了新的不平衡啊?没关系,我们让结点A扮演原先结点2的角色,进行递归操作,重新判断各种情况。

    子情况3,结点2的兄弟结点是红色:
    在这里插入图片描述
    首先以结点2的父结点A为轴,进行左旋
    在这里插入图片描述
    然后结点A变成红色、结点B变成黑色:
    在这里插入图片描述
    这样的意义是什么呢?结点2所在的路径仍然少一个黑色结点呀?
    别急,这样的变化有可能转换成子情况4、5、6中的任意一种,在子情况4、5、6当中会进一步解决。

    子情况4:结点2的父结点是红色,兄弟和侄子结点是黑色:
    在这里插入图片描述
    这种情况,我们直接让结点2的父结点A变成黑色,兄弟结点B变成红色:
    在这里插入图片描述
    这样一来,结点2的路径补充了黑色结点,而结点B的路径并没有减少黑色结点,重新符合了红黑树的规则。

    子情况5:结点2的父结点随意,兄弟结点B是黑色右孩子,左侄子结点是红色,右侄子结点是黑色:
    在这里插入图片描述
    这种情况下,首先以结点2的兄弟结点B为轴进行右旋
    在这里插入图片描述
    接下来结点B变为红色,结点C变为黑色:
    在这里插入图片描述
    这样的变化转换成了子情况6。

    子情况6:结点2的父结点随意,兄弟结点B是黑色右孩子,右侄子结点是红色:

    在这里插入图片描述
    首先以结点2的父结点A为轴左旋:
    在这里插入图片描述
    接下来让结点A和结点B的颜色交换,并且结点D变为黑色:
    在这里插入图片描述
    这样是否解决了问题呢?

    经过结点2的路径由(随意+黑)变成了(随意+黑+黑),补充了一个黑色结点;

    经过结点D的路径由(随意+黑+红)变成了(随意+黑),黑色结点并没有减少。

    所以,这时候重新符合了红黑树的规则。


    下边给出一个实际案例

    下面这颗红黑树,待删除的是结点17:
    在这里插入图片描述
    第一步: 结点17有两个孩子,子树当中仅大于17的结点是25,所以把结点25复制到17位置,保持17y原来的颜色–黑色:
    在这里插入图片描述
    接下来,需要删除原本的结点25
    在这里插入图片描述

    这个情况对应于 第二步的情况3,即待删除结点是黑色,子结点是空叶子结点。于是删除框中结点25,进入第三步的情况。
    在这里插入图片描述
    此时,框中的结点虽然是空叶子结点,但仍然可以用于判断局面,当前局面符合 第三步的子情况5 的镜像:
    在这里插入图片描述
    该情况 与 第三步的子情况5 的对比
    在这里插入图片描述
    于是通过左旋和变色,把子树转换成情况6的镜像:
    在这里插入图片描述
    再经过右旋、变色,子树最终成为了下面的样子:
    在这里插入图片描述
    在这里插入图片描述
    这样一来,整颗二叉树又重新符合了红黑树的规则。

    4.5 应用场景

    红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是 O(logn),效率非常之高。

    例如,Java 集合中的 TreeSet 和 TreeMap,C++ STL 中的 set、map,以及 Linux 虚拟内存的管理,都是通过红黑树去实现的。

    展开全文
  • redis存储树结构数据

    千次阅读 2019-10-03 08:00:51
    本文主要讲解两方面内容:1.redis如何存储树结构数据。2.java操作redis时选取哪种序列化器。 redis如何存储树结构数据 先抛出结论,树结构数据在redis中的存储顺序如下: ...

    本文主要讲解两方面内容:1.redis如何存储树结构数据。2.java操作redis时选取哪种序列化器。

    1. redis如何存储树结构数据

    先抛出结论,树结构数据在redis中的存储形式如下:树结构数据在redis中的存储形式

    1.1 前置条件

    1. spring-boot-starter-data-redis(2.1.8)
    2. fastjson(1.2.61)
    3. redis可视化工具 Redis Desktop Manager

    1.2 树结构数据在redis中的存储形式(数据结构)

    在这里插入图片描述
    假设有如上典型的组织机构数据,前端需要按层级展示,分层级查询指定节点的子集。

    1.2.1 redis中Key的设计

    redisKey={NAME_SPACE}:{level}:{parentId}
    NAME_SPACE:该数据所在命名空间
    level:当前层级
    parentId:父节点id,可为空

    1.2.2 查询

    1. 按层级查询:输入指定层级,返回该层级下的所有节点列表

    入参:

    {
    	"level":3
    }
    

    返回:

    [
        {
            "nodeId": "010101",
            "nodeName": "人事部"
        },
        {
            "nodeId": "010102",
            "nodeName": "技术部"
        },
        {
            "nodeId": "010301",
            "nodeName": "人事部"
        },
        {
            "nodeId": "010202",
            "nodeName": "技术部"
        },
        {
            "nodeId": "010201",
            "nodeName": "人事部"
        }
    ]
    
    1. 查询指定节点的所有子节点:输入该节点id和当前层级

    入参:

    {
    	"nodeId":"0102",
    	"level":2
    }
    

    返回:

    [
        {
            "nodeId": "010202",
            "nodeName": "技术部"
        },
        {
            "nodeId": "010201",
            "nodeName": "人事部"
        }
    ]
    

    1.2.3 后台实现

    主要代码:

    /**
         * 查询 指定层级下某个父节点的所有子节点
         *
         * @param level    层级
         * @param parentId 父节点id,为空时查询该层级下所有节点
         * @return 指定层级下某个父节点的所有子节点
         */
        @SuppressWarnings("unchecked")
        public List<OrgBean> getSubTree(int level, @Nullable String parentId) {
            List<OrgBean> beanList;
            if (StringUtils.isBlank(parentId) && level != 1) {
                //parentId 为空,模糊匹配查询
                beanList = patternSearch(level);
            } else {
                //parentId 不为空,精确匹配查询
                beanList = exactlySearch(level, parentId);
            }
            return beanList;
        }
    
        @SuppressWarnings("unchecked")
        private List<OrgBean> patternSearch(int level) {
            //SCAN 0 MATCH {NAME_SPACE}:{level}:* COUNT 10000
            String pattern = getRedisKey("*", level);
            logger.info("redisKey:{}", pattern);
            List<String> keys = (List<String>) redisTemplate.execute(connection -> {
                List<String> keyStrList = new ArrayList<>();
                RedisKeyCommands keysCmd = connection.keyCommands();
                //采用 SCAN 命令,迭代遍历所有key
                Cursor<byte[]> cursor = keysCmd.scan(ScanOptions.scanOptions().match(pattern).count(10000L).build());
                while (cursor.hasNext()) {
                    keyStrList.add(new String(cursor.next(), StandardCharsets.UTF_8));
                }
                return keyStrList;
            }, true);
            if (isNotEmpty(keys)) {
                return keys.stream().flatMap(key -> {
                    List list = listOperations.range(key, 0, -1);
                    return deserializeJsonList(list, OrgBean.class).stream();
                }).collect(toList());
            } else {
                return Collections.emptyList();
            }
        }
    
        @SuppressWarnings("unchecked")
        private List<OrgBean> exactlySearch(int level, String parentId) {
            List<OrgBean> beanList = new ArrayList<>();
            String redisKey = getRedisKey(parentId, level);
            logger.info("redisKey:{}", redisKey);
            Boolean hasKey = redisTemplate.hasKey(redisKey);
            if (Boolean.valueOf(true).equals(hasKey)) {
                List jsonList = listOperations.range(redisKey, 0, -1);
                beanList = deserializeJsonList(jsonList, OrgBean.class);
            }
            return beanList;
        }
    
        private <T> List<T> deserializeJsonList(List jsonList, Class<T> clazz) {
            ArrayList<T> beanList = new ArrayList<>();
            if (isNotEmpty(jsonList)) {
                //反序列化为指定类型的bean
                for (Object o : jsonList) {
                    if (nonNull(o)) {
                        T bean = JSON.toJavaObject((JSONObject) o, clazz);
                        beanList.add(bean);
                    }
                }
            }
            return beanList;
        }
        /**
         * redisKey: {NAME_SPACE}:{level}:{parentId}
         */
        private String getRedisKey(String parentId, int level) {
            return concat(DELIMIT, NAME_SPACE, level, parentId);
        }
        /**
         * 连接字符串通用方法
         *
         * @param delimit 分隔符
         * @param element 字符串元素
         * @return 按指定分隔符连接的字符串
         */
        private String concat(String delimit, Object... element) {
            if (isNull(element) || element.length == 0) {
                return null;
            }
            return Stream.of(element).filter(Objects::nonNull)
                    .map(String::valueOf).filter(StringUtils::isNoneBlank).collect(joining(delimit));
        }
    

    2 java操作redis,设置序列化器

    org.springframework.data.redis.serializer.JdkSerializationRedisSerializer
    org.springframework.data.redis.serializer.StringRedisSerializer
    org.springframework.data.redis.serializer.GenericJackson2JsonRedisSerializer
    org.springframework.data.redis.serializer.Jackson2JsonRedisSerializer
    com.alibaba.fastjson.support.spring.FastJsonRedisSerializer
    com.alibaba.fastjson.support.spring.GenericFastJsonRedisSerializer
    spring-boot-starter-data-redis 默认采用 JdkSerializationRedisSerializer,这样序列化后的数据无法通过工具直观地展示,通常redis的Key采用StringRedisSerializer,value采用JSON格式化后存储。
    json序列化器分别有两种:JsonRedisSerializer和GenericJsonRedisSerializer,Jackson和FastJson分别有对应的实现。

    2.1 两种序列化器的区别

    1)JsonRedisSerializer 序列化器,针对指定类型的javaBean,初始化的时候需指定泛型。反序列化时,需要做类型转换。
    2)Generic
    JsonRedisSerializer 序列化器,无需指定特定类型,redis服务器中将存储具体数据的类型信息。反序列化时,直接得到既定类型,不需要做类型转换。
    举例说明:

    2.1.1 *JsonRedisSerializer 序列化器,构造方法:

    com.alibaba.fastjson.support.spring.FastJsonRedisSerializer 
    public FastJsonRedisSerializer(Class<T> type) {
            this.type = type;
        }
    
    org.springframework.data.redis.serializer.Jackson2JsonRedisSerializer
    /**
     * Creates a new {@link Jackson2JsonRedisSerializer} for the given target {@link Class}.
     *
     * @param type
     */
    public Jackson2JsonRedisSerializer(Class<T> type) {
    	this.javaType = getJavaType(type);
    }
    

    2.1.2 *JsonRedisSerializer 序列化器,redis服务器中存储的数据格式:

    在这里插入图片描述
    在这里插入图片描述

    2.1.3 Generic*JsonRedisSerializer 序列化器,构造方法:

    com.alibaba.fastjson.support.spring.GenericFastJsonRedisSerializer
    public class GenericFastJsonRedisSerializer implements RedisSerializer<Object> {}
    
    org.springframework.data.redis.serializer.GenericJackson2JsonRedisSerializer
    public class GenericJackson2JsonRedisSerializer implements RedisSerializer<Object> {
    	/**
    	 * Creates {@link GenericJackson2JsonRedisSerializer} and configures {@link ObjectMapper} for default typing.
    	 */
    	public GenericJackson2JsonRedisSerializer() {
    		this((String) null);
    	}
    }
    

    2.1.4 Generic*JsonRedisSerializer 序列化器,redis服务器中存储的数据格式:

    在这里插入图片描述
    在这里插入图片描述

    2.1.5 *JsonRedisSerializer 序列化器,反序列化后的类型

    public void testDeserialize() {
            Object val1 = fastJsonTemp.opsForValue().get("emp1_fastJson");
            Object val2 = genericFastJsonTemp.opsForValue().get("emp1_genericFastJson");
            Object val3 = jacksonTemp.opsForValue().get("emp1_jackson");
            Object val4 = genericJacksonTemp.opsForValue().get("emp1_genericJackson");
            //class com.alibaba.fastjson.JSONObject
            log.info(val1.getClass().toString());
            //class com.fcg.redis.orgtree.Employee
            log.info(val2.getClass().toString());
            //class java.util.LinkedHashMap
            log.info(val3.getClass().toString());
            //class com.fcg.redis.orgtree.Employee
            log.info(val4.getClass().toString());
        }
    

    2.2 选用FastJsonRedisSerializer

    理由:

    • 项目中统一采用FastJson,作为JSON序列化工具,因其效率较高。
    • Redis中仅需存储数据,不宜限定该数据的具体JavaBean类型,利于不同项目间共享缓存数据。

    缺点:

    • 由于原始数据缺少类型信息,取出数据后如果需要按照既定类型操作(setters/getters),要多一步转换操作,如:
    {
    	//取出数据类型为 JSONObject
    	List jsonList = listOperations.range(redisKey, 0, -1);
    	//反序列化为指定类型
    	beanList = deserializeJsonList(jsonList, OrgBean.class);
    }
    private <T> List<T> deserializeJsonList(List jsonList, Class<T> clazz) {
           ArrayList<T> beanList = new ArrayList<>();
           if (isNotEmpty(jsonList)) {
               //反序列化为指定类型的bean
               for (Object o : jsonList) {
                   if (nonNull(o)) {
                       T bean = JSON.toJavaObject((JSONObject) o, clazz);
                       beanList.add(bean);
                   }
               }
           }
           return beanList;
       }
    

    2.3 RedisTemplate 配置

    @Bean
        public RedisTemplate<String, Object> redisTemplate(RedisConnectionFactory connectionFactory) {
        	//泛型用Object,可序列化所有类型
            FastJsonRedisSerializer<Object> jsonRedisSerializer = new FastJsonRedisSerializer<>(Object.class);
            StringRedisSerializer stringRedisSerializer = new StringRedisSerializer();
            RedisTemplate<String, Object> template = new RedisTemplate<>();
            template.setKeySerializer(stringRedisSerializer);
            template.setValueSerializer(jsonRedisSerializer);
            template.setHashKeySerializer(stringRedisSerializer);
            template.setHashValueSerializer(stringRedisSerializer);
            template.setDefaultSerializer(jsonRedisSerializer);
            template.setConnectionFactory(connectionFactory);
            template.afterPropertiesSet();
            return template;
        }
    

    在使用RedisTemplate时,不要指定泛型,可序列化所有类型,否则在使用ListOperations 时,会把整个List作为一个元素:

    public class OrgService {
        @Resource(name = "redisTemplate")
        private RedisTemplate redisTemplate;
        @Resource(name = "redisTemplate")
        private ListOperations listOperations;
    }
    

    3 怎么获取节点信息

    有时候除了获取子节点信息外,还需要获取节点本身的信息,这时需要在redis中增加存储节点自身数据,修改结构如下:
    子节点数据: key={NAME_SPACE}:{level}:{parentId},val=List[{childNode}]
    节点本身数据:key={NAME_SPACE}:{level}:{nodeId},val={nodeInfo}
    数据结构
    详细代码请参考git仓库。

    源码地址

    https://gitee.com/thanksm/redis_learn/tree/master/orgtree

    展开全文
  • 数据结构之通用树结构的实现

    千次阅读 2018-02-17 14:54:38
    大家都知道是非线性数据结构,显然我们无法用数组来表示的逻辑结构。那我们应该怎么办呢?通过什么来表示呢?其实可以设计结构体数组对结点间的关系进行表述。如下图所示:从上图发现,将根结点的双亲定义为-1,...

    之前我们讲了树的定义和操作,这节我们讲一下如何实现这些操作。既然要考虑如何实现,那就得说说树的存储结构。

    大家都知道树是非线性数据结构,显然我们无法用数组来表示树的逻辑结构。那我们应该怎么办呢?通过什么来表示呢?其实可

    以设计结构体数组对结点间的关系进行表述。如下图所示:


    从上图发现,将根结点的双亲定义为-1,表示其没有双亲;将根的孩子结点的双亲定义为0,表示其双亲是根结点;将根结点孩

    子1的孩子结点的双亲定义为1,表示其双亲是根结点的孩子结点1;还有双亲定义为根结点孩3,以此类推就会有4、5、6、7...

    等等双亲。通过Child来存放其孩子结点的在结构体数组中下标,这样根据双亲Parent和孩子结点Child就能轻松的访问树结构里

    所有元素了。

    接下来我们考虑两个现实的问题:1.树结构需要添加删除结点,数组存储是否足够灵活?2.每个结点的子结点可以有多个,如何

    存储?到此是不是感觉到很头疼呢?既然要实现树结构的操作,当然希望是一个通用的树结构的操作,可以任意插入结点、删除

    结点等。那我们到底应该怎么办呢?

    大家都知道,之前我们学习线性表时说过,链表是可以无限扩展,任意插入的,不限长度的,这里我们是否可以也用链表代替这

    个结构数组呢?

    Of course!我们当然可以利用链表组织树中的各个结点,链表中的前后关系不代表结点间的逻辑关系,结点的逻辑关系由child数

    据域描述,child数据域保存其他结点的存储地址。既然提到链表,来我们这里就得复用之前已经实现的链表代码,参考线性表之

    单链表

    这里我们的定义两个结构体,链表结点结构体和树结点结构体。如下图:


    树中每一个结点包含一个指向父结点的指针(如下图红色箭头所示)。


    树中每一个结点都是同一个链表中的数据元素,根结点是链表的首元素,根结点的孩子结点从左往右分别是链表的第二个、第三

    个。。。等元素,根结点的孩子结点的孩子结点紧跟在链表后面但是要注意:树结点在链表中的位置不代表树的任何逻辑关

    系。


    下面我们来看一下树的详细架构图:


    由上图我们发现要实现树结构的操作,势必需要两个链表,一个用于记录树所有元素,我们这里称为组织链表、另一个是孩子链

    表用来描述树结构的逻辑关系。

    说了这么多,我们接下来一步一步的来实现上一节描述的那些操作。

    1.创建树

    // 创建树  
    GTree* GTree_Create()
    {
        return LinkList_Create();    // 调用链表创建函数,定义一个空组织链表,并返回
    }

    这里没啥好说的,不明白的小伙伴可以参考之前的章节。

    2.销毁树和清空树

    // 销毁树
    void GTree_Destroy(GTree* tree)
    {
        GTree_Clear(tree);
        LinkList_Destroy(tree);
    }
    // 清空树
    void GTree_Clear(GTree* tree)
    {
         GTree_Delete(tree, 0);
    }

    销毁树就是将所有的树结构清空,并且释放所有申请内存,代表着这个东西不存在了,清空树就是将树变成空树,也就是将其从

    根结点删除。

    3.插入数据

    根据结构图我们知道,树中的一个元素不仅要在组织链表中,还要在其组织链表的孩子链表中,这就需要申明两个链表结点结构

    体内存来用于插入链表(比如结构图中的成员B不仅在组织链表中,而且还包含在A成员的孩子链表中),实现方法如下:

    首先定义插入所需要的树结点结构体变量,用于处理插入元素,接着进行入口参数合法性检查,如果不合法,直接返回NULL;

    如果合法,开始插入元素:

    1.定义存放树结点、孩子结点和插入元素结点结构体变量,并且分别为其定义的结构体申请内存,同时获取当前插入位置双亲的

    元素地址;

    2.对申请内存合法性进行检查;

        2.1.内存申请成功:

              2.1.1.处理插入元素,保存插入元素数据、初始化插入元素双亲(默认为NULL,无双亲)、创建孩子结点链表;

              2.1.2.将树结点和孩子结点地址指向插入元素结点地址,并在树结点链表(组织链表)尾部插入树结点元素;

              2.1.3.检查一下插入位置是否合法,合法,将插入元素的双亲指向当前元素(双亲)的结点地址,在树孩子结点链表(孩子

              链表)尾部插入孩子结点元素,否则,释放申请的孩子结点内存,退出插入操作;

        2.2.内存申请失败,释放内存,退出插入操作;

    实现代码如下:

    // 在树结构指定的位置pPos插入元素data
    // pPos:要插入元素的双亲的位置,即在那个双亲下插入
    int GTree_Insert(GTree* tree, GTreeData* data, int pPos)
    {
        // 定义链表结点结构体
        LinkList* list = (LinkList*)tree;
        // 定义返回变量,并且检查参数合法性
        int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list));
        // 合法性OK
        if( ret )
        {
            TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));     // 定义链表结点结构体,并申请内存,存放树结点链表成员
            TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));    // 定义链表结点结构体,并申请内存,存放孩子结点链表成员
            TLNode* pNode = (TLNode*)LinkList_Get(list, pPos);    // 定义链表结点结构体,保存pPos位置的元素
            GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode));     // 定义树结点结构体,并申请内存,存放要插入元素内容
            // 内存申请合法性检查
            ret = (trNode != NULL) && (cldNode != NULL) && (cNode != NULL);
            // 内存申请成功
            if( ret )
            {
                cNode->data = data;                   // 保存要插入的元素地址
                cNode->parent = NULL;                 // 双亲地址指向NULL
                cNode->child = LinkList_Create();     // 创建孩子链表
                
                trNode->node = cNode;                 // 树结点指向要插入元素结点地址             
                cldNode->node = cNode;                // 树孩子结点指向要插入元素结点地址  
                // 在树结点链表(组织链表)尾部插入树结点元素
                LinkList_Insert(list, (LinkListNode*)trNode, LinkList_Length(list));
                // 要插入的位置合法,不是根结点
                if( pNode != NULL )
                {
                    cNode->parent = pNode->node;      // 将要插入元素的双亲指向当前元素的结点地址                
                    // 在树孩子结点链表(孩子链表)尾部插入孩子结点元素
                    LinkList_Insert(pNode->node->child, (LinkListNode*)cldNode, LinkList_Length(pNode->node->child));
                }
                else
                {            	 
                	free(cldNode);
                }
            }
            // 内存申请不成功,释放内存
            else
            {
                free(trNode);
                free(cldNode);
                free(cNode);
            }
        }
        
        return ret;
    }

    4.打印树结构

    上面我们讲解了树结构插入的操作,但是因为树结构是非线性的,所有我们也不知道是否操作的正确,就算查看地址也因为非线

    性不连续的而行不通,所以我们应该写一个显示函数,可以将插入树结构的数据按照层次(自定义格式)打印出来。

    树结构的显示,归根结底就是遍历树成员,将其打印出来。由于树的定义是非线性、采用递归的形式的,所以树结构的显示必然

    也需要递归来实现。实现的思路如下:

    首先先打印根结点,然后遍历根结点的孩子结点,遍历的过程中打印孩子结点,打印孩子结点时就会遍历该孩子结点的孩子结

    点,直至遍历结束,所需的树结构也就打印出来了。

    实现代码如下:

    // 按指定格式显示树结构,使用文本形式,缩放的方式
    // pFunc  显示方式式函数的地址
    // 孩子结点显示空格增量
    // 孩子结点显示格式'-'
    /* eg:pFunc:%c   gap = 2 div = '-'
          A
          --B
          ----E
          ----F
          --C
          --D 
          ----H
          ----I
          ----J
    */
    void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div)
    {
    	  // 定义树结点结构体,用于存放获取的根结点成员,即组织链表的首元素
        TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);
        // 获取根结构成员成功,入口参数合法,调用显示递归函数
        if( (trNode != NULL) && (pFunc != NULL) )
        {  
            recursive_display(trNode->node, pFunc, 0, gap, div);
        }
    }


    显然,我们递归时直接调用GTree_Display()函数是实现不了打印树结构的,所以我们单独定义了一个实现递归函数。实现代码

    如下:

    // 显示树结构递归函数
    static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div)
    {
        int i = 0;
        // 合法性检查
        if( (node != NULL) && (pFunc != NULL) )
        {
        	  // 循环打印缩进格式
            for(i=0; i<format; i++)
            {
                printf("%c", div);
            }
            // 打印树结构保存的成员数据
            pFunc(node->data);
            // 空行
            printf("\n");
            // 遍历孩子链表,打印孩子链表成员数据 
            for(i=0; i<LinkList_Length(node->child); i++)
            {
                // 获取每一个链表元素,用于递归打印
                TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);
                // 调用递归函数,按格式打印孩子结点数据
                recursive_display(trNode->node, pFunc, format + gap, gap, div);
            }
        }
    }

    遍历孩子结点时调用显示递归函数,这里还有一个pFunc可能大家感到迷茫,莫名其妙,其实这是自定义的一个函数类型,用于

    定义打印内容的格式(字符、字符串、整数等),代码如下:

    typedef void (GTree_Printf)(GTreeData*);
    
    void printf_data(GTreeData* data)
    {
        printf("%c", (int)data);
    }

    打印的结果如下图:


    5.删除结点

    通过上面插入结点的操作,我们知道树结构的插入分两步,第一步往组织链表里插入结点、第二步向孩子链表中插入结点,所以

    树结构是链表中嵌套着链表分层次、不确定元素个数和要删除结点的性质的(可能是分支结点、也可能是叶结点,还有可能直接

    就是根结点)。如果是分子节点,那么它的孩子结点可能还不止一个,同时还可能有子孙结点,所以我们就得依次一个一个、一

    层一层的删除,确保要删除结点、其孩子结点和子孙结点全部被删除。也就是说删除也要分两步,首先删除组织链表里的结点,

    再将组织链表里结点的孩子结点也要删除,然后用上递归的思想继续删除子孙结点,直至删除完毕为止。实现方法如下:

    首先要从组织链表中找到要删除的结点地址,然后保存要删除的结点数据,最后调用删除递归函数。实现代码如下:

    // 删除树结构指定位置pos的元素
    GTreeData* GTree_Delete(GTree* tree, int pos)
    {
        // 定义树结点结构体变量,获取要删除结点当前位置的元素地址
        TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);
        // 定义返回变量
        GTreeData* ret = NULL;
        // 要删除结点的位置元素合法
        if( trNode != NULL )
        {
            ret = trNode->node->data;                 // 保存当前位置元素数据地址,用于函数返回
            
            recursive_delete(tree, trNode->node);     // 调用递归,删除结点    
        }
        
        return ret;
    }

    递归删除函数实现方法如下:

    1.合法性检查;

    2.找到要删除结点的双亲指针;

    3.从组织链表中删除结点;

        3.1.遍历链表,寻找要删除的结点;

              3.1.1.找到后就删除该结点;

               3.1.2.释放该结点内存;

               3.1.3.标记已经找到删除结点,并跳出遍历链表操作;

       3.2.找不到要删除的元素直接进行后面的操作;

    4.从孩子链表中删除孩子结点及其子孙结点;

        4.1.遍历链表,寻找要删除的结点;

               4.1.1.找到后就删除该结点;

               4.1.2.释放该结点内存;

               4.1.3.标记已经找到删除结点,并跳出遍历链表操作;

       4.2.找不到要删除的元素直接进行后面的操作;

    5.如果存在子孙结点,调用递归函数删除所有的子孙结点。

    实现代码如下:

    // 结点删除递归函数
    // list:要删除的树结构
    // node:要删除的结点
    static void recursive_delete(LinkList* list, GTreeNode* node)
    {
    	  // 入口参数合法性检查OK
        if( (list != NULL) && (node != NULL) )
        {
        	  // 定义一个树结点结构体变量,存放要删除位置的双亲地址
            GTreeNode* parent = node->parent;         
            int index = -1;         // 查找变量
            int i = 0;              // 循环变量
            // 遍历树结构组织链表,找到要删除结点的位置
            for(i=0; i<LinkList_Length(list); i++)
            {
            	  // 定义结点链表结构体变量,存放遍历的树链表成员
                TLNode* trNode = (TLNode*)LinkList_Get(list, i);
                // 找到了要删除的结点位置
                if( trNode->node == node )
                {
                    LinkList_Delete(list, i);     // 删除该位置的树结构成员
                    
                    free(trNode);                 // 释放内存,防止内存泄漏
                    
                    index = i;                    // 标记要删除结点在组织链表中的位置
                    
                    break;                        // 跳出遍历树结构操作
                }
            }
            // 删除位置真实存在
            if( index >= 0 )
            {  
            	  // 有双亲
                if( parent != NULL )
                {
                	   // 遍历孩子结点链表,将其从双亲的孩子结点中删除
                     for(i=0; i<LinkList_Length(parent->child); i++)
                     {
            	  				 // 定义结点链表结构体变量,存放遍历的双亲的孩子结点链表成员
                         TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i);
                         // 找到要删除的孩子结点
                         if( trNode->node == node )
                         {
                         	   // 将其从双亲的孩子链表中删除
                             LinkList_Delete(parent->child, i);
                             // 释放内存,防止内存泄漏
                             free(trNode);
                             // 跳出遍历孩子结点链表操作
                             break;
                         }
                     }               
                }
                // 如果存在子孙结点,递归删除其他结点
                while( LinkList_Length(node->child) > 0 )
                {
                	  // 获取子孙结点链表首元素
                    TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0);
                    // 调用递归函数,继续删除
                    recursive_delete(list, trNode->node);
                }
                // 销毁子孙结点链表
                LinkList_Destroy(node->child);
                // 释放内存,防止内存泄漏
                free(node);
            }
        }
    }

    6.获取指定的结点

    实现代码如下:

    // 获取树结构指定位置pos的元素
    GTreeData* GTree_Get(GTree* tree, int pos)
    {
        // 定义树结点结构体变量,存放要获取结点当前位置的元素地址
        TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);
        GTreeData* ret = NULL;    
        // 要获取的结点的位置元素合法,返回该结点成员数据
        if( trNode != NULL )
        {
            ret = trNode->node->data;
        }
        
        return ret;
    }

    从上面代码上可以发现,获取结点有点类似删除结点,就是少了删除的操作。

    7.获取根结点

    获取根结点其实就是获取树结构的首元素,实现代码如下:

    // 获取树结构的根结点元素
    GTreeData* GTree_Root(GTree* tree)
    {
        return GTree_Get(tree, 0);      // 调用获取树结点函数
    }

    8.获取树结构的高度

    获取树结构的高度,我们可以这样考虑,先求出根结点的子结点的高度,然后找到最大值后再加上1不就是整个树的高度了;但

    是有一个问题就是,子结点还会有子结点,那怎么办呢?好办呀,按照如上的方法、利用递归的思想,一层层的求子结点的高

    度,最后返回的结果就是整个树的高度了,实现代码如下:

    // 获取树结构的高度
    int GTree_Height(GTree* tree)
    {
        // 定义树结点结构体变量,存放子树结点
        TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);
        int ret = 0;
        // 根结点合法,调用获取树结构高度递归函数,返回高度
        if( trNode != NULL )
        {
            ret = recursive_height(trNode->node);
        }
        
        return ret;
    }

    递归函数实现代码如下:

    // 获取树结构高度递归函数
    static int recursive_height(GTreeNode* node)
    {
        int ret = 0;
        // 结点合法
        if( node != NULL )
        {
            int subHeight = 0;       // 子结点
            int i = 0;               // 循环变量
            // 遍历子树的孩子结点链表
            for(i=0; i<LinkList_Length(node->child); i++)
            {
                // 依次取出子树结点的孩子结点
                TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);
                // 调用求高度递归函数,计算子结点
                subHeight = recursive_height(trNode->node);
                // 求计算结果的最大值,边计算边找最大值
                if( ret < subHeight )
                {
                    ret = subHeight;
                }
            }
            // 计算结果加1就是整个树的高度
            ret = ret + 1;
        }
        
        return ret;
    }

    9.获取树结构的全体成员数量

    获取树结构的全体成员数量也就是获取整个组织链表的长度,实现代码如下:

    // 获取树结构的元素数量
    int GTree_Count(GTree* tree)
    {
        return LinkList_Length(tree);
    }

    10.获取树结构的度

    获取树结构的度的实现方法和获取树结构的高度的实现思想差不多,也是先将根结点的度求出来,然后找求根结点所有子树结点

    的度,然后找出最大值,就是树的度数了,还是要利用递归的思想。实现代码如下:

    // 获取树结构的度
    int GTree_Degree(GTree* tree)
    {
        // 定义树结点结构体变量,存放子树结点
        TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);
        int ret = -1;    
        // 根结点合法,调用获取树结构度递归函数,返回高度
        if( trNode != NULL )
        {
            ret = recursive_degree(trNode->node);
        }
        
        return ret;
    }

    递归函数代码实现如下:

    // 获取树结构度递归函数
    static int recursive_degree(GTreeNode* node)
    {
    		int ret = -1;
        
        // 结点合法
        if( node != NULL )
        {
            int subDegree = 0;        // 子结点度
            int i = 0;
            // 获取子结点的长度,即度
            ret = LinkList_Length(node->child);
            // 变量子树孩子结点的成员
            for(i=0; i<LinkList_Length(node->child); i++)
            {
            	  // 依次取出子树结点的孩子结点
                TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);            
                // 调用求度递归函数,计算子结点度
                subDegree = recursive_degree(trNode->node);            
                // 求计算结果的最大值
                if( ret < subDegree )
                {
                    ret = subDegree;
                }
            }
        }
        
        return ret;
    }

    本节中的树结构是一种通用的数据结构。

    利用链表组织树结点优点:能够便利的存取结点。

    利用链表组织树结点缺点:链表的维护具有一定复杂性。

    树结构的非线性特性和递归定义的特性是树结构实现难度较大的根本原因。

    至此,有关树结构的基本操作已经实现了,因是初学,有描述不妥的地方还清大神加以指正。

    通用树结构C代码实现


    展开全文
  • MySQL 查询 树结构

    万次阅读 2019-06-28 16:25:15
    1. 关于树结构 此类结构的数据,通常需要表结构中含有id 、parentId等自关联字段,有时为了提高查询效率还可增加更多冗余字段,如index,index的值为所有父级目录的id字符串集合。 关于树结构数据的组装,常见的...
  • 树结构概述

    千次阅读 2020-04-06 10:26:50
    文章目录什么是树结构?简介为什么要使用树结构?树的基本概念根节点双亲节点路径节点的度节点的权叶子节点子树层树的高度森林 什么是树结构? 树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为...
  • C++树结构

    千次阅读 2017-07-27 22:08:57
    树树是什么在计算机科学中,(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做...
  • 扁平化数据转化为树结构

    千次阅读 2021-04-14 10:31:06
    扁平化数据转化为树结构 function toTree({arrayList, pidStr = 'pid', idStr = 'id', childrenStr = 'children'}) { let listOjb = {}; // 用来储存{key: obj}格式的对象 let treeList = []; // 用来储存最终树形...
  • 一些常见的树结构

    千次阅读 2017-06-04 20:14:24
    二叉搜索  1.所有非叶子结点至多拥有两个儿子(Left和Right);  2.所有结点存储一个关键字;  3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;  如:   ...
  • 使用递归方式过滤树结构

    千次阅读 2018-11-10 22:09:04
    使用递归方式过滤树结构 本文介绍使用递归方法过滤树数据结构。 需求 给定叶子节点,过滤树。下面通过示例说明。 示例数据结构: 0 / | \ 1 2 3 / \ | / \ 4 5 6 7 8 给定条件为:4 和 6,如果所有...
  • js树结构转数组 扁平化 树结构平铺
  • js数组和树结构数据相互转换

    万次阅读 多人点赞 2019-07-10 17:06:04
    数组转树结构采取递归和非递归两种方式,树结构转扁平化数组采取深度优先遍历(递归和非递归两种方式)和广度优先遍历实现。 let arr =[ {id:2,name:'部门B',parentId:0}, {id:3,name:'部门C',parentId:1}, {id:1...
  • 文章目录关于数据结构中树结构的相关分享一、传统的数据结构中的树结构1.1 二叉查找树1.2 平衡二叉树1.3 平衡二叉树之红黑树1.4 B 树1.5 B+树1.6 B* 树二、字典树 ( Trie树 )三、决策树(利用信息论的熵依靠决策树做...
  • java递归生成树结构(类似菜单)

    千次阅读 2019-07-19 17:17:45
    上面是基本的树结构 下面是java代码生成这样的树的json代码 这里不包括展现,展现很简单 /*** * pid 父id * allList 所有数据库查出来的list数据 */ public List<Map<String,Object>> getChild...
  • Python 实现树结构

    万次阅读 多人点赞 2018-03-23 16:57:36
    自然界中的和计算机科学中的之间的区别在于数据结构的根在顶部,其叶在底部。 1 的相关定义 节点:的基本部分。它可以有一个名称,我们称之为“键”。节点也可以有附加信息。我们将这个附加信息称为...
  • * 向树结构中添加数据 * * @param object elements 元素信息 * ps: elements 是元素的element类整个对象 * * @returns bool */ setChildren (elements) { let isOk = false let catalog = this.elem...
  • JS递归遍历树结构

    千次阅读 2020-03-19 16:26:00
    JS递归遍历树结构上代码 上代码 // 树结构 const options = [ { value: 'zhejiang', label: 'Zhejiang', children: [ { value: 'hangzhou', label: 'Hangzhou', children: [ ...
  • Java代码实现封装多级树结构对象

    千次阅读 2019-02-27 09:47:34
    在开发中,我们经常见到,前端展示树状结构的,这时候就需要后端去封装一个多级树结构对象,前端根据这样结构的数据去渲染数据,这篇文章讲的是如何封装成多级树结构对象。 正文: 1.先封装个树结构的对象 @Data...
  • mapTree (org) { const haveChildren = Array.isArray(org.children) && org.children.length > 0; return {  //分别将我们查询出来的值做出改变他的key title: org.groupName, ...
  • go语言菜单树结构

    千次阅读 2018-07-26 11:29:08
    GO语言菜单树结构实现,Menu是数据库表映射。MenuTree是树结构菜单,目前只考虑2级菜单。后面附源码,亲测可用 package models import ( "github.com/astaxie/beego/orm" "time" ) ...
  • 递归遍历树结构-已解决

    千次阅读 2017-08-28 11:58:19
    在项目中用到导航树结构,所以就用递归写了一个遍历导航树的功能。 表结构: /** * 递归获取菜单 * * @param roleKey * @param systemCode * @return */ public String getSysMenuJson(String ...
  • javascript 遍历树结构(递归)

    千次阅读 2020-04-13 18:44:17
    //选中的节点 var j = 0; function bianli(checkedData) { for (var i in checkedData) { //过滤,只处理满足此条件的,不需要过滤则去掉这层if if (checkedData[i].TYPE == "emp") { checkId[j++] = checkedData...
  • java list集合转多叉树结构工具类

    万次阅读 2018-09-28 17:46:07
    因为项目需求,修改将如下数据格式的数据转为树结构数据: id parent 1 null 2 null 3 null 4 1 5 1 6 1 7 2 8 2 9 3 10 4 11 7 ...
  • java后台封装树结构形式数据

    千次阅读 2019-01-21 20:35:48
    然后了解我们的数据库结构 数据库中顶级节点的父节点为空,即PARENTORGID为空,其余的节点的PARENTORGID都为父亲节点的id 2.下面开始进行后台编码实现 方法为,首先再数据库中查询出所有组织结构的数据,数据格式...
  • sql查询树结构效率慢的改进方法

    千次阅读 2020-05-06 14:53:05
    用sql的树结构查询慢,改为用代码处理数据的方式: package com.ropeok.common.util; import com.alibaba.fastjson.JSON; import com.alibaba.fastjson.JSONArray; import com.alibaba.fastjson.JSONObject; ...
  • PyQt5中树结构的实现

    万次阅读 2018-08-15 23:02:29
    树的实质是很多条数据按照一定的内在关系,分层级显示出来。因此每一条数据包括数据项...对于静态的数据,实现树结构可以直接在Qt中拖入一个Tree Widget控件,然后右键点击它,选择编辑。 其中column是每一条数...
  • INCREMENT=68 DEFAULT CHARSET=utf8 COMMENT='文件分类管理' 方案一: 一般情况下,我们自己写递归代码的方式 (1)获取结构数据接口 /** * 获取文件分类结构 * * @return */ @Override public ...
  • java实现角色权限的菜单树结构

    千次阅读 2020-07-10 14:19:55
    通过迭代器和递归实现查询用户角色的权限 业务层 /** * @author * @date 2020-07-09 15:36:12 * @description 根据id查找用户权限信息 */ @Override public SysUserDTO getUserMenuDetail(String id) { ...
  • 最近编译原理学到语法分析树,需要频繁、大量地画树结构,一开始我使用了画图、PPT等工具,或是在纸上画好然后拍下来,但很是麻烦。 经同学推荐,找到了这样一个树的自动生成工具:Syntax Tree Generator。它的使用...
  • 对比线性表与结构,它们有很大的不同:

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 938,071
精华内容 375,228
关键字:

树结构