数据结构树的基本操作

2018-05-14 18:45:16 IT_xiaoye 阅读数 1021

何为二叉树

概念:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成

特点:

  • 每个结点最多有两棵子树
  • 二叉树的子树有左右之分,其子树的次序不能颠倒

基本操作介绍

  • 二叉树的遍历(递归和非递归),可以说是所有操作中最重要的
  • 求树的结点个数
  • 求树的叶子结点的个数
  • 求第K层结点的个数
  • 求树的高度
  • 在树中查找指定元素
  • 给定一个结点,查找它的父结点
  • 复制一棵二叉树
  • 求一个二叉树的镜像(递归和非递归)
  • 构建一个二叉树(给出前序遍历结果,带有空结点)
  • 还原一个二叉树(给出前序和中序遍历结果,不带空节点)

话不多说,直接附上代码来解释这些操作

结构体声明:

typedef char TreeNodeType;

typedef struct TreeNode{
    struct TreeNode* lchild;//左孩子结点
    struct TreeNode* rchild;//右孩子结点
    TreeNodeType data;
}TreeNode;

函数体声明:

//初始化二叉树
void TreeNodeInit(TreeNode** root);
//先序遍历二叉树
void PreOrder(TreeNode* root);
//中序遍历
void InOrder(TreeNode* root);
//后序遍历
void PostOrder(TreeNode* root);
//层序遍历
void LevelOrder(TreeNode* root); 
//求树的节点个数
size_t TreeSize(TreeNode* root);
//求树的叶节点的个数
size_t LeafTreeSize(TreeNode* root);
//求第K层节点的个数
size_t TreeLevelSize(TreeNode* root,size_t k);
//求树的高度
size_t TreeHeight(TreeNode* root);
//在树中查找指定元素
TreeNode* TreeFind(TreeNode* root, TreeNodeType to_find);
//给一个节点,找它的父节点
TreeNode* Parents(TreeNode* root,TreeNode* node);
//非递归遍历二叉树
void PreOrderByLoop(TreeNode* root);//前
void InOrderByLoop(TreeNode* root);//中
void PostOrderByLoop(TreeNode* root);//后
//求一个二叉树的镜像
//递归版
void TreeMirror(TreeNode* root);
//非递归版
void TreeMirrorByLoop(TreeNode* root);      
//销毁一棵树
TreeNode* TreeDestroy(TreeNode* root);

嘿嘿,下面开始疯狂的粘贴代码了
这里写图片描述

简单明了初始化和销毁,不解释

//初始化
void TreeNodeInit(TreeNode** root)
{
    if(root == NULL)
    {
        //非法输入
        return;
    }
    *root = NULL;
}
//销毁单个结点
void Destroy(TreeNode* root)
{
    free(root);
}

下面进行递归和非递归的遍历,这个才是最重要的,其他的都可以不管,这个必须要仔细看
这里写图片描述

//先序遍历(根节点,左子树,右子树)
void PreOrder(TreeNode* root)
{
    if(root == NULL)                                                                                                                    
    {
        //遇到空节点就返回,递归出口
        return;
    }
    //访问该节点
    printf("%c ",root->data); //先访问根节点
    PreOrder(root->lchild);//再访问左子树
    PreOrder(root->rchild);//再访问右子树
}
//中序遍历(左子树,根节点,右子树)
void InOrder(TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }
    InOrder(root->lchild);//遍历到最后一个左子树叶子结点
    printf("%c ",root->data);//和前序遍历不同就是访问语句调了个位置
    InOrder(root->rchild);
}
//后序遍历(左子树,右子树,根节点)
void PostOrder(TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }   
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    printf("%c ",root->data);//看到这里应该懂了前中后遍历了吧
}   
//层序遍历(比较复杂,各位得好好捋一捋)
void LevelOrder(TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }
    //1.先把根节点插入队列
    SeqQueue seq;
    SeqQueueInit(&seq);
    SeqQueuePush(&seq,root);
    //2.循环的取队首元素
    while(1){
    SeqQueueType node;
    int ret = SeqQueueGetTop(&seq,&node);
    if(ret == 0)
    {
        return;
    }
    //3.访问队首元素并出队列
    SeqQueuePop(&seq);
    if(node != NULL)
    {
    printf("%c ",node->data);
    //4.将队首元素的左子树节点和右子树节点都依次入队列
    SeqQueuePush(&seq,node->lchild);
    //5.进入下一次循环,直到队列为空,说明遍历完了
    SeqQueuePush(&seq,node->rchild);
    }                                                                                                                                   
    }
}
//非递归遍历二叉树(前序)
void PreOrderByLoop(TreeNode* root)
{
    if(root == NULL)
    {   
        return;
    }   
    SeqStack stack;
    SeqStackInit(&stack);
    SeqStackPush(&stack,root);
    while(1)
    {   
        //取栈顶元素
        SeqStackType cur;
        int ret = SeqStackFindTop(&stack,&cur);
        //如果栈空的话说明已经遍历完了
        if(ret == 0)
        {   
            break;
        }   
        //访问栈顶元素并且出栈
        SeqStackPop(&stack);
        printf("%c ",cur->data);
        //先把每个节点的右孩子节点入栈,
        //再把左孩子节点入栈,
        //保证每次访问完自身后,再访问左子树
        if(cur->rchild != NULL)
        {   
            SeqStackPush(&stack,cur->rchild);
        }   
        if(cur->lchild != NULL)
        {   
            SeqStackPush(&stack,cur->lchild);                                                                                           
        }   
    }   
    printf("\n");
}
//非递归遍历二叉树(中序)
void InOrderByLoop(TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }
    SeqStack stack;
    SeqStackInit(&stack);
    SeqStackType cur = root;
    while(1)
    {
        while(cur != NULL)
        {
            SeqStackPush(&stack,cur);
            cur = cur -> lchild;
        }
        SeqStackType top;
        int ret = SeqStackFindTop(&stack,&top);
        if(ret == 0)
        {
            break;
        }
        printf("%c ",top->data);
        SeqStackPop(&stack);
        cur = top->rchild;
    }
}       
//非递归遍历二叉树(后序)
void PostOrderByLoop(TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }
    SeqStack stack;
    SeqStackInit(&stack);
    TreeNode* cur = root;
    //保存上一个访问的元素
    TreeNode* pre = NULL;
    while(1)
    {
        //循环的将左子树入栈
        while(cur!=NULL)
        {
            SeqStackPush(&stack,cur);
            cur = cur -> lchild;
        }
        //取出栈顶元素
        SeqStackType top;
        int ret = SeqStackFindTop(&stack,&top);
        if(ret == 0)
        {
            return;
        }
        //在访问前要判断
        //   1.它的右子树是否为空
        //   2.或者判断它的右子树是否刚被访问过
        //满足任意一个条件就可以访问当前元素并将其出栈
        if(top->rchild == NULL || top->rchild == pre)
        {                                                                                                                               
            printf("%c ",top->data);
            SeqStackPop(&stack);
            pre = top;
                    }
        //否则cur = cur->rchild ,跳到循环开始继续
        else{
            cur = top->rchild;
        }
    }
}

