http://www.carrefourstation.com

二叉树的总括

二叉树的豆蔻梢头层层操作,二叉树一多种操作

//二叉树学习过程中的问题和代码集合
//按先序序列创建二叉树
//树的高度
//求树的结点数
//求二叉树第K层的节点个数
//求二叉树中叶子节点的个数
//求二叉树中节点的最大距离
//两结点最低公共祖先
//判断二叉树是不是平衡二叉树
//释放树空间

//感谢:http://blog.csdn.net/luckyxiaoqiang/article/details/7518888#topic1

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

//二叉树结点
typedef int DateType;
typedef struct BiTNode{
    DateType data;
    struct BiTNode *lchild,*rchild,*m_pLeft,*m_pRight;
}BiTNode,*BiTree;

//按先序序列创建二叉树
int CreateBiTree(BiTree &T){

    char data;
    //‘#’表示空树
    cin>>data;
    if(data == '#'){
        T = NULL;
    }
    else{
        T = (BiTree)malloc(sizeof(BiTNode));

        T->data = data;

        CreateBiTree(T->lchild);

        CreateBiTree(T->rchild);
    }
    return 0;
}
//输出
void Visit(BiTree T){
    if(T->data != '#'){
        printf("%c ",T->data);
    }
}

//先序遍历
void PreOrder(BiTree T){
    if(T != NULL){
        //访问根节点
        Visit(T);
        //访问左子结点
        PreOrder(T->lchild);
        //访问右子结点
        PreOrder(T->rchild);
    }
}
//中序遍历  
void InOrder(BiTree T){  
    if(T != NULL){  
        //访问左子结点  
        InOrder(T->lchild);  
        //访问根节点  
        Visit(T);  
        //访问右子结点  
        InOrder(T->rchild);  
    }  
}  
//后序遍历
void PostOrder(BiTree T){
    if(T != NULL){
        //访问左子结点
        PostOrder(T->lchild);
        //访问右子结点
        PostOrder(T->rchild);
        //访问根节点
        Visit(T);
    }
}

//树的高度
//Depth(t)= max( Depth(lchild),Depth(rchild) ) + 1
int BinTreeDepth(BiTree t)
{
    int h,h1,h2;
    if(t == NULL)    return 0;
    else
    {
        h1 = BinTreeDepth(t->lchild);
        h2 = BinTreeDepth(t->rchild);
        h = max(h1,h2) + 1;
        return h;
    }

}

//求树的结点数
//树的结点数=左子树 + 右子树 + 1;
int getNodeNum(BiTree t)
{
    if(t == NULL) return 0;
    return (getNodeNum(t->lchild)+getNodeNum(t->rchild)+1);
}

//求二叉树第K层的节点个数
//NodeNum(t,k) = NodeNum(t->lchild,k-1)+NodeNum(t->rchild,k-1)
int GetNodeNumKthLevel(BiTree t, int k)
{
    if(t == NULL || k < 1)
        return 0;
    if(k == 1)
        return 1;
    // 左子树中k-1层的节点个数
    int numLeft = GetNodeNumKthLevel(t->lchild, k-1); 
    // 右子树中k-1层的节点个数
    int numRight = GetNodeNumKthLevel(t->rchild, k-1); 
    return (numLeft + numRight);
}

//求二叉树中叶子节点的个数
//左右儿子为NULL
//则:LeafNum(t) = LeafNum(t->lchild) + LeafNum(t->rchild);
int GetLeafNodeNum(BiTree t)
{
    if(t == NULL) 
        return 0;
    if(t->lchild ==NULL && t->rchild ==NULL) 
        return 1;
    int numleft = GetLeafNodeNum(t->lchild);
    int numright = GetLeafNodeNum(t->rchild);

    return (numleft + numright);
}

