网站开发建,html展示网站源代码,营销网站建设专业服务公司,网站做产品的审核工作目录#xff1a;
二叉树的基本操作 1. 二叉树的创建 1.1. 顺序存储 2. 二叉树的初始化3. 二叉树插入节点4. 二叉树的遍历 4.1. 递归遍历4.2. 层序遍历4.3. 非递归遍历
二叉树的基本操作
1. 二叉树的创建
二叉树的存储方式哦同样有两种#xff0c;一种是顺序存储#x…目录
二叉树的基本操作 1. 二叉树的创建 1.1. 顺序存储 2. 二叉树的初始化3. 二叉树插入节点4. 二叉树的遍历 4.1. 递归遍历4.2. 层序遍历4.3. 非递归遍历
二叉树的基本操作
1. 二叉树的创建
二叉树的存储方式哦同样有两种一种是顺序存储一种是链式存储。 1.1. 顺序存储
#define MAXSIZE 100
struct TreeNode{int data;bool isEmpty;
}
TreeNode t[MAXSIZE];
·
与其他数据结构类似树的结构同样是先来一个结点再来一个树的整体。
在树的结构体中data表示数据域用来存放树的节点的数据isEmpty表示树的这个节点是否为空。对树的节点声明以后再创建一个以节点类型为数组元素类型的数组这样树的结构就定义好了。但由于顺序二叉树对于空间的浪费和查询的困难顺序二叉树只适合于完全二叉树所以我们一般使用链式二叉树。### 链式存储一个典型的存储结构如下c
typedef struct BTNode{int data;struct node *lchild;struct node *rchild;
}BTNode,*BTree;该结构采用的是二叉树的左右链表示即一个结构体中有三部分一部分是二叉树节点本事的数据其他两部分是指向二叉树下一个节点的指针一个指向左子树一个指向右子树。 其中data为数据域left和right为指针域分别指向左孩子和右孩子。
2. 二叉树的初始化
二叉树的初始化只需要创建一个二叉树并让他等于NULL即可。
void InitBTree(BTree *root)
{*rootNULL;
}如果我们要对根节点进行初始化的话可以采取以下的方式
(*root)(BTree)malloc(sizeof(BTNode));
(*root)-lchildNULL;
(*root)-rchild-NULL;
(*root)-data2;3. 二叉树插入节点
如果需要对一个二叉树插入一个节点我们只需要申请内存然后赋值即可。
BTNode *p(BTNode *)malloc(sizeof(BTNode));
p-data2;
p-lchildNULL;
p-rchildNULL;
root-lchildp;4. 二叉树的遍历
二叉树的遍历有四种基本的方式分别为先序遍历中序遍历后序遍历和层次遍历。其中每一种方式又有两种方式分别为递归和非递归。
4.1. 递归遍历
递归遍历的方式比较简单只需要按照先序遍历的顺序依次递归遍历二叉树即可并且不同遍历方式的代码相似。
void firstTree(BTree BT)//先序遍历递归
{if(BT!NULL){printf(%c,BT-data);displayTree(BT-left);displayTree(BT-right);}elseprintf(#);
}
void middleTree(BTree BT)//中序遍历递归
{if(BT!NULL){displayTree(BT-left);printf(%c,BT-data);displayTree(BT-right);}elseprintf(#);
}
void lastTree(BTree BT)//后序遍历递归
{if(BT!NULL){displayTree(BT-left);displayTree(BT-right);printf(%c,BT-data);}elseprintf(#);
}4.2. 层序遍历
层序遍历的基本原理是借助队列的形式当一个节点被读入以后我们先将其压入队列末尾。接下来如果队列元素不空的话我们就将队头的节点弹出然后访问其值并且将其左右子树压入队列末尾。以此类推循环往复就达到了层序遍历的目的。 具体代码实现如下
void levelOrder(BTree BT)
{LinkQuene Q;InitQuene(Q);BTree p;EnQuene(Q,BT);while(!isEmpty(Q)){DeQueneu(Q,p);visit(p);if(p-lchild!NULL)EnQuene(Q,p-lchild);if(p-rchild!NULL)EnQuene(Q,p-rchild);}
}4.3. 非递归遍历
非递归遍历需要通过栈的操作来进行 示例代码如下
//前序遍历
void firstTree(BTNode* root)
{if (root NULL)return;BTNode* p root;stackBTNode* s; //创造一个栈用来存放树节点while (!s.empty() || p!NULL){//如果p不为空的话酒将p压入栈中然后让p指向左子树while (p!NULL){printf(%c,p-data);s.push(p);p p-lchild;}//当p为空时说明根和左子树都遍历完了该进入右子树了if (!s.empty()){p s.top();s.pop();p p-rchild;}}
}//中序遍历
void middleTree(BTNode* root)
{if (root NULL)return;BTNode* p root;stackBTNode* s; //创造一个栈用来存放树节点while (!s.empty() || p!NULL){//如果p不为空的话酒将p压入栈中然后让p指向左子树while (p!NULL){s.push(p);p p-lchild;}//当p为空时说明根和左子树都遍历完了该进入右子树了if (!s.empty()){p s.top();s.pop();printf(%c,p-data);p p-rchild;}}
}其中前序遍历和中序遍历的方式较为相似只需要先建立一个栈然后将访问到的节点存入栈中节点一直向左指向直到节点为空。 当节点为空时让指针指向栈顶元素并弹出然后开始右子树的访问。 前序遍历和中序遍历的区别仅仅在于打印数据的时间不同。
而后序遍历则更加复杂一点
//后序遍历
void PostOrderWithoutRecursion(BTNode* root)
{if (root NULL)return;stackBTNode* s;BTNode *proot;//p用来表示当前访问的节点BTNode *qNULL;//q用来表示上一个访问的节点//先把p移动到左子树最下边while (p!NULL){s.push(P);p p-lchild;}while (!s.empty()){//此时让p已经为空了先从栈中提取一个元素赋给pp s.top();//现在p的值就是最左下角的节点s.pop();if (p-rchild NULL || p-rchild q) //如果右子树为空或者刚访问过右子树{printf(%c,p-data);q p;//每次输出值以后修改上一次访问的节点}else if(p-lchildq)//如果左子树已经访问过了{s.push(p);//让根结点入栈p p-rchild; //进入右子树while (p!NULL){s.push(p);p p-lchild;}}}
}后序遍历需要两个指针其中一个指针指向的是当前访问的元素另一个指针指向的是上次访问过的元素。 这样是为了保证左右子树都访问过了以后在访问根节点当我们访问过左子树以后弹出根节点然后需要判断右子树是否访问过或者右子树是否为空如果是的话就访问根节点否则就将右子树的根节点压入栈中然后再访问右子树的根节点的左子树直到右子树为空或者右子树被访问过就返回去访问根节点弹栈。