其余小操作

//在树中查找指定元素
TreeNode* TreeFind(TreeNode* root, TreeNodeType to_find)
{
    if(root == NULL)
    {
        return NULL;
    }
    if(root->data == to_find)
    {
        return root;
    }
    TreeNode* Lresult = TreeFind(root->lchild,to_find);
    TreeNode* Rresult = TreeFind(root->rchild,to_find);
    //时间复杂度为O(n),最坏的情况是所有元素都遍历了也没找到
    //空间复杂度也是O(n)
    return Lresult == NULL?Rresult:Lresult;
}    
//求树的高度
size_t TreeHeight(TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    //比较左右两子树的深度,返回深度大的那个
    size_t lheight = TreeHeight(root->lchild);
    size_t rheight = TreeHeight(root->rchild);
    //相当于是调用次数的比较
    return lheight >= rheight? lheight+1:rheight+1;
    //下面的代码也可以实现相同功能,
    //但是函数会被递归调用三次,上一种方式只会被递归调用两次
    //所以效率比较低
    //return TreeHeight(root->lchild) >= TreeHeight(root->rchild)?TreeHeight(root->lchild):TreeHeight(root->rchild);
}
    //求树的叶节点个数                                                                                                                      
size_t LeafTreeSize(TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    if(root->lchild == NULL && root->rchild == NULL)
    {
        return 1;
    }
    return LeafTreeSize(root->lchild) + LeafTreeSize(root->rchild);

}

//求第K层节点的个数
size_t TreeLevelSize(TreeNode* root,size_t k)
{
    //我们规定树从第一层开始
    if(root == NULL || k < 1)
    {
        return 0;
    }
    if(k == 1)
    {
        return 1;
    }
    return TreeLevelSize(root->lchild,k-1) + TreeLevelSize(root->rchild,k-1);
}
//复制一棵树
TreeNode* TreeClone(TreeNode* root)
{
    if(root == NULL)
    {
        return NULL;
    }
    TreeNode* newnode = CreateTreeNode(root->data);
    newnode->lchild = TreeClone(root->lchild);
    newnode->rchild = TreeClone(root->rchild);
    return newnode;
}

//求树的节点个数
size_t TreeSize(TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->lchild) + TreeSize(root->rchild);
}
//给一个节点,找它的父节点
TreeNode* Parents(TreeNode* root,TreeNode* node)
{
    if(root == NULL)
    {
        return NULL;
    }
    if(root->lchild == node || root->rchild == node)
    {
        return root;
    }
    TreeNode* Lresult = Parents(root->lchild,node);
    TreeNode* Rresult = Parents(root->rchild,node);
    return Lresult != NULL? Lresult:Rresult;
}