//求二叉树中节点的最大距离
//MaxDistance(t->lchild)//MacDistance(t->rchild)
//MaxLeft(t->lchild)+MaxRight(t->rchild)
int GetMaxDistance(BiTree t, int & maxLeft, int & maxRight)
{
    // maxLeft, 左子树中的节点距离根节点的最远距离
    // maxRight, 右子树中的节点距离根节点的最远距离
    if(t == NULL)
    {
        maxLeft = 0;
        maxRight = 0;
        return 0;
    }
    int maxLL, maxLR, maxRL, maxRR;
    int maxDistLeft, maxDistRight;
    if(t->lchild != NULL)
    {
        maxDistLeft = GetMaxDistance(t->lchild, maxLL, maxLR);
        maxLeft = max(maxLL, maxLR) + 1;
    }
    else
    {
        maxDistLeft = 0;
        maxLeft = 0;
    }
    if(t->rchild != NULL)
    {
        maxDistRight = GetMaxDistance(t->rchild, maxRL, maxRR);
        maxRight = max(maxRL, maxRR) + 1;
    }
    else
    {
        maxDistRight = 0;
        maxRight = 0;
    }
    return max(max(maxDistLeft, maxDistRight), maxLeft+maxRight);
}

//两结点最低公共祖先
//如果两个节点分别在根节点的左子树和右子树,则返回根节点
//如果两个节点都在左子树,则递归处理左子树;如果两个节点都在右子树,则递归处理右子树
//求最近公共祖先:
/*
//应该就是这样的啊,为什么运行的时候出现内存访问冲突的问题........
bool FindNode(BiTree t, DateType x)
{
    if(t == NULL || x == NULL)
        return false;
    if(t->data == x)
        return true;
    bool found = FindNode(t->lchild, x);
    if(!found)
        found = FindNode(t->rchild, x);
    return found;
}

DateType  GetLastCommonParent(BiTree t ,DateType A,DateType B)
{
    if(FindNode(t->lchild,A))
    {
        if(FindNode(t->rchild,B))
            return t->data;
        else
            return GetLastCommonParent(t->lchild,A,B);
    }
    else
    {
        if(FindNode(t->lchild,B))
            return t->data;
        else
            return GetLastCommonParent(t->rchild,A,B);
    }
}
*/

//判断二叉树是不是平衡二叉树
//如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1,返回真,其他返回假
bool isAVL(BiTree t, int & height)
{
    if(t == NULL) // 空树,返回真
    {
        height = 0;
        return true;
    }
    int heightLeft;
    bool resultLeft = isAVL(t->lchild, heightLeft);
    int heightRight;
    bool resultRight = isAVL(t->rchild, heightRight);
    // 左子树和右子树都是AVL,并且高度相差不大于1,返回真
    if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) 
    {
        height = max(heightLeft, heightRight) + 1;
        return true;
    }
    else
    {
        height = max(heightLeft, heightRight) + 1;
        return false;
    }
}

//释放树空间
void DestroyBinTree(BiTree t)
{
    if(t==NULL) return;
    DestroyBinTree(t->lchild); 
    DestroyBinTree(t->rchild);
    t->lchild=NULL;
    t->rchild=NULL;
    free(t);
}


//先序遍历(非递归)
//思路:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,
//出栈,再先序遍历T的右子树。

void PreOrder2(BiTree T){
    stack<BiTree> stack;
    //p是遍历指针
    BiTree p = T;
    //栈不空或者p不空时循环
    while(p || !stack.empty()){
        if(p != NULL){
            //存入栈中
            stack.push(p);
            //访问根节点
            printf("%c ",p->data);
            //遍历左子树
            p = p->lchild;
        }
        else{
            //退栈
            p = stack.top();
            stack.pop();
            //访问右子树
            p = p->rchild;
        }
    }//while
}
//中序遍历(非递归)
//思路:T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。
//先将T入栈,遍历左子树;
//遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。

void InOrder2(BiTree T){
    stack<BiTree> stack;
    //p是遍历指针
    BiTree p = T;
    //栈不空或者p不空时循环
    while(p || !stack.empty()){
        if(p != NULL){
            //存入栈中
            stack.push(p);
            //遍历左子树
            p = p->lchild;
        }
        else{
            //退栈,访问根节点
            p = stack.top();
            printf("%c ",p->data);
            stack.pop();
            //访问右子树
            p = p->rchild;
        }
    }//while
}

