二叉树(binary tree)
二叉树的定义
二叉树的定义:树的度为2的树。
二叉树的递归定义:二叉树或者是一棵空树,或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树,而左右子树又都是一棵二叉树。
二叉树的性质
1.第i层上至多有2的i-1次方个结点。
2.深度为h的二叉树至多有2的h次方减1个结点。
3.每一层都满的二叉树称为满二叉树,只在最后一层右边缺若干个结点的树称为完全二叉树。
(对结点的编号通常都是从满二叉树的树根开始,从上到下从左到右编号)。
完全二叉树的重要性质:
根结点序号为i=1的情况下:
1.编号为i的结点,左孩子编号为2i,右孩子编号为2i+1.
2.除根结点外,编号为i的结点,其父结点的标号为i/2向下取整。
二叉树的存储结构
同线性表一样,二叉树有顺序和链接两种存储结构。
1.顺序存储结构
顺序存储一棵二叉树,首先对该树中每个结点进行编号,然后以各个结点的编号为下标,把各结点的值对应存储到一个一维数组中。
每个结点的编号与等深度的满二叉树中对应的结点编号相同,即树根编号为1,然后从上到下从左到右编号,i结点的左右孩子为2i和2i+1.
缺点:对于单支结点较多的二叉树来说很多存储位置空闲。
2.链接存储结构
链接存储中通常采用的方法是,在每个结点中设置三个域:值域(用来存储对应的数据元素),左指针域和右指针域。
另一种方法是,在如上的结构中再增加一个parent指针域(便于查找父结点)。
不带双亲指针的链接存储结构称作二叉链表,既可以由独立分配的结点链接而成,也可以由数组中的元素结点链接而成。
独立结点的类型可以这样定义:
struct BTreeNode{ ElemType data; BTreeNode* left; BTreeNode* right; };
数组元素结点可以定义为
struct ABTreeNode{ ElemType data; int left,right; };
第二种形式中left和right域分别存储左右孩子结点所在单元的下标,所以被定义为整型。
在数组中建立二叉树的好处是,建立好后可以把整个数组写入到文件中保存起来,需要时再从文件中读入到数组中。
二叉树遍历
设二叉树由BTreeNode类型的、通过动态分配产生的独立结点链接而成,并设BT为指向根结点的指针。
前序遍历
void PreOrder(BTreeNode* BT) { if(BT != NULL) { cout<<BT->data<<' '; //访问根结点,操作视应用而定 PreOrder(BT->left); PreOrder(BT->right); } }
中序遍历
void InOrder(BTreeNode* BT) { if(BT != NULL) { InOrder (BT->left); cout<<BT->data<<' '; InOrder (BT->right); } }
后序遍历
void PostOrder(BTreeNode* BT) { if(BT != NULL) { PostOrder (BT->left); PostOrder (BT->right); cout<<BT->data<<' '; } }
按层遍历
可以按照二叉树的层次结构进行遍历,即按照从上到下从左到右的次序访问各个结点。
按层遍历算法需要使用一个队列,开始时把整个树的根结点入队,然后每从队列中删除一个结点并输出该结点的值时,都把它的非空的左右孩子结点入队,这样当队列空时算法结束。
//按层遍历 void LevelOrder(BTreeNode* BT) { const int MaxSize = 30; //定义用于存储队列的数组长度 //在这个算法中,队列的最大长度不会超过二叉树中一层上的最大结点数 BTreeNode* q[MaxSize]; //定义队列所使用的数组空间 int front=0, rear=0; //定义队首指针和队尾指针,初始为空队 BTreeNode* p; if(BT != NULL) //将树根指针进队 { rear = (rear +1) % MaxSize; q[rear] = BT; } while(front!=rear) //当队列非空时执行循环 { front=(front + 1) % MaxSize; //使队首指针指向队首元素 p = q[front]; //操作并删除队首元素 cout<<p->data<<' '; if(p->left !=NULL) //若存在左孩子,则该结点指针进队 { rear = (rear +1) % MaxSize; q[rear] = p->left; } if(p->right !=NULL) //若存在右孩子,则该结点指针进队 { rear = (rear +1) % MaxSize; q[rear] = p->right; } }//while end }
相关推荐
二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历二叉树遍历...
二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法二叉树遍历算法
遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
二叉树遍历 二叉树遍历
数据结构课程设计--二叉树遍历及其应用、对树的先序遍历、后序遍历、中序遍历、层序遍历、二叉树的深度及其叶子树、并打印树形。
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
层次遍历二叉树
易语言二叉树遍历源码,二叉树遍历,二叉树_取下级树,内存_读整数内存,读整数内存_
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;...ABCDEFG【选做内容】采用非递归算法实现二叉树遍历。
二叉树遍历的特点
算法面试通关40讲完整课件 21 二叉树遍历 算法面试通关40讲完整课件 21 二叉树遍历 算法面试通关40讲完整课件 21 二叉树遍历 算法面试通关40讲完整课件 21 二叉树遍历 算法面试通关40讲完整课件 21 二叉树遍历 算法...
实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...
遍历二叉树程序,亲自调试,注释详尽,有不懂的随时和大家交流,希望能帮到大家~
包括了二叉树的各种递归与非递归的遍历算法 还可对二叉树所有结点求和
二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的...
java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...
数据结构树和二叉树遍历二叉树和线索二叉树PPT学习教案.pptx
设计二叉树的双序遍历设计二叉树的双序遍历设计二叉树的双序遍历设计二叉树的双序遍历设计二叉树的双序遍历设计二叉树的双序遍历设计二叉树的双序遍历设计二叉树的双序遍历设计二叉树的双序遍历设计二叉树的双序遍历...
(1)以二叉链为存储结构,建立二叉树 (2)用递归算法和非递归算法实现二叉树的中序遍历 (3)二叉树中序遍历的演示