//求一个二叉树的镜像(递归版)
void TreeMirror(TreeNode* root)
{
    if(root == NULL)                                                                                                                    
    {
        return;
    }
    TreeNode* tmp = root->lchild;
    root->lchild = root->rchild;
    root->rchild = tmp;
    TreeMirror(root->lchild);
    TreeMirror(root->rchild);
}
//非递归版
void TreeMirrorByLoop(TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }
    SeqStack stack;
    SeqStackInit(&stack);
    SeqStackPush(&stack,root);
    while(1)
    {
        SeqStackType top;
        int ret = SeqStackFindTop(&stack,&top);
        if(ret == 0)
        {
            return;
        }
        TreeNode* tmp = top->lchild;
        top->lchild = top->rchild;
        top->rchild = tmp;
        SeqStackPop(&stack);
        if(top -> lchild != NULL)
        {
            SeqStackPush(&stack,top->lchild);
        }
        if(top -> rchild != NULL)
        {
            SeqStackPush(&stack,top->rchild);
        }
    }
}
2017-11-05 10:04:39 hester_hester 阅读数 7627

目标效果:



dsp0603.cpp页面;

#include <stdio.h>
#include <stdlib.h>

#define ElemType char //二叉树中数据元素类型
#include "bintree.h"  //二叉树的实现

//打印结点数据(作为Visit函数)
Status print(char);
//计算二叉树中叶子结点的个数
int LeafCount(BiTree bt);
//计算二叉树的深度
int Deapth(BiTree bt);
//按缩进方式打印二叉树
void PrintTreeIndent(BiTree bt, int indent);

///////////////////////////////////////////////////////////
// 主程序
int main()
{
    BiTree bt = 0;

    //建立二叉树
    printf("建立二叉树(按先序输入二叉树中的结点,空格表示空树)\n");
    if( CreateBiTree(bt)==ERROR ) {
        printf("ERROR: call CreateBiTree\n");
        system("pause");
        exit(1);
    }
    PrintTree(bt);

    //遍历二叉树
    printf("\n先序遍历: ");
    if( PreOrderTraverse(bt)==ERROR )
        printf("ERROR: call PreOrderTraverse\n");
    printf("\n中序遍历: ");
    if( InOrderTraverse(bt)==ERROR )
        printf("ERROR: call InOrderTraverse\n");
    printf("\n后序遍历: ");
    if( PostOrderTraverse(bt)==ERROR )
        printf("ERROR: call PostOrderTraverse\n");

    printf("\n按层遍历: ");
    if( LevelOrderTraverse(bt)==ERROR )
        printf("ERROR: call LevelOrderTraverse\n");
    //二叉树的应用
    printf("\n二叉树中叶子结点的个数: %d\n", LeafCount(bt));
    printf("\n二叉树的深度: %d\n", Deapth(bt));
    printf("\n按缩进形式打印:\n");
    PrintTreeIndent(bt,1);

    //销毁二叉树
    DestroyBiTree(bt);

    system("pause"); //暂停以便查看结果
    return 0;
}


///////////////////////////////////////////////////////////
// 函数实现

//计算二叉树中叶子结点的个数
int LeafCount(BiTree bt)
{
    if(!bt)          //结点为空
        return 0;
    if(!bt->lchild&&!bt->rchild)      //没有子节点了
        return 1;
    else
        return LeafCount(bt->lchild)+LeafCount(bt->rchild);
}

//计算二叉树的深度
int Deapth(BiTree bt)
{
	int height,leftH,rightH;     //左右子树的深度和最深的深度
	if(!bt)
		height=0;
	else{
		leftH=Deapth(bt->lchild);
		rightH=Deapth(bt->rchild);
		if(leftH>rightH)
			height=leftH+1;
		else
			height=rightH+1;;
	}
	return height;
}

//按缩进方式打印二叉树
void PrintTreeIndent(BiTree bt, int indent)
{
	if(bt){
		for(int i=0;i<10-indent;i++)     //这里固定了以10减,正常最规范的应该用树的深度减
			printf(" ");
		printf("%c",bt->data);
		printf("\n");
		PrintTreeIndent(bt->lchild,indent+1);
		PrintTreeIndent(bt->rchild,indent+1);
	}
}



bintree.h页面:
#ifndef BINTREE_H_INCLUDED
#define BINTREE_H_INCLUDED

#include <stdlib.h>
#include "ds.h"

//数据元素的缺省类型用char
#ifndef ElemType
#define ElemType char
#define ELEMTYPE_TAG
#endif
/*下面使用TElemType如同ElemType*/
#define TElemType ElemType
#define QElemType BiTree     //队列元素为二叉树指针类型,所以这里不是普通的char类型
#define MAXQSIZE 100
///////////////////////////////////////////////////////////
// 二叉链表类型
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;
//循环队列类型定义
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

//初始化队列
Status InitQueue(SqQueue &Q);
//元素入队
Status EnQueue(SqQueue &Q,QElemType e);
//元素出队
Status DeQueue(SqQueue &Q,QElemType &e);
//销毁队列
Status DestroyQueue(SqQueue &Q);
//队列判空
Status QueueEmpty(SqQueue Q);
// 二叉链表的基本操作

//新建二叉链表结点
BiTree MakeNode(TElemType e, BiTree lch, BiTree rch)
{
    BiTree p = (BiTree)malloc(sizeof(BiTNode));
    p->data = e;
    p->lchild = lch;
    p->rchild = rch;
    return p;
}