//后序遍历(非递归)
typedef struct BiTNodePost{
    BiTree biTree;
    char tag;
}BiTNodePost,*BiTreePost;
//后序遍历
void PostOrder2(BiTree T){
    stack<BiTreePost> stack;
    //p是遍历指针
    BiTree p = T;
    BiTreePost BT;
    //栈不空或者p不空时循环
    while(p != NULL || !stack.empty()){
        //遍历左子树
        while(p != NULL){
            BT = (BiTreePost)malloc(sizeof(BiTNodePost));
            BT->biTree = p;
            //访问过左子树
            BT->tag = 'L';
            stack.push(BT);
            p = p->lchild;
        }
        //左右子树访问完毕访问根节点
        while(!stack.empty() && (stack.top())->tag == 'R'){
            BT = stack.top();
            //退栈
            stack.pop();
            BT->biTree;
            printf("%c ",BT->biTree->data);
        }
        //遍历右子树
        if(!stack.empty()){
            BT = stack.top();
            //访问过右子树
            BT->tag = 'R';
            p = BT->biTree;
            p = p->rchild;
        }
    }//while
}
//层次遍历
void LevelOrder(BiTree T){
    BiTree p = T;
    //队列
    queue<BiTree> queue;
    //根节点入队
    queue.push(p);
    //队列不空循环
    while(!queue.empty()){
        //对头元素出队
        p = queue.front();
        //访问p指向的结点
        printf("%c ",p->data);
        //退出队列
        queue.pop();
        //左子树不空,将左子树入队
        if(p->lchild != NULL){
            queue.push(p->lchild);
        }
        //右子树不空,将右子树入队
        if(p->rchild != NULL){
            queue.push(p->rchild);
        }
    }
}
int main()
{

    //测试:ABC##DE#G##F###
    //测试:124##57##8##3#6##
    BiTree T;
    cout<<"先序输入二叉树"<<endl;
    CreateBiTree(T);

    printf("先序遍历:n");
    PreOrder(T);
    printf("n");

    printf("先序遍历(非递归):n");
    PreOrder2(T);
    printf("n");

    printf("中序遍历:n");
    InOrder(T);
    printf("n");

    printf("中序遍历(非递归):n");
    InOrder2(T);
    printf("n");

    printf("后序遍历:n");
    PostOrder(T);
    printf("n");

    printf("后序遍历(非递归):n");
    PostOrder2(T);
    printf("n");

    printf("层次遍历:n");
    LevelOrder(T);
    printf("n");

    cout<<endl<<"树的高度为:"<<BinTreeDepth(T)<<endl<<endl;

    cout<<"结点数"<<getNodeNum(T)<<endl<<endl;

    cout<<"二叉树第K层的节点个数"<<endl;
    int k;    cin>>k;
    cout<<"二叉树第K层的节点个数"<<endl;
   cout<<GetNodeNumKthLevel(T,k)<<endl<<endl;

    cout<<"二叉树中叶子节点的个数"<<endl<<GetLeafNodeNum(T)<<endl<<endl;

    int maxLeft = 0;
    int maxRight = 0;
    cout<<"二叉树中节点的最大距离"<<endl;
  cout<<<<GetMaxDistance(T, maxLeft, maxRight)<<endl<<endl;

    //cout<<"两结点最低公共祖先"<<endl;
    //DateType A,B;
    ///cin>>A>>B;
    //cout<<GetLastCommonParent(T,A,B)<<endl;

    int height = 0;
    cout<<"判断二叉树是不是平衡二叉树"<<endl<<isAVL(T,height)<<endl<<endl;

    cout <<"释放树空间"<<endl<<endl;
    DestroyBinTree(T);

    system("pause");
    return 0;
}

总结:

二叉树的操作紧如果用递归,只要用递归的合计就非常轻易杀绝难点,可是递归的频率不高,所以在遍历的时候要思虑不用递归该怎么办?

接下来:

用分层的章程来创设二叉树

走访内部存款和储蓄器出错的难点,指针

线索二叉树、寻觅二叉树。

 

// 二叉树学习进度中的难题和代码集结 //按先序系列创制二叉树 //树的万丈 //求树的结点数 //求二...

void BinTree::inOrder(BTNode *cur)
{
    if (cur != nullptr)
    {
        inOrder(cur->leftChild); //递归访问
        cout << cur->data << " ";
        inOrder(cur->rightChild); //递归访问
    }
}
算法步骤:

