做网站出现的常见问题,网站软文标题,wordpress 主题 教程,aso平台#x1f31e; “少年没有乌托邦#xff0c;心向远方自明朗#xff01;” 二叉树 #x1f388;1.二叉树的遍历#x1f52d;1.1先序遍历#x1f52d;1.2中序遍历#x1f52d;1.3后序遍历#x1f52d;1.4层次遍历#x1f52d;1.5二叉树遍历的递归算法#x1f4dd;1.5.1先… “少年没有乌托邦心向远方自明朗” 二叉树 1.二叉树的遍历1.1先序遍历1.2中序遍历1.3后序遍历1.4层次遍历1.5二叉树遍历的递归算法1.5.1先序遍历1.5.2中序遍历1.5.3后序遍历1.5.4例题一1.5.5例题二1.5.6例题三 1.6二叉树遍历的非递归算法1.7例题四 1.二叉树的遍历 二叉树的遍历是按照一定次序访问二叉树中的所有结点且每个结点仅被访问一次的过程。遍历线性结构是容易解决的而二叉树的结构是非线性结构需要寻找规律使二叉树的结点排列在一个线性队列上便于遍历。 由二叉树的递归定义知二叉树有根结点、左子树和右子树3个基本单元组成。如果以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树则遍历整个二叉树有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右则只有DLR、LDR、LRD三种遍历方案分别称为先序遍历、中序遍历和后序遍历。 1.1先序遍历
先序遍历二叉树的过程如下
访问根结点先序遍历左子树先序遍历右子树
✅ 如下图所示二叉树的先序序列为ABJDGCEHF
1.2中序遍历
中序遍历二叉树的过程如下
中序遍历左子树访问根结点中序遍历右子树
✅ 如下图所示二叉树的中序序列为JBGDAEHCF
1.3后序遍历
后序遍历二叉树的过程如下
后序遍历左子树后序遍历右子树访问根结点
✅ 如下图所示二叉树的后序序列为JGDBHEFCA
1.4层次遍历
二叉树非空设二叉树的高度为h时层次遍历二叉树的过程如下
先访问根结点第1层再从左向右访问每层结点
✅ 如下图所示二叉树的层次序列为ABCJDEFGH
1.5二叉树遍历的递归算法
1.5.1先序遍历
void BiTree::InTraverse(BitNode* t)
{//中序遍历递归函数if (t){cout data;InTraverse(t-lchild);InTraverse(t-rchild);}
}
void BiTree::InTraverseBiTree()
{BitNode* p bt;InTraverse(p);
}1.5.2中序遍历
void BiTree::InTraverse(BitNode* t)
{//中序遍历递归函数if (t){InTraverse(t-lchild);cout data;InTraverse(t-rchild);}
}
void BiTree::InTraverseBiTree()
{BitNode* p bt;InTraverse(p);
}1.5.3后序遍历
void BiTree::InTraverse(BitNode* t)
{//中序遍历递归函数if (t){InTraverse(t-lchild);InTraverse(t-rchild);cout data;}
}
void BiTree::InTraverseBiTree()
{BitNode* p bt;InTraverse(p);
}1.5.4例题一 已知二叉树采用二叉链表存储结构存储设计一个交换二叉树左右子树的递归算法。 void ChangeSubTree(BitNode* t)
{BitNode* temp;if (t){temp new BitNode;temp t-lchild;t-lchild t-rchild;t-rchild temp;ChangeSubTree(t-lchild);ChangeSubTree(t-rchild);}
}1.5.5例题二 已知二叉树采用二叉链表结构存储请设计一个判断两棵二叉树是否相似的算法。若相似返回1否则返回0.所谓两棵二叉树s和t相似是指s和t均为空的二叉树或者s和t的根结点相似值可以不同且左右子树分别相似。 int Alike(BitNode* s, BitTree* t)
{if (s NULL t NULL)return 1;else if (s NULL || t NULL)return 0;elsereturn Alike(s-lchild, t-lchild) Alike(s-rchild, t-rchild);
}1.5.6例题三 已知二叉树采用二叉链表存储结构存储设计一个将二叉树s拷贝给t的递归算法。 void CopyBitree(BitNode* s, BitNode* t)
{if (s NULL)t NULL;else{t new BitNode;t-data s-data;CopyBiTree(s-lchild, t-lchild);CopyBiTree(s-rchild, t-rchild);}
}1.6二叉树遍历的非递归算法 为了把递归过程改成一个非递归过程需要利用一个工作栈记录遍历时的回退路径。 先序遍历的算法流程
用指针p指向当前需要处理的结点访问该结点该结点入栈并将p指向左孩子循环处理左子树当该结点无左孩子时表示栈顶结点无左子树栈顶结点退栈并将p指向刚出栈结点的右孩子对右子树进行相同处理重复上述过程直到栈为空为止
void PreTraverse(BitNode* t)
{BitNode* p t;SqStack s;while (p || !s.EmptyStack()){if (p){//访问根结点根结点指针入栈遍历左子树cout p-data;//访问结点s.Push(p);p p-lchild;}else{//根结点退栈遍历右子树s.Pop(p);p p-rchild;}}
}中序遍历的算法流程
用指针p指向当前需要处理的结点p入栈扫描该结点的左子树上的所有结点并将它们一一进栈当该结点无左孩子时表示栈顶结点无左子树栈顶结点退栈该问该结点并将p指向刚出栈结点的右孩子对右子树进行相同处理重复上述过程直到栈为空为止
void PreTraverse(BitNode* t)
{BitNode* p t;SqStack s;while (p || !s.EmptyStack()){if (p){//根结点入栈遍历左子树s.Push(p);p p-lchild;}else{//根结点退栈访问结点遍历右子树s.Pop(p);cout p-data;//访问结点p p-rchild;}}
}后序遍历的算法流程
用指针p指向当前需要处理的结点并置标志位flag0表示第一次入栈p入栈扫描该结点的左子树上的所有结点并将它们一一进栈当该结点无左孩子时表示栈顶结点无左子树栈顶结点退栈并判断标志位的值若flag0置flag1表示该结点第二次入栈该问该结点并将p指向刚出栈结点的右孩子若flag1,则访问该结点置p NULL.对右子树进行相同处理重复上述过程直到栈为空为止
typedef struct
{BitNode* pointer;int flag;
}BitNodeFlag;
void PostTraverse(BitNode* t)
{BitNodeFlag bf;BitNode* p t;SqStack s;while (p || !s.EmptyStack()){if (p){bf.pointer p;bf.flag 0;s.Push(bf);p p-lchild;}else{s.Pop(bf);if (bf.flag 0){bf.uflag 1;s.Push(bf);p p-rchild;}else{cout bf.pointer-data;p NULL;}}}
}层次遍历的算法流程 层次遍历访问完某一层的结点后再按照它们的访问次序对各结点的左、右子树顺序访问。如此一层一层地访问先访问的结点其左、右孩子也要先访问。层次遍历过程可以用队列来实现。 void LevelTraverse(BitNode* t)
{BitNode* p t;LinkQueue q;//初始化建立空队列if (p)q.Enqueue(p);//根结点入队while (!q.EmptyQueue()){q.DeQueue(p);//出队cout p-data;//访问结点if (p-lchild)q.EnQueue(p-lchild);//左子树根结点入队if (p-rchild)q.EnQueue(p-rchild);//右子树根结点入队}
}1.7例题四 已知二叉树采用二叉链表存储结构存储设计一个计算二叉树叶子结点的非递归算法。 int CountBitLeaf(BitNode* t)
{SqStack s;BitNode* p t;int count 0;while (p ! NULL || !s.EmptyStack()){while (p ! NULL){s.Push(p);p p-lchild;}if (!s.EmptyStack()){s.Pop(p);if (p-lchild NULL p-rchild NULL)countp p-rchild;}}return count;
}好啦关于二叉树的遍历的知识到这里就先结束啦后期会继续更新学习数据结构与算法的相关知识欢迎大家持续关注、点赞和评论❤️❤️❤️