//按先序次序输入二叉树中的结点值(字符)构造二叉树
Status CreateBiTree(BiTree &T)
{
    char ch;
    read(ch); // NOTE: 这里用字符类型
    if( ch==' ' ) //空格代表空指针
        T = 0;
    else {
		T=(BiTree)malloc(sizeof(BiTNode));
		if(!T)
			return ERROR;
		else{
			T->data=ch;
			CreateBiTree(T->lchild);
			CreateBiTree(T->rchild);
		}
    }
    return OK;
}

//销毁二叉树
Status DestroyBiTree(BiTree &T)
{
    T=NULL;
    return OK;
}

//先序遍历二叉树T,对每个结点数据调用Visit函数
Status PreOrderTraverse(BiTree T)
{
	if(T){
		printf("%c",T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
    return OK;
}

//中序遍历二叉树T,对每个结点数据调用Visit函数
Status InOrderTraverse(BiTree T)
{
    if(T){
		InOrderTraverse(T->lchild);
		printf("%c",T->data);
		InOrderTraverse(T->rchild);
	}
    return OK;
}

//后序遍历二叉树T,对每个结点数据调用Visit函数
Status PostOrderTraverse(BiTree T)
{
    if(T){
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		printf("%c",T->data);
	}
    return OK;
}

//按层次顺序遍历二叉树T,对每个结点数据调用Visit函数
Status LevelOrderTraverse(BiTree T)
{
    //将每一层的节点分别入队列,然后分别读取,读取后继续将它们的子节点入队,所以保证是按照一层一层来遍历的
    BiTree P=T;
    SqQueue Q;
    InitQueue(Q);   //初始化队列
    if(P)
    {
        EnQueue(Q,P);
        while(!QueueEmpty(Q))
        {
            DeQueue(Q,P);   //出队列
            printf("%c",P->data);
            if(P->lchild)
                EnQueue(Q,P->lchild);
            if(P->rchild)
                EnQueue(Q,P->rchild);
        }
    }
    DestroyQueue(Q);
    return OK;
}

//以直观方式打印二叉树
void PrintTree(BiTree t, int level=0)
{
    int i;
    if(t) {
        PrintTree(t->rchild, level+1);
        for(i=0; i<level; i++) printf("    ");
        write(t->data); write('\n');
        PrintTree(t->lchild, level+1);
    }
}

//构造一个空队列
Status InitQueue(SqQueue &Q)
{
    Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.base)
        return ERROR;
    Q.front=Q.rear=0;
    return OK;
}
//元素入队
Status EnQueue(SqQueue &Q,QElemType e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front)
        return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}
//元素出队
Status DeQueue(SqQueue &Q,QElemType &e)
{
    if(Q.front==Q.rear)
        return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
}
//判断队列是否为空
Status QueueEmpty(SqQueue Q)
{
    if(Q.rear==Q.front)
        return OK;
    else
        return ERROR;
}
//销毁队列
Status DestroyQueue(SqQueue &Q)
{
    if(!Q.base)
        return ERROR;
    Q.rear=Q.front;
    free(Q.base);
    return OK;
}
//取消缺省类型的定义以免影响其它部分
#ifdef ELEMTYPE_TAG
#undef ElemType
#undef ELEMTYPE_TAG
#endif

#endif //BINTREE_H_INCLUDED


说几个小问题:
1.项目里有层次遍历,需要使用队列存储,我偷懒直接复制的前边博客里循环队列操作的代码,结果出现以下错误,return还不变成蓝色(code blocks中return等关键字是蓝色),百度是因为中文空格和英文空格的原因,只要把空格都删掉然后重新在英文输入法中把空格重新敲一遍就行了的。
2.循环队列我定义了100个元素,这也就意味着层次遍历时,结点个数最多为99个,不知道循环队列插入时判满后能不能再进行动态分配,课本上是没讲的,如果不能的话存储用链式队列比较好,对个数没要求。
3.凹入打印那里,因为空格个数递减,所以我是用一个初始值10减去一个递增变量,正确初始值应该为树的深度,因为每一层的长度一样,最多有个数为深度的不同凹入情况,但是因为输入的都是简单树,加上循环队列那里就对结点个数有要求了,所以这里就不那样写了,自己明白就好。


我的项目一般都会在学校机房里做前半部分,环境为VC6.0,后半部分是在自己电脑上做的,环境为code blocks,最近几次在电脑上都是新建一个项目,删掉main函数后导入几个操作页面,但是修改后还是修改的原先那个vc项目,并且在原项目中是运行的之前的结果的,我上传的也是原项目,所以如果下载源码,不要直接运行debug中的那个exe文件,打开后编译运行一下就好。


源码链接:点击打开链接






2017-08-01 23:52:35 believe_s 阅读数 1311

是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点,所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位,这个结点称为该树的根结点,或称为树根。
头文件 tree.h

#ifndef __TREE_H__
#define __TREE_H__

#include "error.h"

struct _treeNode;                   // 结构体声明

// 孩子结点链表的类型
typedef struct _childNode
{
    struct _treeNode * childNode;
    struct _childNode* next;        // 指向孩子结点链表下一个元素
}ChildNode;

