为了方便程序验证，首先构造一个如图所示的二叉树。
源码：
/*************************** bintree.h文件 *****************************/
#ifndef _BINTREE_H
#define _BINTREE_H
template <class T>
class CBintree
{
public:
CBintree()
bool Depth_RF()//先根深度遍历
bool Depth_RM()//中根深度遍历
bool WidthFS()//层次遍历
protected:
private:
struct TreeNode
{
T va
TreeNode *plchild
TreeNode *prchild
}
TreeNode *m_pBintree
}
#endif
template <class T>
CBintree<T>::CBintree()
{
m_pBintree = new TreeNode
TreeNode *pNode2 = new TreeNode
TreeNode *pNode3 = new TreeNode
TreeNode *pNode4 = new TreeNode
TreeNode *pNode5 = new TreeNode
TreeNode *pNode6 = new TreeNode
TreeNode *pNode7 = new TreeNode
m_pBintree->va = (T)1
m_pBintree->plchild = pNode2
m_pBintree->prchild = pNode3
pNode2->va = (T)2
pNode2->plchild = pNode4
pNode2->prchild = pNode5
pNode3->va = (T)3
pNode3->plchild = NULL
pNode3->prchild = pNode6
pNode4->va = (T)4
pNode4->plchild = NULL
pNode4->prchild = NULL
pNode5->va = (T)5
pNode5->plchild = pNode7
pNode5->prchild = NULL
pNode6->va = (T)6
pNode6->plchild = NULL
pNode6->prchild = NULL
pNode7->va = (T)7
pNode7->plchild = NULL
pNode7->prchild = NULL
}
template <class T>
bool CBintree<T>::Depth_RF() //先根深度遍历
{
cout <<"先根遍历序列:\n"
stack <TreeNode>s
s.push(*m_pBintree)
while (!s.empty())
{
TreeNode node_s = s.top()
cout <<node_s.va <<"\n"
s.pop()
if (node_s.prchild != NULL)
{
s.push(*node_s.prchild)
}
if (node_s.plchild != NULL)
{
s.push(*node_s.plchild)
}
}
return true
}
template <class T>
bool CBintree<T>::Depth_RM() //中根深度遍历
{
cout <<"中根遍历序列:\n"
stack <TreeNode>s
TreeNode *pNode = m_pBintree
while (pNode != NULL || !s.empty())
{
while (pNode != NULL)
{
s.push(*pNode)
pNode = pNode->plchild
}
if (!s.empty())
{
TreeNode node_s = s.top()
cout <<node_s.va <<"\n"
s.pop()
pNode = node_s.prchild
}
}
return true
}
template <class T>
bool CBintree<T>::WidthFS() //层次遍历
{
cout <<"层次遍历序列:\n"
queue <TreeNode>q
q.push(*m_pBintree)
while (!q.empty())
{
TreeNode *pNode = &q.front()
cout <<pNode->va <<"\n"
if (pNode->plchild != NULL)
{
q.push(*pNode->plchild)
}
if (pNode->prchild != NULL)
{
q.push(*pNode->prchild)
}
q.pop()
}
return true
}
/************************ main.cpp 文件 ****************************/
#include <iostream>
#include <stack>
#include <queue>
using namespace std
#include "bintree.h"
int main()
{
CBintree <int>bt
bt.Depth_RF()
bt.Depth_RM()
bt.WidthFS()
return 0
}
/***************** 教科书标准算法及优化算法（转）*******************/
1.先序遍历非递归算法
void PreOrderUnrec(Bitree *t)
{
Stack s
StackInit(s)
Bitree *p=t
while (p!=NULL || !StackEmpty(s))
{
while (p!=NULL) //遍历左子树
{
visite(p->data)
push(s,p)
p=p->lchild
}
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s)
p=p->rchild
}//endif
}//endwhile
}
2.中序遍历非递归算法
void InOrderUnrec(Bitree *t)
{
Stack s
StackInit(s)
Bitree *p=t
while (p!=NULL || !StackEmpty(s))
{
while (p!=NULL) //遍历左子树
{
push(s,p)
p=p->lchild
}
if (!StackEmpty(s))
{
p=pop(s)
visite(p->data) //访问根结点
p=p->rchild //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}
3.后序遍历非递归算法
typedef enum tagtype
typedef struct
{
Bitree ptr
tagtype tag
}stacknode
typedef struct
{
stacknode Elem[maxsize]
int top
}SqStack
void PostOrderUnrec(Bitree t)
{
SqStack s
stacknode x
StackInit(s)
p=t
do
{
while (p!=null)//遍历左子树
{
x.ptr = p
x.tag = L//标记为左子树
push(s,x)
p=p->lchild
}
while (!StackEmpty(s) &&s.Elem[s.top].tag==R)
{
x = pop(s)
p = x.ptr
visite(p->data) //tag为R，表示右子树访问完毕，故访问根结点
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R//遍历右子树
p=s.Elem[s.top].ptr->rchild
}
}while (!StackEmpty(s))
}//PostOrderUnrec
4.前序最简洁非递归算法
void PreOrderUnrec(Bitree *t)
{
Bitree *p
Stack s
s.push(t)
while (!s.IsEmpty())
{
s.pop(p)
visit(p->data)
if (p->rchild != NULL) s.push(p->rchild)
if (p->lchild != NULL) s.push(p->lchild)
}
}
5.后序算法之二
void BT_PostOrderNoRec(pTreeT root)
{
stack<treeT *>s
pTreeT pre=NULL
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root)
root = root->left
}
else
{
root = s.top()
if (root->right!=NULL &&pre!=root->right){
root=root->right
}
else{
root=pre=s.top()
visit(root)
s.pop()
root=NULL
}
}
}
}
用matlab求最短路径，其使用的主要函数是digraph、shortestpath。求解方法：
A=[1 2 201 3 142 4 152 5 123 4 103 6 134 5 85 6 84 7 95 7 106 7 12]'
s = A(1,:)
t = A(2,:)
w = A(3,:)
G = digraph(s,t,w)
[path1,d] = shortestpath(G,1,7)
求解结果
path1 = 1 3 4 7 %路线
d = 33 %最短路径长度
最短路径线路图
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）