二叉樹的基本操作（遞歸和非遞歸）

遞歸：

#include<stdio.h>
#include<malloc.h>
#include <iostream>
using namespace std;
#define MAX 20
int g_num;
typedef struct BTNode{       /*節點結構聲明*/
	char data ;               /*節點資料*/
	struct BTNode *lchild;
	struct BTNode *rchild ;  /*指針*/
}BTNode,*BiTree;

void createBiTree(BiTree *t){ /* 先序周遊建立二叉樹*/
	char s;
	BiTree q;
	s=getchar();
	if(s=='#'){*t=NULL; return;}
	q=(BiTree)malloc(sizeof(struct BTNode));
	if(q==NULL){printf("Memory alloc failure!"); exit(0);}
	q->data=s;
	*t=q;
	createBiTree(&q->lchild); /*遞歸建立左子樹*/
	createBiTree(&q->rchild); /*遞歸建立右子樹*/
}

void PreOrder(BiTree p){  /* 先序周遊二叉樹*/
    if ( p!= NULL ) {
       	printf("%c", p->data);
       	PreOrder( p->lchild ) ;
       	PreOrder( p->rchild) ;
    }
}
void InOrder(BiTree p){  /* 中序周遊二叉樹*/
    if( p!= NULL ) {
 	 InOrder( p->lchild ) ;
   	 printf("%c", p->data);
   	 InOrder( p->rchild) ;
    }
}
void PostOrder(BiTree p){  /* 後序周遊二叉樹*/
   if ( p!= NULL ) {
    	PostOrder( p->lchild ) ;
       	PostOrder( p->rchild) ;
       	printf("%c", p->data);
    }
}

void Preorder_n(BiTree p){ /*先序周遊的非遞歸算法*/
    BiTree stack[MAX],q;
    int top=0,i;
    for(i=0;i<MAX;i++) stack[i]=NULL;/*初始化棧*/
    q=p;
    while(q!=NULL){
        printf("%c",q->data);
        if(q->rchild!=NULL) stack[top++]=q->rchild;
        if(q->lchild!=NULL) q=q->lchild;
        else
            if(top>0) q=stack[--top];
            else q=NULL;
    }
}

void release(BiTree t){ /*釋放二叉樹空間*/
  	if(t!=NULL){
    	release(t->lchild);
    	release(t->rchild);
    	free(t);
  	}
}
//deepth
int Depth(BiTree p)
{
    int m,n;
    if(p==NULL)
    {
        return 0;
    }
    else
    {
         m = Depth(p->lchild);
         n = Depth(p->rchild);
        return (m>n) ? m+1 : n+1;
     }
}
//sum of node
int Nodecount(BiTree p)
{
    if(p==NULL)
    {
        return 0;
    }
    else
        return Nodecount(p->lchild) + Nodecount(p->rchild) + 1;
}
//leaf
void countleaf(BiTree p)
{
    if(p){
        if(p->lchild==NULL&&p->rchild==NULL)
        {
            g_num++;
        }
        else{
            countleaf(p->lchild);
            countleaf(p->rchild);
        }
    }
}
BTNode* copyBiTree(BiTree T)
{
    BiTree NLT = NULL;
    BiTree NRT = NULL;
    BiTree newNode = new BTNode;
    if(T->lchild)
    {
        NLT = copyBiTree(T->lchild);
    }
    else
    {
        NLT = NULL;
    }
    if(T->rchild)
    {
        NRT = copyBiTree(T->rchild);
    }
    else
    {
        NRT = NULL;
    }
    if(newNode == NULL)
    {
        return 0;
    }
    newNode->lchild = NLT;
    newNode->rchild = NRT;
    newNode->data = T->data;
    return newNode;

}
int main(){
    BiTree t=NULL;
    printf("\nplease input data:(exit for #)");
    createBiTree(&t);
    BiTree newT = NULL;
    newT = copyBiTree(t);
    g_num = 0;
    cout<<"PreOrder the tree is:";
    PreOrder(t);
    cout<<endl;
    cout<<"InOrder the tree is:";
    InOrder(t);
    cout<<endl;
    cout<<"PostOrder the tree is:";
    PostOrder(t);
    cout<<endl;
    cout<<"先序非遞歸周遊:";
    Preorder_n(t);
    cout<<endl;
    cout<<"Depth"<<endl;
    int ans = Depth(t);
    cout<<ans<<endl;
    cout<<"Ndenum"<<endl;
    cout<<Nodecount(t)<<endl;
    cout<<"LeafNodenum"<<endl;
    countleaf(t);
    cout<<g_num<<endl;
    cout<<endl;
    cout<<"copy the tree"<<endl;
    g_num = 0;//重新初始化
    cout<<"PreOrder the tree is:";
    PreOrder(newT);
    cout<<endl;
    cout<<"InOrder the tree is:";
    InOrder(newT);
    cout<<endl;
    cout<<"PostOrder the tree is:";
    PostOrder(newT);
    cout<<endl;
    cout<<"先序非遞歸周遊:";
    Preorder_n(newT);
    cout<<endl;
    cout<<"Depth"<<endl;
    ans = Depth(newT);
    cout<<ans<<endl;
    cout<<"Nodenum"<<endl;
    cout<<Nodecount(newT)<<endl;
    cout<<"LeafNodenum"<<endl;
    countleaf(newT);
    cout<<g_num<<endl;
    release(newT);
    cout<<"成功驗證周遊，複制，深度，總結點，葉子結點函數，并釋放了記憶體"<<endl;
    return 0;
}
           

非遞歸：

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <bits/stdc++.h>
using namespace std;

typedef struct BiTreeNode
{
    struct BiTreeNode * lchild;
    struct BiTreeNode * rchild;
    char data;
}BiTreeNode,*BiTree;

void createBiTree(BiTree *t){ /* 先序周遊建立二叉樹*/
	char s;
	BiTree q;
	s=getchar();
	if(s=='#'){*t=NULL; return;}
	q=(BiTree)malloc(sizeof(struct BiTreeNode));
	if(q==NULL){printf("Memory alloc failure!"); exit(0);}
	q->data=s;
	*t=q;
	createBiTree(&q->lchild); /*遞歸建立左子樹*/
	createBiTree(&q->rchild); /*遞歸建立右子樹*/
}

BiTreeNode *GoFarLeft(BiTreeNode *T,stack<BiTreeNode *> &s)
{
    if(T==NULL)
    {
        return NULL;
    }
    while(T->lchild)
    {
        s.push(T);
        T = T->lchild;
    }
    return T;
}

void InOrder(BiTree T)
{
    stack<BiTree> s;
    //step 1：一直往左走，找到中序周遊的起點
    BiTree t = GoFarLeft(T,s);
    while(t)
    {
        cout<<t->data<<" ";
        //if lchild is not NULL,redo step 1
        if(t->rchild!=NULL)
        {
            t = GoFarLeft(t->rchild,s);
        }
        //visit the stack top element
        else if(!s.empty())
        {
            t = s.top();
            s.pop();
        }
        //if rchild is null&&stack is empty
        else
        {
            t = NULL;
        }
    }
}

int main()
{
    BiTree T;
    cout<<"input(end#)"<<endl;
    createBiTree(&T);
    cout<<endl;
    cout<<"樹的非遞歸中序周遊順序："<<endl;
    InOrder(T);
    return 0;
}
           

注：非遞歸用到了c++棧容器，如果沒學到的話可以自己編寫棧程式也是一樣的