// 树节点类型
typedef char TreeData;
typedef struct _treeNode
{
    TreeData data;
    struct _treeNode * parent;      // 指向父节点的指针
    struct _treeNode * next;        // 指向链表的下一个结点
    struct _childNode* childList;   // 孩子链表的头节点
    int degree;                     // 结点的度
}TreeNode;

typedef struct _tree
{
    struct _treeNode* head;         // 树链表的头节点
    int len;                        // 树结点个数
}Tree;

// 定义一个函数指针类型
typedef void(*TreePrint)(TreeNode *node);

Tree* Create_Tree();

// pos 代表要插入结点父亲结点的位置
// 约定:
// 1 新插入的结点插入在当前父亲结点所有孩子的右边
// 2 根节点的位置是 0
int Insert_Tree (Tree* tree, TreeData data, int pos);

// 打印树
void Display (Tree* tree, TreePrint pFunc);

// 删除结点
int Delete (Tree* tree, int pos, TreeData *x);

// 求指定位置树结点的值
int Tree_Get (Tree* tree, int pos, TreeData *x);

// 清空树中所有的节点
int Tree_Clear (Tree* tree);

// 树的销毁 
void Tree_Destroy   (Tree* tree);

// 获取根节点的地址
TreeNode* Tree_Root (Tree* tree);

// 求树的结点个数
int Tree_Count  (Tree* tree);

// 求树的高度
int Tree_Height (Tree* tree);

// 求树的度
int Tree_Degree (Tree* tree);

// 打印
void printA (TreeNode* node);

#endif  // __TREE_H__


源文件 tree.c

#include "tree.h"
#include <stdlib.h>

Tree *Create_Tree()
{
    // 创建树节点
    Tree* tree = (Tree*) malloc(sizeof(Tree)/sizeof(char));
    if (NULL == tree)
    {
        errno = MALLOC_ERROR;
        return NULL;
    }

    // 给树结点链表创建头节点
    tree->head = (TreeNode*) malloc(sizeof(TreeNode)/sizeof(char));
    if (NULL == tree->head)
    {
        errno = MALLOC_ERROR;
        free (tree);
        return NULL;
    }

    tree->head->parent    = NULL;
    tree->head->childList = NULL;
    tree->head->next      = NULL;   // 代表树中没有结点

    // 空树结点为0
    tree->len = 0;

    return tree;
}

int Insert_Tree (Tree* tree, TreeData data, int pos)
{
    if (NULL == tree || pos < 0 || pos > tree->len)
    {
        errno = ERROR;
        return FALSE;
    }

    if (pos != 0 && tree->len == pos)
    {
        errno = ERROR;
        return FALSE;
    }

    // 新建结点
    TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode)/sizeof(char));
    if (NULL == node)
    {   
        errno = MALLOC_ERROR;
        return FALSE;
    }

    node->data = data;
    node->next = NULL;

    // 创建该新节点的孩子结点链表的头节点
    node->childList = (ChildNode*) malloc(sizeof(ChildNode)/sizeof(char));
    if (NULL == node->childList)
    {   
        errno = MALLOC_ERROR;
        free (node);
        return FALSE;
    }   
    node->childList->next      = NULL;
    node->childList->childNode = NULL;

    node->degree = 0;

    int i;
    // 找父节点
    TreeNode* parent = tree->head->next;     // 当前树节点的第一个结点
    for (i = 0; i < pos; i++)
    {
        parent = parent->next;
    }
    node->parent = parent; 

    // 在父亲结点的子结点链表中加入一个结点
    if (parent != NULL)
    {
        // 创建一个孩子结点
        ChildNode* childnode = (ChildNode*) malloc(sizeof(ChildNode)/sizeof(char));
        if (NULL == childnode)
        {
            errno = MALLOC_ERROR;
            free (node->childList);
            free (node);
            return FALSE;
        }
        childnode->childNode = node;
        childnode->next      = NULL;

        // 加入到父亲结点子结点链表当中
        ChildNode* tmp = parent->childList;   // 子结点链表的头节点
        while (tmp->next)
        {   
            tmp = tmp->next;
        }
        tmp->next = childnode;
        parent->degree += 1;
    }

    TreeNode* tmp = tree->head;              // 树节点链表的头节点
    while (tmp->next)
    {
        tmp = tmp->next;
    }
    tmp->next = node;
    tree->len += 1;

    return TRUE;
}

// 递归打印结点
void r_display (TreeNode* node, int gap, TreePrint pFunc)
{
    if (NULL == node)
    {
        return;
    }

    // 打印距离前一个结点的距离
    int i;
    for (i = 0; i < gap; i++)
    {
        printf ("%c", '-');
    }

    // 打印结点自己
    // printf ("%c\n", node->data);
    pFunc (node);

    ChildNode* child = node->childList->next; // 该结点的第一个孩子
    // 打印该结点的孩子
    while (child)
    {
        r_display (child->childNode, gap+4, pFunc);
        child = child->next;  // 下一个孩子
    }
}

void Display (Tree *tree, TreePrint pFunc)
{
    if (NULL == tree)
    {
        return;
    }

    r_display (tree->head->next, 0, pFunc);
}

