C语言 二叉树的相关操作
// 头文件 #ifndef __BITREE_H__ #define __BITREE_H__ #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> //线索 存储标志位 // Link(0): 表示指向左右孩子的指针 // Thread(1): 表示指向前驱后继的线索 //typedef enum{Link, Thread} pointerTag; typedef struct Btree { char data; struct Btree *lchild; //左孩子 struct Btree *rchild; //右孩子 }Bitnode, *Bitree; 全局变量,表示先前节点 //Bitree pre; //--------------------------------------------------------------- // 创建树，按照前序遍历的方式 void createBitree(Bitree *tree) { char ch; scanf("%c", &ch); if(ch == '\\') { *tree = NULL; } else { *tree = (Bitree)malloc(sizeof(Bitree)); (*tree)->data = ch; createBitree( &(*tree)->lchild); //递归算法 createBitree( &(*tree)->rchild); } } //--------------------------------------------------------------- //二叉树的销毁 void destroy(Bitree tree) { if( tree ) { destroy(tree->lchild); destroy(tree->rchild); free(tree); } } //--------------------------------------------------------------- //交换左右孩子算法 void exchange(Bitree *tree) { Bitree p = NULL; if( *tree ) { p = (*tree)->lchild; //左右指针交换 (*tree)->lchild = (*tree)->rchild; (*tree)->rchild = p; exchange(&(*tree)->lchild); //递归 exchange(&(*tree)->rchild); } } //--------------------------------------------------------------- //求结点层次数 int getNodeLevel(Bitree T, char x, int* nLevel, int nLevelTemp) { //nLevel 返回目标结点层数 //nLevelTemp 保存当前结点层数 if(!T) { *nLevel = 0; return 0; } if(T->data == x) { *nLevel = nLevelTemp; return 1; } if(getNodeLevel(T->lchild, x, nLevel, nLevelTemp+1)) { printf("%c, ", T->data); return 1; } if(getNodeLevel(T->rchild, x, nLevel, nLevelTemp+1)) { printf("%c, ", T->data); return 1; } return 0; } //------------------------------------------------------------------- //求双亲结点，返回双亲结点指针 Bitree getParent(Bitree T, char x) { Bitree pParent = NULL; if(T->data == x) { printf("目标结点为根结点，无父结点。\n"); return NULL; } if((T->lchild && T->lchild->data == x) || (T->rchild && T->rchild->data == x)) { return T; //取得父节点指针，返回 } if (T->lchild) { pParent = getParent(T->lchild, x); //递归搜索左子树 if (pParent != NULL) return pParent; } if(T->rchild) return getParent(T->rchild, x); //递归搜索右子树 return NULL; } //--------------------------------------------------------------- //按元素值搜素节点 Bitree btSearch(Bitree T, char x) { Bitree pR = NULL; if(T) { if(T->data == x) return T; else { pR = btSearch(T->lchild, x); //递归搜索左子树 if (pR != NULL) { return pR; } return btSearch(T->rchild, x); //递归搜索右子树 } } return NULL; } //--------------------------------------------------------------- //得到孩子节点 int getChildren(Bitree T, char x, Bitree* pL,Bitree* pR) { //pL,pR分别返回左右孩子结点指针 Bitree p = NULL; (*pL) = NULL; (*pR) = NULL; if(T == NULL) return 0; //空树，返回 p = btSearch(T,x); //搜索结点x if(p == NULL) return 1; //x不在树上 if(p->lchild) { (*pL) = p->lchild; //返回左孩子指针 } if(p->rchild) (*pR) = p->rchild; //返回右孩子指针 return 2; } //--------------------------------------------------------------- //求兄弟结点 int getSibling(Bitree T, char x, Bitree* pL, Bitree* pR) { //pL返回左兄弟指针，pR返回右兄弟指针 Bitree p=NULL; (*pL) = NULL; (*pR) = NULL; if(T==NULL) return 0; //空树 p = getParent(T,x); if(p==NULL) { if(T->data==x) return 1; //x为根结点 else return 2; //x不在树上 } if(p->lchild && p->lchild->data==x) { (*pR) = p->rchild; return 3; //右兄弟可能存在 } if(p->rchild && p->rchild->data==x) { (*pL) = p->lchild; return 4; //左兄弟可能存在 } } //--------------------------------------------------------------- //求二叉树的度为二的节点数 int getDoubleNum(Bitree tree) { if(!tree) return 0; if( !tree->lchild && !tree->rchild ) return 0; if( tree->lchild && !tree->rchild ) return getDoubleNum(tree->lchild); if( tree->rchild && !tree->lchild ) return getDoubleNum(tree->rchild); if( tree->lchild && tree->rchild ) return getDoubleNum(tree->lchild) + getDoubleNum(tree->rchild) + 1; } //--------------------------------------------------------------- //求二叉树的叶子节点的个数 int getBeafNum(Bitree tree) { if(!tree) return 0; if(!tree->lchild && !tree->rchild) return 1; return getBeafNum(tree->lchild) + getBeafNum(tree->rchild); } //--------------------------------------------------------------- //求二叉树的节点数 int nodeNum(Bitree tree) { if( !tree ) return 0; else { return nodeNum(tree->lchild) + nodeNum(tree->rchild) + 1; } } //--------------------------------------------------------------- //求二叉树的高度 int getHigh(Bitree tree) { int hl = 0; int hr = 0; if( !tree ) { return 0; } else { hl = getHigh( tree->lchild); hr = getHigh( tree->rchild); if(hl > hr) return hl + 1; else return hr + 1; } } //--------------------------------------------------------------- //访问二叉树节点的具体操作 void visit(char c, int level) { printf("%c 位于 第 %d 层\n", c, level); } //--------------------------------------------------------------- //先序遍历 void traverseFirst(Bitree tree, int level) { if( tree ) { visit( tree->data, level); //访问节点之后你要做什么 traverseFirst( tree->lchild, level + 1); // 递归算法 traverseFirst( tree->rchild, level + 1); } } //--------------------------------------------------------------- //中序遍历 void traverseMiddle(Bitree tree, int level) { if( tree) { traverseMiddle( tree->lchild, level + 1); visit( tree->data, level); traverseMiddle( tree->rchild, level + 1); } } //--------------------------------------------------------------- //后序遍历 void traverseBehind(Bitree tree, int level) { if( tree) { traverseBehind( tree->lchild, level + 1); traverseBehind( tree->rchild, level + 1); visit( tree->data, level); } } //--------------------------------------------------------------- 中序遍历线索化 //void traverseThread(Bitree tree) //{ // if( tree ) // { // traverseThread( tree->lchild ); //递归左孩子线索化 // //结点处理 // if( !tree->lchild ) // {// 如果节点无左孩子 ，设置ltag为thread，lchild指向刚刚访问过的节点 // tree->ltag = Thread; // tree->lchild = pre; // } // if( !pre->rchild ) // { // pre->rtag = Thread; // pre->rchild = tree; // } // pre = tree; // // traverseThread( tree->rchild ); //递归右孩子线索化 // } //} //void inorderThreading(Bitree *t, Bitree tree) //{ // *t = (Bitree)malloc(sizeof(Bitree)); // (*t)->ltag = Link; // (*t)->rtag = Thread; // (*t)->rchild = *t; // if( !tree ) // { // (*t)->lchild = *t; // } // else // { // (*t)->lchild = tree; // pre = *t; // traverseThread( tree ); // pre->rchild = *t; // pre->rtag = Thread; // (*t)->rchild = pre; // } // //} # endif