二叉樹基本操作

頭文件

#ifndef BinaryTree_hpp

#define BinaryTree_hpp

#include <stdio.h>

typedef char TelemType;

typedef struct BitNode{

TelemType data;

struct BitNode *lchild,*rchild;

}BitNode;

typedef BitNode *BiTree;

class BinaryTree {

public:

void PreOrderTraverse(BiTree T);

void PreOrderTraverseRec(BiTree T);

void InOrderTraverse(BiTree T);

void InOrderTraverseST(BiTree T);

void PostOrderTraverse(BiTree T);

void PostOrderTraverseRec(BiTree T);

void PostOrderTraverseRec2(BiTree T);

void CreateBitTree(BiTree &T);

void DestoryBitTree(BiTree &T);

};

#endif /* BinaryTree_hpp */

實現(xiàn)文件

#include "BinaryTree.hpp"
#include <iostream>
#include <stack>
using namespace std;
void BinaryTree::PreOrderTraverseRec(BiTree T)
{
    BitNode *p,*q;
    stack<BitNode *>S;
    p = T;
    while(p||!S.empty()) {
        if (p) {
            S.push(p);
            cout<<p->data;
            p=p->lchild;
        }
        else {
            q = S.top();
            S.pop();
            p=q->rchild;
        }
    }
}
void BinaryTree::InOrderTraverse(BiTree T)
{
    if (T) {
        InOrderTraverse(T->lchild);
        cout<<T->data;
        InOrderTraverse(T->rchild);
    }
}
void BinaryTree::InOrderTraverseST(BiTree T)
{
    BitNode *p,*q;
    stack<BitNode *> S;
    p = T;
    while (p||!S.empty()) {
        if (p) {
            S.push(p);
            p= p->lchild;
        }
        else {
            q=S.top();
            S.pop();
            cout<<q->data;
            p=q->rchild;
        }
    }
}
void BinaryTree::PostOrderTraverseRec(BiTree T)
{
    BitNode *p,*q = nullptr;
    p=T;
    stack<BitNode *> S;
    while (p||!S.empty()) {
//將左節(jié)點一直到最末，入棧
        while (p) {
            S.push(p);
            p=p->lchild;
        }
        p=S.top();
        
        if (!p->rchild||p->rchild==q) {
            cout<<p->data;
            q=p;
            p=NULL;
            S.pop();
        }
        else {
            p=p->rchild;
        }
    }
}
void BinaryTree::PostOrderTraverseRec2(BiTree T)
{
    BitNode *cur,*pre = NULL;
    cur=T;
    stack<BitNode *> S;
    S.push(cur);
    while (!S.empty()) {
        cur=S.top();
//要保證根結點在左孩子和右孩子訪問之后才能訪問，因此對于任一結點P，先將其入棧。如果P不存在左孩子和右孩子，則可以直接訪問它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結點。若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結點前面被訪問
        if ((!cur->lchild&&!cur->rchild)||(pre&&(pre==cur->lchild||pre==cur->rchild))) {
            cout<<cur->data;
            S.pop();
            pre=cur;
        }
        else {
            if (cur->rchild) {
                S.push(cur->rchild);
            }
            if (cur->lchild) {
                S.push(cur->lchild);
            }
        }
    }
}
void BinaryTree::CreateBitTree(BiTree &T)
{
    char ch;
    cin>>ch;
    if (ch == '#') {
        T=NULL;
    }
    else {
        T= new BitNode;
        T->data = ch;
        CreateBitTree(T->lchild);
        CreateBitTree(T->rchild);
    }
}
void BinaryTree::DestoryBitTree(BiTree &T)
{
    if (T) {
        DestoryBitTree(T->lchild);
        DestoryBitTree(T->rchild);
        delete T;
        T=NULL;
    }
}