void r_delete (Tree *tree, TreeNode *node)
{
    if (NULL == tree || NULL == node)
        return;

    // 从树链表中移除这个结点,找node的前一个结点
    TreeNode* tmp = tree->head;  // 链表的头节点
    while (tmp->next)
    {
        if (tmp->next == node)
        {
            tmp->next = node->next;
            tree->len--;
            break;
        }
        tmp = tmp->next;
    }

    // 将父亲结点中子结点链表中指向node的结点删除
    TreeNode* parent = node->parent;
    if (NULL != parent)
    {
        ChildNode* tmp = parent->childList;  // 子结点链表的头节点
        while (tmp->next)
        {
            if (tmp->next->childNode == node)
            {
                ChildNode* p = tmp->next;
                tmp->next    = p->next;
                free (p);
                parent->degree--;
                break;
            }
            tmp = tmp->next;
        }
    }

    // 将该结点的孩子结点删掉
    ChildNode* child = node->childList->next; 
    // 子结点链表中的第一个结点
    while (child)
    {
        ChildNode* pchild = child->next;
        r_delete (tree, child->childNode);
        child  = pchild;
    }

    free (node->childList);
    free (node);
}

int Delete (Tree *tree, int pos, TreeData *x)
{
    if (NULL == tree || pos < 0 || pos > tree->len)
    {
        errno = ERROR;
        return FALSE;
    }

    if (0 != pos && tree->len == pos)
    {
        errno = ERROR;
        return FALSE;
    }

    int i;
    // 找结点
    TreeNode* current = tree->head->next;  
    for (i = 0; i < pos; i++)
    {
        current = current->next;
    }

    *x = current->data;

    r_delete (tree, current);

    return TRUE;

}

int Tree_Get (Tree* tree, int pos, TreeData *x)
{
    if (NULL == tree || pos < 0 || pos > tree->len)
    {
        errno = ERROR;
        return FALSE;
    }

    if (0 != pos && tree->len == pos)
    {
        errno = ERROR;
        return FALSE;
    }

    int i;
    // 找结点
    TreeNode* current = tree->head->next;  
    for (i = 0; i < pos; i++)
    {
        current = current->next;
    }

    *x = current->data;

    return TRUE;
}

int Tree_Clear (Tree* tree)
{
    if (NULL == tree)
    {
        errno = ERROR;
        return FALSE;
    }

    TreeData x;
    return Delete (tree, 0, &x);
}

void Tree_Destroy (Tree* tree)
{
    if (NULL == tree)
    {
        errno = ERROR;
        return;
    }

    Tree_Clear (tree);

    free (tree->head);
    free (tree);
}

TreeNode* Tree_Root (Tree* tree)
{
    if (NULL == tree)
    {
        errno = ERROR;
        return NULL;
    }

    return tree->head->next;
}

int Tree_Count (Tree* tree)
{
    if (NULL == tree)
    {
        errno = ERROR;
        return FALSE;
    }

    return tree->len;
}

// 递归求高度
int r_height (TreeNode* node)
{
    if (NULL == node)
    {
        return 0;
    }

    int subHeight = 0;
    int max       = 0;
    ChildNode* child = node->childList->next;
    while (child)
    {
        subHeight = r_height (child->childNode);
        if (subHeight > max)
        {
            max = subHeight;
        }
        child = child->next;
    }

    return max + 1;
}

int Tree_Height (Tree* tree)
{
    if (NULL == tree)
    {
        errno = ERROR;
        return FALSE;
    }

    int height = r_height (tree->head->next);

    return height;
}

// 递归求度
int r_degree (TreeNode* node)
{
    if (NULL == node)
    {
        return 0;
    }

    int max       = node->degree;
    int subDegree = 0;
    ChildNode* child = node->childList->next;
    while (child)
    {
        subDegree = r_degree (child->childNode);
        if (subDegree > max)
        {
            max = subDegree;
        }
        child = child->next;
    }

    return max;
}

int Tree_Degree (Tree* tree)
{
    if (NULL == tree)
    {
        errno = ERROR;
        return FALSE;
    }

    int degree = r_degree (tree->head->next);

    return degree;
}

void printA (TreeNode* node)
{
    printf ("%c\n", node->data);
}


主函数 main.c

#include <stdio.h>
#include "tree.h"



int main()
{
    Tree* tree = Create_Tree();
    if (NULL == tree)
    {
        myError ("Create_Tree");
        return -1;
    }

    Insert_Tree (tree, 'A', 0);
    Insert_Tree (tree, 'B', 0);
    Insert_Tree (tree, 'C', 0);
    Insert_Tree (tree, 'D', 0);
    Insert_Tree (tree, 'E', 1);
    Insert_Tree (tree, 'F', 1);
    Insert_Tree (tree, 'H', 3);
    Insert_Tree (tree, 'I', 3);
    Insert_Tree (tree, 'J', 3);
    Insert_Tree (tree, 'X', 3);
    Insert_Tree (tree, 'Z', 8);

    Display (tree, printA);

    //printf ("删除B :\n");
    TreeData x;
    //Delete(tree, 1, &x);
    //Display(tree, printA);

    printf ("height = %d\n", Tree_Height(tree));
    printf ("degree = %d\n", Tree_Degree(tree));
    return 0;
}

