重拾数据结构--二叉树基础以及常用操作

节点的度:某节点的度定义为该节点孩子节点的个数。 叶子节点:度为0 的结点称为叶结点,或者称为终端结点。 树的度:树
  • 节点的度:某节点的度定义为该节点孩子节点的个数。
  • 叶子节点:度为0 的结点称为叶结点,或者称为终端结点。
  • 树的度:树中各结点度的最大值。
  • 节点的高度:从该节点起到叶子节点的最长简单路径的边数。(简单路径:无重复边的路径)
  • 树的高度:根节点的高度。
  • 节点的层数:规定树的根结点的层数为1,其余结点的层数等于它的双亲结点的层数加1。
  • 节点的深度:即该节点的层数。
  • 树的层数:树中所有节点的最大层数。
  • 树的深度:树中所有结点的最大层数。
  • 外节点:叶子节点。
  • 内节点:除叶子节点之外的节点。
  • 满二叉树:所有终端都在同一层次,且非终端结点的度数为2。在满二叉树中若其深度为k,则其所包含的结点数必为2^k-1。
  • 完全二叉树:除最后一层,每一层的节点数都达到最大。最后一层若是没满,则节点集中在左边,空的只能是右边。对于完全二叉树,设一个结点为i则其父节点为i/2,2i为左子节点,2i+1为右子节点。
  • 扩充二叉树:对二叉树中度为1的节点和叶子节点添加空节点,使之成为满二叉树。
    二叉树的每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒。

与树不同,树的节点个数至少为1,而二叉树的节点个数可以为0;树中节点的最大度数没有限制,而二叉树节点的最大度数为2;树的节点无左、右之分,而二叉树的节点有左、右之分。

注:关于树深度、层数、高度的定义会有不同的说法:有从0开始计数的,也有从1开始计数的。从哪儿开始计数不是关键,关键在于一致性,量的写法要一致。

存储方式

顺序存储表示

二叉树可以用数组或链接串列来存储,而且如果这是满二叉树,这种方法不会浪费空间。用这种紧凑排列,如果一个节点的索引为i,它的子节点能在索引2i+1和2i+2找到,并且它的父节点(如果有)能在索引floor((i-1)/2)找到(假设根节点的索引为0)。这种方法更有利于紧凑存储和更好的访问的局部性,特别是在[前序遍历]中。然而,它需要连续的存储空间,这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1,而实际却只有h个结点,空间的浪费太大,这是顺序存储结构的一大缺点。

重拾数据结构--二叉树基础以及常用操作

#defineMAX_TREE_SIZE 100/* 二叉树的最大节点数 */typedefTElemType SqBiTree[MAX_TREE_SIZE];/* 顺序存储的数组 */typedefstruct {intlevel,order;/* 节点所在层以及在该层的序号 */ }position;

二叉链表存储表示

在使用记录或内存地址指针的程序设计语言中,二叉树通常用树结点结构来存储。有时也包含指向唯一的父节点的指针。如果一个结点的子结点个数小于2,一些子结点指针可能为空值,或者为特殊的哨兵结点。 使用链表能避免顺序存储浪费空间的问题,算法和结构相对简单,但使用二叉链表,由于缺乏父链的指引,在找回父节点时需要重新扫描树得知父节点的节点地址。

/* 二叉树的二叉链表存储表示 */typedefstructBiTNode { TElemType data;structBiTNode *lchild,*rchild;/* 左右孩子指針 */ }BiTNode,*BiTree;

三叉链表存储表示

改进于二叉链表,增加父节点的指引,能更好地实现节点间的访问,不过算法相对复杂。 当二叉树用三叉链表表示时,有N个结点,就会有N+2个空指针。

/* 二叉树的三叉链表存储表示 */typedefstructBiTPNode { TElemType data;structBiTPNode *parent,*lchild,*rchild;/* 父、左右孩子指針 */ }BiTPNode,*BiPTree;

创建二叉树

本文使用二叉树的二叉链表存储表示:

#defineSIZE 100typedefchardataType;structtreeNode{ dataType val;structtreeNode * leftChild;structtreeNode * rightChild;intvisit =0;//后序遍历时使用};typedefstructtreeNode * treeNodeP;

创建如下这样一颗二叉树:

重拾数据结构--二叉树基础以及常用操作

括号表示法创建

