二叉树基本操作

二叉树基本操作

头文件

#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 */

实现文件

#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()) {
//将左节点一直到最末，入栈
        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;
    }
}