①将根结点压进队列Q;
②对队列Q实行出队操作,打字与印刷出队结点音信,然后将出队结点的左右儿女结点(当其子女结点存在的情形下卡塔尔压入队列Q;
③重复步骤②的操作直至队列为空

void HierarchyTravel(Tree tree)
{
     LinkQueue q;;
     Init(&q);
     EnQueue(&q,*tree);
     TreeNode node;
     printf("HierarchyTravel:");
     while(!QueueEmpty(&q))
     {
         DeQueue(&q,&node);
         printf("%ct",node.value);
         if(node.LeftChild)
             EnQueue(&q,*node.LeftChild);
         if(node.RightChild)
             EnQueue(&q,*node.RightChild);
     }
}

图片 1图片 2

BinTree::~BinTree()
{
    this->Destory();//撤销一棵树的函数
}

5、二叉树的档案的次序遍历

 1 template<typename T>
 2 struct TreeNode2
 3 {
 4  T data;
 5  TreeNode2* pLChild;
 6  TreeNode2* pRChild;
 7  TreeNode2* pParent;
 8 };
 9 template<typename T>
10 int GetNodeDeepth(TreeNode2<T>* pNode)
11 {
12  int nDeepth = 0;
13  // 此处已判断节点为NULL的情况
14  while(pNode)
15  {
16   ++nDeepth;
17   pNode = pNode->pParent;
18  }
19  return nDeepth;
20 }
21 template<typename T>
22 TreeNode2<T>* FindNearestParentNode(TreeNode2<T>* p1, TreeNode2<T>* p2)
23 {
24  int nDeepth1 = GetNodeDeepth(p1);
25  int nDeepth2 = GetNodeDeepth(p2);
26 
27  TreeNode2* pReturn = NULL;
28  // 把深度大的放在1里
29  if(nDeepth1 < nDeepth2)
30  {
31   pReturn = p1;
32   p1 = p2;
33   p2 = pReturn;
34   pReturn = NULL;
35  }
36  for(int i = 0; i < nDeepth1-nDeepth2; ++i)
37   p1 = p1->pParent;
38  while(p1)
39  {
40   if(p1 == p2)
41   {
42    pReturn = p1;
43    break;
44   }
45   p1 = p1->pParent;
46   p2 = p2->pParent;
47  }
48 
49  return pReturn;
50 }

后序遍历(递归)

7、二叉树的非递归遍历代码

#include "stdafx.h"
#include "stdlib.h"
#include <stack>
#include <iostream>
using namespace std;
typedef struct TreeNode{
    char value;
    struct TreeNode * LeftChild;
    struct TreeNode * RightChild;
}TreeNode,*Tree;
Tree CreatTree()
{   
    char value;
    TreeNode * Node;
    scanf("%c",&value);
    if(value=='#')
        Node=NULL;
    else{
        Node=(TreeNode *)malloc(sizeof(TreeNode));
        Node->value=value;
        Node->LeftChild=CreatTree();
        Node->RightChild=CreatTree();
}
    return Node;

}
void PreTravel(Tree tree)
{
   stack<Tree> s;
   while(tree||!s.empty())
   {
       while(tree)
       {
           printf("%ct",tree->value);
           s.push(tree);
           tree=tree->LeftChild;
       }
       tree=s.top();
       s.pop();
       tree=tree->RightChild;

   }
}
void MiddleTravel(Tree tree)
{
   stack<Tree> s;
   while(tree||!s.empty())
   {
       while(tree)
       {
           s.push(tree);
           tree=tree->LeftChild;
       }
       tree=s.top();
      printf("%ct",tree->value);
      s.pop();
      tree=tree->RightChild;
   }
}

void PostTravel(Tree T)  // 后序遍历的非递归      
{      
    stack<Tree> S;      
    Tree curr = T ;           // 指向当前要检查的节点    
    Tree previsited = NULL;    // 指向前一个被访问的节点    
    while(curr != NULL || !S.empty())  // 栈空时结束      
    {      
        while(curr != NULL)            // 一直向左走直到为空    
        {      
            S.push(curr);      
            curr = curr->LeftChild;      
        }      
        curr = S.top();    
        // 当前节点的右孩子如果为空或者已经被访问,则访问当前节点    
        if(curr->RightChild== NULL || curr->RightChild== previsited)      
        {      
            cout<<curr->value<<"  ";      
            previsited = curr;      
            S.pop();      
            curr = NULL;      
        }      
        else    
            curr = curr->RightChild;      // 否则访问右孩子    
    }      
}  
int _tmain(int argc, _TCHAR* argv[])
{  
    Tree tree;
    int high;
    printf("输入二叉树节点:");
    tree=CreatTree();
   printf("n中序遍历:");
    MiddleTravel(tree);
    printf("n先序遍历:");
    PreTravel(tree);
    printf("n后序遍历:");
    PostTravel(tree);
 /*   high=Height(tree);
    printf("n层次遍历:");
    HierarchyTravel(tree);
    printf("n树高是:%dn",high);*/
    system("PAUSE");
    return 0;
}

分析:比景况1要简宾博些,只需找到多少个节点的深度,就能够当作多少个链表求公共节点。

函数

输入:AB#C##D## ;

View Code

BinTree::BinTree()
{
    root = nullptr;
}

1、二叉树的数据结构

typedef struct TreeNode{

char value;\符号

struct TreeNode * LeftChild;\左孩子

struct TreeNode * RightChild;\右孩子

}TreeNode,*Tree;

平衡二叉树:所谓平衡二叉树指的是,左右四个子树的高度差的断然值不超过1。

前序遍历(递归)

6、测验代码

#include "stdafx.h"
#include "stdlib.h"
typedef struct TreeNode{
    char value;
    struct TreeNode * LeftChild;
    struct TreeNode * RightChild;
}TreeNode,*Tree;
typedef struct QNode{
    TreeNode Node;
    struct QNode * next;
}QNode,*QueueNode;
typedef struct LinkQueue{
    QueueNode front;
    QueueNode rear;
}LinkQueue;
Tree CreatTree()
{   
    char value;
    TreeNode * Node;
    scanf("%c",&value);
    if(value=='#')
        Node=NULL;
    else{
        Node=(TreeNode *)malloc(sizeof(TreeNode));
        Node->value=value;
        Node->LeftChild=CreatTree();
        Node->RightChild=CreatTree();
}
    return Node;

}
void PreTravel(Tree tree)
{
    if(tree)
    {
        printf("%ct",tree->value);
        PreTravel(tree->LeftChild);
        PreTravel(tree->RightChild);
    }
}
void MiddleTravel(Tree tree)
{
    if(tree)
    {   
        MiddleTravel(tree->LeftChild);
        printf("%ct",tree->value);
        MiddleTravel(tree->RightChild);
    }
}
void PostTravel(Tree tree)
{
    if(tree)
    {   
        PostTravel(tree->LeftChild);    
        PostTravel(tree->RightChild);
        printf("%ct",tree->value);
    }
}
void Init(LinkQueue *q)//队列初始化
{
    q->front=q->rear=(QueueNode)malloc(sizeof(QNode));

    if(!q->front)
        exit(0);
    q->front->next=NULL;

}
void EnQueue(LinkQueue *q,TreeNode treenode)//入队
{
    QueueNode qnode;
    qnode=(QueueNode)malloc(sizeof(QNode));
    qnode->Node=treenode;
    /****插入队列****/
    qnode->next=q->rear->next;
    q->rear->next=qnode;
    /****改队尾指针****/
    q->rear=qnode;
}
void DeQueue(LinkQueue *q,TreeNode *node)//出队
{
    QueueNode p;
    p=q->front->next;
    *node=p->Node;
    q->front->next=p->next;
    if(q->rear==p)       //p将被释放,需要对q->rear进行处理。(不能缺)
        q->rear=q->front;
    free(p);
}
int QueueEmpty(LinkQueue *q)//判断队列是否为空
{
    if(q->rear==q->front)
        return 1;
    else
        return 0;
}
void HierarchyTravel(Tree tree)
{
     LinkQueue q;;
     Init(&q);
     EnQueue(&q,*tree);
     TreeNode node;
     while(!QueueEmpty(&q))
     {
         DeQueue(&q,&node);
         printf("%ct",node.value);
         if(node.LeftChild)
             EnQueue(&q,*node.LeftChild);
         if(node.RightChild)
             EnQueue(&q,*node.RightChild);
     }
}
int Height(Tree tree)
{
  int high;
  int left_high;
  int right_high;
  if(tree==NULL)
      return 0;
  left_high=Height(tree->LeftChild);
  right_high=Height(tree->RightChild);
  if(left_high>right_high)
        high=left_high+1;
  else
        high=right_high+1;
  return high;
}
int _tmain(int argc, _TCHAR* argv[])
{  
    Tree tree;
    int high;
    printf("输入二叉树节点:");
    tree=CreatTree();
    printf("n中序遍历:");
    MiddleTravel(tree);
    printf("n先序遍历:");
    PreTravel(tree);
    printf("n后序遍历:");
    PostTravel(tree);
    high=Height(tree);
    printf("n层次遍历:");
    HierarchyTravel(tree);
    printf("n树高是:%dn",high);
    system("PAUSE");
    return 0;
}

图片 3

Paste_Image.png

满二叉树:除最终风度翩翩层外,每意气风发层上的有着节点都有四个子节点,末了风姿浪漫层都以卡牌节点。

二叉树的类

2、二叉树的创造

Tree CreatTree()
{   
    char value;
    TreeNode * Node;
    scanf("%c",&value);
    if(value=='#')//#代表空节点,用来控制树的结构
        Node=NULL;
    else{
        Node=(TreeNode *)malloc(sizeof(TreeNode));
        Node->value=value;
        Node->LeftChild=CreatTree();
        Node->RightChild=CreatTree();
}
    return Node;

}

 

越来越多音信,请关切路人甲的学习记录

树的布局:

图片 4

Paste_Image.png

哈夫曼树:又称之为最有数,那是生机勃勃种带权路线长度最短的树。哈夫曼编码就是哈夫曼树的应用。

增进左子树的函数

4、求二树的中度

对此难点大家得以应用递归的合计,将标题开展表达。树的冲天=max{左子树的万丈,右子树的万丈}+1。

图片 5

Paste_Image.png

int Height(Tree tree)
{
  int high;
  int left_high;
  int right_high;
  if(tree==NULL)
      return 0;
  left_high=Height(tree->LeftChild);
  right_high=Height(tree->RightChild);
  if(left_high>right_high)
        high=left_high+1;
  else
        high=right_high+1;
  return high;
}

 

构造函数的兑现

3、二叉树的遍历

二叉树的遍历分为前序遍历、中序遍历、后序遍历。首要分别在于根节点的遍历优先级。前序:根、左、右;中序:左、根、右;后序:左、右、根。
①递归遍历

Tree Travel(Tree tree)
{
    if(tree==NULL)
          return NULL;
    else
    {        
               /****前序遍历****/
          printf("%ct",tree->value);
          Travel(tree->LeftChild);
          Travel(tree->RightChild);

              /****中序遍历****/
          Travel(tree->LeftChild);
          printf("%ct",tree->value);
          Travel(tree->RightChild);

              /****后序遍历****/
          Travel(tree->LeftChild);
          Travel(tree->RightChild); 
          printf("%ct",tree->value);
    }
}

②非递归遍历

void PreTravel(Tree tree)
{
   stack<Tree> s;
   while(tree||!s.empty())
   {
       while(tree)
       {
           printf("%ct",tree->value);
           s.push(tree);
           tree=tree->LeftChild;
       }
       tree=s.top();
       s.pop();
       tree=tree->RightChild;

   }
}
void MiddleTravel(Tree tree)
{
   stack<Tree> s;
   while(tree||!s.empty())
   {
       while(tree)
       {
           s.push(tree);
           tree=tree->LeftChild;
       }
       tree=s.top();
      printf("%ct",tree->value);
      s.pop();
      tree=tree->RightChild;
   }
}

void PostTravel(Tree T)  // 后序遍历的非递归      
{      
    stack<Tree> S;      
    Tree curr = T ;           // 指向当前要检查的节点    
    Tree previsited = NULL;    // 指向前一个被访问的节点    
    while(curr != NULL || !S.empty())  // 栈空时结束      
    {      
        while(curr != NULL)            // 一直向左走直到为空    
        {      
            S.push(curr);      
            curr = curr->LeftChild;      
        }      
        curr = S.top();    
        // 当前节点的右孩子如果为空或者已经被访问,则访问当前节点    
        if(curr->RightChild== NULL || curr->RightChild== previsited)      
        {      
            cout<<curr->value<<"  ";      
            previsited = curr;      
            S.pop();      
            curr = NULL;      
        }      
        else    
            curr = curr->RightChild;      // 否则访问右孩子    
    }      
}  

 

郑重声明:本文版权归澳门新莆京手机网站所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。