对应的括号表示法为: A(B(D(H),E(I,J)),C(F,G)) ,括号表示法中,对应 () 中的内容为 ( 前节点的孩子, () 中的 , 用于分隔左右孩子。

voidcreate(treeNodeP &root,char* str){ root = NULL;structtreeStackstack; (&stack)->top =-1;intpos =0;//字符串遍历时的当前位置charch = str[pos]; treeNodeP node = NULL;inttype=0;while(ch !='/0'){switch(ch) {case'('://遇到'('时,表示下一个节点是上一个节点的左孩子。 push(&stack, node);//此时node保存着上一个节点,将上一个节点入栈。 ch = str[++pos];//遍历下一个字符 type = 1;//表示下一个元素是左孩子break;case',': type = 2;//表示下一个孩子是右孩子 ch = str[++pos];//遍历下一个字符break;case')'://遇到`)`时,表示栈顶元素的孩子输入完毕了,可以将栈顶节点出栈了。 pop(&stack);//栈顶节点出栈 ch = str[++pos];//遍历下一个字符break;default://表示遇到的是节点的内容值 node = newtreeNode();//新建节点并初始化 node->val = ch; node->leftChild = NULL; node->rightChild = NULL;if(root ==NULL){//如果root节点为NULL,则当前输入的节点为根节点 root = node; }elseif((&stack)->top >-1){//栈不为空 treeNodeP t = top(&stack);//获取栈顶节点(不弹出)if(type ==1){ t->leftChild = node; }elseif(type ==2){ t->rightChild = node; } } ch = str[++pos];break; } }}

按前序遍历输入

表示为: ABDH###EI##J##CF##G## ,此表示法按照 前序遍历 的顺序输入, # 表示 NULL

核心思想:如果字符连续的出现,则下一个字符为上一个字符的左孩子,在 # 出现之前,所有的字符按照顺序都入栈。如果字符在 # 后第一次出现,则必为栈顶节点的右节点。当出现第一个 # 时,说明上一个字符为当前分支的最左节点,上一个字符的左孩子赋值NULL。连续出现第二个 # 时,说第一个 # 前的字符的右孩子也赋值NULL。当一个节点的右孩子赋值完成时,便可以从栈中弹出了。如果连续出现2个以上的 # ,则栈顶的节点的右孩子依次置NULL,并弹出。

voidcreateByPreorder(treeNodeP &root,char* str){ root = NULL;intpos =0;charch = str[pos]; treeNodeP node = NULL;structtreeStackstack; (&stack)->top =-1;intcount =0;//记录`#`连续出现的记录while(ch !='/0'){if(ch !='#'){ count = 0;//一旦`#`终止连续出现,count赋0 node = newtreeNode();//新建节点并初始化 node->val = ch; node->leftChild = NULL; node->rightChild = NULL;if(root ==NULL){//如果root节点为NULL,则当前输入的节点为根节 root = node; }if((&stack)->top >-1){//栈不为空//遇见一个字符,既然栈中存在节点,则不为左节点便为右节点if(top(&stack)->leftChild){ pop(&stack)->rightChild = node;//如果是右节点,则赋值完整后便可以将节点弹出栈 }else{ top(&stack)->leftChild = node; } } push(&stack, node);//节点入栈 }else{ count++;if((&stack)->top >-1){if(count ==1){//`#`第一次出现时,必然是栈顶节点的左孩子 top(&stack)->leftChild =NULL; }if(count ==2){//`#`第二次连续出现时,必然是栈顶节点的右孩子 pop(&stack)->rightChild =NULL;//此时栈顶节点已完成左右孩子的赋值,可以弹出。 }if(count >2){//将栈中的元素弹出并将右孩子置NULL pop(&stack)->rightChild =NULL; } } } ch = str[++pos];//遍历下一个字符 }}

非递归的前序遍历

voidpreorder(treeNodeP root){if(!root){printf("the tree is empty!"); }structtreeStackstack; (&stack)->top =-1; treeNodeP tmp = root;//只有栈空(所有节点的右孩子都已开始访问或已访问完成)或者//节点为NULL(栈空时,当访问到最右孩子时tmp为NULL)遍历才算完成while(tmp || (&stack)->top >-1) {while(tmp){//此循环的目的是遍历到当前分支的最左节点,将遍历的节点依次输出并入栈。printf("%c",tmp->val); push(&stack, tmp);//栈中的所有节点的右孩子都没有开始访问 tmp = tmp->leftChild; }//上面的循环结束表示当前分支的所有左孩子都入栈了,此时弹出最后一个左孩子节点。 tmp = pop(&stack); tmp = tmp->rightChild;//这里考虑的逻辑就是右孩子是否为NULL,//若为NULL,则弹出栈顶节点,弹出节点为此节点的父节点,此节点后的内容遍历完成,开始父节点的右孩子的前序遍历。//若不为NULL,开始上面的循环,遍历到此节点右孩子分支的最左节点。 }}

输出结果为: ABDHEIJCFG

非递归的中序遍历

voidmidorder(treeNodeP root){if(!root){printf("the tree is empty!"); }structtreeStackstack; (&stack)->top =-1; treeNodeP tmp = root;while(tmp || (&stack)->top >-1) {while(tmp){ push(&stack, tmp); tmp = tmp->leftChild; }//来到当前分支的最左,弹出最左节点,输出。 tmp = pop(&stack);printf("%c",tmp->val); tmp = tmp->rightChild;//这里考虑的逻辑就是右孩子是否为NULL,//若为NULL,则弹出栈顶节点,弹出节点为此节点的父节点,并输出,此节点后的内容遍历完成,开始父节点的右孩子的遍历。//若不为NULL,则再次上面的循环,开始当前节点右孩子的遍历。 }}

与前序遍历唯一的不同就是输出字符的位置变了。前序遍历先是父节点,而中序遍历则是左孩子先。两个输出位置可以细细体味一下。

输出结果为: HDBIEJAFCG

非递归的后序遍历

考虑到后序遍历时父节点需要被回溯2次,所以用一个int型的visit变量加以区分,初始值为0。

voidpostorder(treeNodeP root){if(!root){printf("the tree is empty!"); }structtreeStackstack; (&stack)->top =-1; treeNodeP tmp = root;while(tmp || (&stack)->top >-1) {while(tmp){if(tmp->visit ==1){//入栈次数为1,表示还未访问过右孩子,需要先访问右孩子,此节点入栈,入栈次数+1,同时切换到右孩子分支。 push(&stack, tmp); tmp->visit++; tmp = tmp->rightChild;gotoright; }elseif(tmp->visit ==2){//入栈次数为2,表示右孩子以访问完成,可以输出。输出完毕后从栈中取下一个访问节点,也就是此节点的父节点,开始内循环。printf("%c",tmp->val); tmp = pop(&stack);gotoright; } push(&stack, tmp); tmp->visit = 1;//第一次入栈 tmp = tmp->leftChild; } tmp = pop(&stack);if(tmp->rightChild){//如果最左节点有右孩子,因为后序遍历时右孩子前于父节点,所以右孩子入栈。 push(&stack, tmp);//此节点需再次入栈 tmp->visit++;//入栈次数+1 tmp = tmp->rightChild;//切换到右孩子continue;//继续内循环,遍历到右孩子的最左节点 }//节点无右孩子,则可以输出。printf("%c",tmp->val); tmp = pop(&stack); right:; }}

因为visit一开始都为0,所以内循环中直接遍历到最左节点,并将节点依次入栈。

输出结果为: HDIJEBFGCA

层次遍历

层次遍历的思想即使将当前节点的孩子依次从左到右入队列,此节点访问后便从队列中取下一个节点。重复以上过程。

voidlevelTraverse(treeNodeP root){if(!root){printf("the tree is empty!"); }structtreeQueuequeue; (&queue)->front =-1; (&queue)->rear =-1; treeNodeP tmp = root;while(tmp){printf("%c",tmp->val);if(tmp->leftChild){ enterNode(&queue, tmp->leftChild); }if(tmp->rightChild){ enterNode(&queue, tmp->rightChild); } tmp = getNode(&queue); }}

输出结果为: ABCDEFGHIJ

查找节点

treeNodeP findNode(treeNodeP root,charch){if(!root){returnNULL; }if(root->val == ch){returnroot; }else{ treeNodeP node = findNode(root->leftChild, ch);if(node){returnnode; }else{ node = findNode(root->rightChild, ch);if(node){returnnode; } } }returnNULL;}

求高度

intgetHigh(treeNodeP root){if(!root){return0; }inth1 = getHigh(root->leftChild);inth2 = getHigh(root->rightChild);returnh1 > h2 ? h1 +1: h2 +1;}

所使用的栈、队列数据结构

structtreeStack{ treeNodeP node[SIZE];inttop;};typedefstructtreeStack * treeStackP;voidpush(treeStackPstack, treeNodeP node){if(stack->top < SIZE -1){stack->node[++stack->top] = node; }else{printf("the stack is full!/n"); }}treeNodeP pop(treeStackPstack){if(stack->top >-1){returnstack->node[stack->top--]; }else{returnNULL; }}treeNodeP top(treeStackPstack){if(stack->top >-1){returnstack->node[stack->top]; }else{returnNULL; }}structtreeQueue { treeNodeP node[SIZE];intfront;intrear;};typedefstructtreeQueue * treeQueueP;treeNodeP getNode(treeQueuePqueue){if(queue->front ==queue->rear){returnNULL; }queue->front = (queue->front +1) % SIZE;returnqueue->node[queue->front];}voidenterNode(treeQueuePqueue, treeNodeP node){if((queue->rear +1) % SIZE ==queue->front){printf("the queue is full!"); }queue->rear = (queue->rear +1)% SIZE;queue->node[queue->rear] = node;}
未登录用户
全部评论0
到底啦