error.h是我自己写的一个包含常见错误的头文件,这里我就不发了。

2019-06-16 21:42:44 weixin_43930512 阅读数 3361


总结《大话数据结构》和《C++Primer》,文后附《大话数据结构》和《C++Primer》第五版下载链接,本文相关代码均由C++编写。

1.数据结构与算法常见概念:

数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
数据元素:是组成数据的,有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的逻辑结构:数据对象中数据元素之间的相互关系,分为线性结构、树形结构、图形结构以及集合结构。
数据结构的物理结构:数据的逻辑结构在计算机中的存储形式,分为顺序存储和链式存储(不连续存储)。

算法:解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
算法五个基本特性:输入、输出、有穷性、确定性和可行性。
算法时间复杂度O(n):常数阶、线性阶、平方阶、对数阶、立方阶、nlogn阶、指数阶。
耗时排序:O(1)<O(logn)<O(n)<O(nlgn)<O(x2x^{2})<O(x3x^{3})<O(2n2^{n})<O(n!)<O(nnn^{n})

2.数据结构:

2.1线性结构:

基本概念

线性结构:数据元素之间是一对一的关系。
在这里插入图片描述
线性表:零个或多个数据元素的有限序列。
区分数组长度与线性表的长度
        数组长度是指存放线性表的存储空间的长度,存储分配后这个值是不变的。
        线性表的长度是线性表中数据元素的个数,随着线性表的插入与删除,这个值是在变换的。
在这里插入图片描述线性表的顺序存储:用一段连续的存储单元依次存储线性表的数据元素。(通常使用一维数组实现顺序存储结构)
线性表的链式存储:除了存储本身的信息之外,还需存储一个指示后继的信息。
顺序存储的插入步骤:
        a.线性表长度大于等于数组长度,抛出异常
        b.插入位置不合适,抛出异常(判断插入位置与0和最大值的大小)
        c.从最后一个元素开始向前变量,将它们都向后移动一位
        d.将要插入的元素填入指定位置
        e.表长加一
顺序存储的删除步骤:
        a.线性表是否为空
        b.删除位置不合适,抛出异常(判断插入位置与0和最大值的大小)
        c.取出删除元素
        d.从删除元素的位置遍历到最后一个元素位置,将它们前移一位
        e.表长减一
链式存储的插入与删除在链表中介绍
顺序存储和链式存储使用场景:如果频繁使用查找,很少进行插入和删除,易采用顺序存储。如果需要频繁插入和删除,易采用链式存储。

数组

数组及基本操作

字符串

字符串及基本操作

队列

队列及基本操作

栈及基本操作

链表

链表及基本操作

2.2树形结构

基本概念

树形结构:数据元素之间存在一对多的层次关系
在这里插入图片描述
:结点拥有的子树数
叶结点/终端结点:度为0的结点
树的度:树内各结点的度的最大值
在这里插入图片描述
结点间关系图
在这里插入图片描述
树的深度/高度:树中结点的最大层次
在这里插入图片描述
二叉树:是N(N>=0)个结点的有限集合,该集合或为空集(空二叉树),或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
在这里插入图片描述
满二叉树:所有分支结点都存在左子树和右子树,并且所有非叶子节点都在同一层上
在这里插入图片描述
完全二叉树:对一棵具有n个结点的二叉树按层序编号,如果编号i(1<= i <= n)的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同,则这棵二叉树称为完全二叉树
在这里插入图片描述
二叉树的特点

  1. 每个结点最多只有两颗子树
  2. 左右子树是有顺序的
  3. 即使某结点只有一颗子树,也要区分是右子树还是左子树

二叉树的性质

  1. 在二叉树的第i层上至多有2i12^{i-1}个结点(i>=1)
  2. 深度为k的二叉树至多有2k2^{k}-1个结点(k>=1)
  3. 对任何一棵二叉树T,如果其终端结点数为n0n_{0},此二叉树至多有2k2^{k}-1个结点
  4. 具有n个结点的完全二叉树的深度为[log2log_{2}n]+1([x]表示不大于x的最大整数)
  5. n个结点的完全二叉树按层序编号(参考上图),对任意一个结点i有:
    a. 如果i=1,则i是二叉树的根,如果i>1,其双亲是[i/2]
    b. 如果2i>n,则结点i无左孩子
    c. 如果2i+1>n,则结点i无右孩子(否则其右孩子为2i+1)

二叉树的递归遍历

二叉树的遍历(递归)

二叉树的非递归遍历

未完待续……

2.3图形结构

图形结构:数据元素的多对多的关系
在这里插入图片描述

2.4集合结构

集合结构:数据元素除了同属于一个集合外,它们之间没有其他关系。
在这里插入图片描述

3.资源链接

《大话数据结构》+《C++Primer》PDF百度云盘链接
提取码:6a7b

2019-09-18 15:39:41 RHJlife 阅读数 0

本章内容:树的结构定义、递归的三种遍历、非递归的三种遍历、层次遍历、求深度、求特定结点以及测试的主函数。

