首页 > 代码库 > 二叉树的遍历

二叉树的遍历

2024-07-09 13:27:44   224人阅读

中序遍历思想

若二叉树为空，则结束遍历操作；否则中序遍历根节点的左子树；访问根节点；中序遍历右子树；

实现代码：

//中序遍历代码template<typename T>void BinaryTree<T>::InTraBiTree(BTNode<T> *p){    if(p)    {        InTraBiTree(p->lchild);        cout<<p->data<<" ";        InTraBiTree(p->rchild);    }}

下面是伪代码模拟计算机步骤帮助理解。

假设有这样一个简单二叉树

伪代码模拟计算机步骤如下：

 InTraBiTree(a){    if(a)    {        InTraBiTree(b)//a左为b,不为空        {            if(b)            {                InTraBiTree(b左子)//b左子为空，直接执行下一步                {                    if(NULL){};                }                cout<<b;                                InTraBiTree(c)//b右子为c                {                    if(c)                    {                        InTraBiTree(c左子)//c左子为空，直接执行下一步                        cout<<c;                        InTraBiTree(c右子)//c右子为空，直接执行下一步                    }                }//end c   c层执行结束，跳到b层            }        }//end b     b层结束跳到a层        cout<<a;        InTraBiTree(d)//a右为d        {            if(d)            {                InTraBiTree(d左子)//d左子为空，直接执行下一步                cout<<d                InTraBiTree(d右子)//d右子为空，直接执行下一步            }        }    }}

下面是完全实现代码（C++版），可以测试下

template<typename T>struct BTNode{    T data;    BTNode<T> *lchild;    BTNode<T> *rchild;};template<typename T>class BinaryTree{private:    BTNode<T> *BT;public:    BinaryTree(){BT=NULL;}//构造函数，构造根节点并将根节点置空        void CreateBiTree(T end);//创建结束标志位end的二叉树        BTNode<T> * GetRoot();//返回根地址        void InTraBiTree(BTNode<T> *p);//中序遍历二叉树};void BinaryTree<T>::CreateBiTree(T end){    cout<<"输入二叉树,以"<<end<<"为空指针域的标志："<<endl;    BTNode<T> *p;    T x;    cin>>x;    if(x==end)        return;    p=new BTNode<T>;    p->data=http://www.mamicode.com/x;    p->lchild=NULL;    p->rchild=NULL;    BT=p;    create(p,1,end);    create(p,2,end);}template<typename T>static int create(BTNode<T> *p,int k,int end){    BTNode<T> *q;    T x;    cin>>x;    if(x!=end)    {        q=new BTNode<T>;        q->data=http://www.mamicode.com/x;        q->lchild=NULL;        q->rchild=NULL;        if(k==1) p->lchild=q;        if(k==2) p->rchild=q;        create(q,1,end);        create(q,2,end);    }    return 0;}template<typename T>BTNode<T> * BinaryTree<T>::GetRoot(){    return BT;}template<typename T>void BinaryTree<T>::InTraBiTree(BTNode<T> *p){    if(p)    {        InTraBiTree(p->lchild);        cout<<p->data<<" ";        InTraBiTree(p->rchild);    }}#include<iostream>using namespace std;#include"BinaryTree.h";int main(void){        BinaryTree<char> b;//构造二叉树对象，仅有一个b 指针指向NULL    char end=‘#‘;    b.CreateBiTree(end);//创建二叉树，以#为结束标志    getchar();    cout<<"中序遍历二叉树：";    b.InTraBiTree(b.GetRoot());    cout<<endl;            getchar();}

 


联系
我们