資料結構基礎—二叉樹的非遞回遍歷和基本操作

非遞回遍歷

先序

//非遞回先序遍歷二叉樹
void zhongxu(BiTree T){
    BiTree stack[MAX];//模擬堆疊 
	BiTree node;
    int top = 0;
    if(T == NULL){
        printf("樹為空樹!\n");
        return;
    }else{
        stack[++top] = T;
         while(node != NULL || top > 0){//樹不慷訓是堆疊不空 
             node = [top--];
             printf("%c", node->data;
                    
             if(node->rchild != NULL) stack[++top] = node->rchild;
             if(node->lchild != NULL) stack[++top] = node->lchild;
         }
    }
}

中序

//非遞回中序遍歷二叉樹
void zhongxu(BiTree T){
    BiTree stack[MAX];//模擬堆疊 
	BiTree node;
    int top = 0;
 
    if(T == NULL){
        printf("樹為空樹!\n");
        return;
    }
    node = T;
    while(node != NULL || top > 0){//樹不慷訓是堆疊不空 
        //將所有的左子樹節點入堆疊
        while (node != NULL) {
            stack[++top] = node;//沒有將top下至一個單位 
            node = node->lchild;
        }
        node = stack[top];//此時指標指向節點的左孩子為空節點(一定沒有)，訪問節點
        top--;//退堆疊 
        printf("%c", node->data);
        //指標指向右孩子
        node = node->rchild;
    }
}

后序

//非遞回后序 
void houxu(BiTree T){
    BiTree p = T;
    BiTree stack[MAX];
    BiTree r = NULL;//輔助指標,記錄被訪問過的節點
    int top = 0;
    while (p || top >= 1){//樹不慷訓是堆疊不空   
        while (p) {//左子全部進堆疊 
            stack[++top] = p;
            p = p->lchild;
        }
        
        p = stack[top]; //指標指向最后一個入堆疊的左節點
        if (NULL== p->rchild || p->rchild == r) {//此節點沒有右孩子或者右孩子已經訪問過=>訪問它 
            printf("%c", p->data);//訪問該節點值
            top--;//退堆疊  
            r = p;  //記錄最近訪問過的節點
            p = NULL;   //節點訪問完后重置p指標，p要重新指向退堆疊后的堆疊頂 
        }
        else {
            p = p->rchild; //右孩子存在則指向右孩子，重復上面操作
        }  
    }
}

基本操作

先序創建二叉樹

/* 先序遍歷創建二叉樹*/
void createBiTree(BiTree *t){ 
    char s;
    BiTree q;
    cout << "請輸入二叉樹(先序，#為空):";
    s=getche();
    cout << endl;
    if(s=='#'){
	    *t=NULL;
		return;}
    q = new BtNode;
    if(q == NULL)  exit(0); 
    q->data=https://www.cnblogs.com/wht-de-bk/p/s;
    *t=q;
    createBiTree(&q->lchild); /*遞回建立左子樹*/
    createBiTree(&q->rchild); /*遞回建立右子樹*/
}

后序銷毀二叉樹

void DeleteBiTree(BiTree T){
    if(T){
         DeleteBiTree(T->lchild);
         DeleteBiTree(T->rchild);
         free(T);
    }
}
void DestroyBiTree(BiTree T){
    DeleteBiTree(BiTree T);
    T = NULL;
}

算結點數

空數為零；否則左+右+1

//求結點 
int qiujiedian(BiTree p){
	
	if(p == NULL) return 0;
	else return (qiujiedian(p->lchild)+qiujiedian(p->rchild)+1);
}

算深度

空樹為零；否則max(左深，右深)+1

//算深度(max子樹+1)
int qiushendu(BiTree T){
	if(T == NULL) return 0;
	if(T->left == 0&&T->right == 0) return 1;//T不是下一個結點就是當前結點所以... 
	return(max(qiushendu(T->lchild),qiushendu(T->rchild))+1);
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536104.html

標籤：其他

上一篇：室內定位競爭格局：四大梯隊，你更看好誰？

下一篇：基礎資料結構 -鏈表