#include <stdio.h>
#include <stdlib.h>
#define maxsize 50
//二叉树的链式存储
typedef struct BTNode
{
    //树结点存储的类型可以更换,常用int、double、char等
    int data;
    BTNode *lchild;
    BTNode *rchild;
}BTNode,*Tree;
//访问改结点数值
void visit(Tree Q)
{
    printf("%d\n",Q->data);
}
//先序遍历
void preorder(Tree Q)
{
    if(Q!=NULL)
    {
        visit(Q);
        preorder(Q->lchild);
        preorder(Q->rchild);
    }
}
//中序遍历
void midorder(Tree Q)
{
    if(Q!=NULL)
    {
        midorder(Q->lchild);
        visit(Q);
        midorder(Q->rchild);
    }
}
//后序遍历
void postorder(Tree Q)
{
    if(Q!=NULL)
    {
        postorder(Q->lchild);
        postorder(Q->rchild);
        visit(Q);
    }
}
//求高度
int getDepth(Tree Q)
{
    if(Q==NULL)
        return 0;
    else
    {
        int l,r;
        l=getDepth(Q->lchild);
        r=getDepth(Q->rchild);
        return (l>r?l:r)+1;
    }
}
//查找符合key的结点,存放到w中
void search(Tree Q,Tree &w,int key)
{
    if(Q!=NULL)
    {
        if(Q->data==key)
        {
            w=Q;
        }
        else
        {
            search(Q->lchild, w, key);
            //剪枝操作
            if(w!=NULL)
                search(Q->rchild, w, key);
        }
    }
    return;
}
//层次遍历
void level(Tree Q)
{
    int front,rear;
    Tree l[maxsize];
    Tree q;
    front=rear=0;
    if(Q!=NULL)
    {
        //初始先把根结点放入
        rear=(rear+1)%maxsize;
        l[rear]=Q;
        //循环访问
        while(front!=rear)
        {
            front=(front+1)%maxsize;
            q=l[front];
            visit(q);
            if(q->lchild!=NULL)
            {
                rear=(rear+1)%maxsize;
                l[rear]=q->lchild;
            }
            if(q->rchild!=NULL)
            {
                rear=(rear+1)%maxsize;
                l[rear]=q->rchild;
            }
        }
        
    }
}
//非递归设计遍历,先
void Npreorder(Tree Q)
{
    if(Q!=NULL)
    {
        Tree Stack[maxsize];
        int top=-1;
        Tree q;
        Stack[++top]=Q;
        while(top!=-1)
        {
            q=Stack[top--];
            visit(q);
            if(q->rchild!=NULL)
               Stack[++top]=q->rchild;
            if(q->lchild!=NULL)
                Stack[++top]=q->lchild;
        }
    }
}
//非递归设计遍历,中
void Nmidorder(Tree Q)
{
    if(Q!=NULL)
    {
        Tree q;
        Tree Stack[maxsize];
        int top=-1;
        q=Q;
        while(top!=-1||q!=NULL)
        {
            //左孩子存在,则存此刻结点再往下找做孩子
            while(q!=NULL)
            {
                Stack[++top]=q;
                q=q->lchild;
            }
            if(top!=-1)
            {
                q=Stack[top--];
                visit(q);
                q=q->rchild;
            }
        }
    }
}
//非递归设计遍历,后
void Npostorder(Tree Q)
{
    if(Q!=NULL)
    {
        Tree Stack1[maxsize];
        int top1=-1;
        Tree Stack2[maxsize];
        int top2=-1;
        Tree q=NULL;
        Stack1[++top1]=Q;
        //将所有结点都放进来
        while(top1!=-1)
        {
            q=Stack1[top1--];
            Stack2[++top2]=q;
            if(q->lchild!=NULL)
                Stack1[++top1]=q->lchild;
            if(q->rchild!=NULL)
                Stack1[++top1]=q->rchild;
        }
        //输出结点
        while (top2!=-1)
        {
            q=Stack2[top2--];
            visit(q);
        }
        
    }
}
int main()
{
    //随便写一个树
    Tree head,A,B,C,D,E;
    head=(Tree)malloc(sizeof(BTNode));
    A=(Tree)malloc(sizeof(BTNode));
    B=(Tree)malloc(sizeof(BTNode));
    C=(Tree)malloc(sizeof(BTNode));
    D=(Tree)malloc(sizeof(BTNode));
    E=(Tree)malloc(sizeof(BTNode));
    head->data=0;
    A->data=1;
    B->data=2;
    C->data=3;
    D->data=4;
    E->data=5;
    head->lchild=A;
    head->rchild=B;
    A->lchild=C;
    A->rchild=D;
    B->lchild=E;
    B->rchild=NULL;
    C->lchild=D->lchild=E->lchild=C->rchild=D->rchild=E->rchild=NULL;
    //三种遍历
    //preorder(head);
    //midorder(head);
    //postorder(head);
    //获得深度
    //printf("%d",getDepth(head));
    //层次遍历
    //level(head);
    //三种非递归遍历
    //Npreorder(head);
    //Nmidorder(head);
    //Npostorder(head);
    return 0;
}

 

数据结构之树

阅读数 15739