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

节点的度:某节点的度定义为该节点孩子节点的个数。 叶子节点:度为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 100

typedefchardataType;

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
到底啦