关于二叉树链表的相关操作
关于链式二叉树，其实递归是最重要的，我们学会了递归，也就对二叉链表的基本操作有了很深刻的了解。
对于二叉树的基本结构：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。1 #define MAXLEN 100 2 typedef char elementType; 3 4 typedef struct lBNode{ 5 elementType data; 6 struct lBNode *lChild,*rChild; 7 }BiNode,*BiTree;
为了代码的可移植性与简洁性，我们一般都需要定义许多的typedef
其次就是二叉树的建立，二叉树的建立一般来说分为两种，用户交互性的输入，一般来说是按先序输入每个节点的信息，当前节点为空，则输入特殊字符，相关代码如图所示
void createBinaryTree( BiNode *&BT ) { elementType x; cin>>x; if ( x == '/' ) { return; } else { BT = new BiNode; BT->data = x; BT->lChild = NULL; BT->rChild = NULL; createBinaryTree(BT->lChild); createBinaryTree(BT->rChild); } }
但是，这种输入的方法是有问题的，因为树的节点信息多而且比较乱，一旦输错，很有可能会前功尽弃，所以，我们一般会建议以文件的方式读取二叉树的相关信息，将文件中的节点信息读入一个二维数组中，然后根据二维数组来构建二叉树。
//二叉树数据文件 //二叉树标识--BinaryTree，无此标识将判定文件格式不对。 //每行表示二叉树中的一个结点。由3项组成： //第一项是结点元素值； //第二项表示此结点有无左子树，其中：1--有左子树，0--无左子树； //第三项表示此结点有无右子树，其中：1--有右子树，0--无右子树。 //结点次序（从上到下）必须严格按照先序遍历次序排列。 //文件扩展名没有限制，程序只根据标识“BinaryTree”判定是否二叉树数据文件。 //文件中可以有空行。 //文件可以有注释行，注释行必须以“//”开始，且注释行必须是单独的行，不能混杂在标识行、数据行中 //此二叉树有12个结点 BinaryTree A 1 1 B 1 1 C 0 0 D 1 1 E 0 0 F 0 0 G 1 1 H 1 1 I 0 0 J 1 0 K 0 0 L 0 0
而文件格式一般来说，除了前面的注释，空格之类的东西，一般来说，首先是"BinaryTree“等相关标志，保证打开文件正确，并且告诉计算机下面开始读取数据，首先是将这个文本读取到一个二维数组中，代码如图所示：
bool ReadFileToArray( char fileName[],char strLen[100][3],int &nArrlen ) { //fileName存放文件名 //strLen[][3]存放节点的二维数组，数组的三列对应数据文件的三列 //nArrlen返回二叉树节点的个数 FILE *pFile; char str[1000]; //读取第一行文本的字符串 char strTmp[10] = ""; pFile = fopen(fileName,"r"); if ( pFile == NULL ) { cout<<"二叉树文件打开失败!"<<endl; return false; } while ( fgets(str,1000,pFile) != NULL ) { TrimLeft(str); //这个函数是为了去掉左面的空格，须自定义 if ( str[0] == '\n' ) { continue; //空行跳过 } strncpy(strTmp,str,2); if ( strcmp (strTmp,"//") == 0 ) { continue; } else { break; } } //读取文件第一行，判断标识是否正确 if ( strcmp(str,"BinaryTree\n") != 0 ) { cout<<"文件打开错误！"<<endl; fclose(pFile); return false; } nArrlen = 0; char s[10]; fgets(s,10,pFile);//读取文件中的空行 while(fscanf(pFile,"%c %c %c\n",&strLen[nArrlen][0],&strLen[nArrlen][1],&strLen[nArrlen][2]) != EOF ) { nArrlen++; } fclose(pFile); return true; }
我们通过这个代码可以看出来，前面的循环是为了跳过注释行，以及对“BinaryTree"标志进行判断，这里还用到了自定义函数TrimLeft，用于对左面空格进行消除,整体的代码组织比较简单，可用于一些简单的创立，对于这个，就不再过多的描述了
我们在将这个数组存入数据之后，便可以仿照上面的交互式创建二叉树的过程，将数组数据作为输入的标准
bool CreateBiTreeFromFile( BiNode *&pBT,char strLen[100][3],int nLen,int &nRow ) { //strLen[100][3]储存二叉树的节点信息 //nLen表示节点个数 //nRow表示当前的行数 if ( nRow > nLen || nLen == 0 ) { return false; } pBT = new BiNode; pBT->data = strLen[nRow][0]; pBT->lChild = NULL; pBT->rChild = NULL; int nRowNext = nRow; if ( strLen[nRowNext][1] == '1' ) { nRow++; CreateBiTreeFromFile(pBT->lChild,strLen,nLen,nRow); } if ( strLen[nRowNext][2] == '1' ) { nRow++; CreateBiTreeFromFile(pBT->rChild,strLen,nLen,nRow); } return true; }
通过这些代码，我们可以看到它其实就是交互性建立二叉树，通过递归先序创建二叉树，这套方法最有效，也是最容易理解的。
在建立完二叉树之后，我们便可以进行我们所想的操作，我在上面说过，二叉树的大部分操作都是建立在遍历的基础上，而遍历又分为先序，中序，后序，按组成结构来说，又分为递归与非递归，递归操作简单便于理解，许多操作用递归往往只需要几行代码便可以轻松解决，在本人看来，递归操作，也就是分治，将一个大问题分解成几个相同的小问题来解决，而小问题又可以再分，直到一个特殊的出口，而我们人脑所需要考虑的，便是开头和结尾，我们只需要考虑如何分，然后如何找到出口。
if （是出口）
{********}
else （不是出口）
{********}
至于中间如何分，分多少个，我们便不需要考虑，把这些工作都交给计算机来操作，当然，具体的操作还需要我们一点点去摸索，这中间还涉及到参数的传递，返回值等一系列问题，这些都需要读者自己去慢慢摸索，我们现在先对于树的遍历进行讨论，三种遍历方式如图所示//
//先序遍历
void PreOrderTraverse( BiNode *BT ) { if ( BT ) { cout<<BT->data<<","; PreOrderTraverse(BT->lChild); PreOrderTraverse(BT->rChild); } }
//中序遍历 void InOrderTraverse( BiNode *BT ) { if ( BT ) { InOrderTraverse(BT->lChild); cout<<BT->data<<","; InOrderTraverse(BT->rChild); } }
//后序遍历 void PostOrderTraverse( BiNode *BT ) { if ( BT ) { PostOrderTraverse(BT->lChild); PostOrderTraverse(BT->rChild); cout<<BT->data<<","; } }
这三种遍历方式的区别便在于输出的位置，对一棵二叉树来说，遍历的方式其实只有一种，那就是从左到右，从上到下，指针的移动也正是遵循这个，但是，输出的位置不同就导致出现了三种遍历的方式，下面附一张图，便于你理解，
假如你理解了递归遍历的要点，那么许多的比较常见的树操作都是根据这三种遍历方法来实现的：
1、求二叉树的高度
1 int DepthTree ( BiNode *BT ) 2 { 3 if ( BT == NULL ) 4 { 5 return 0; 6 } 7 else 8 { 9 int left,right; 10 left = DepthTree(BT->lChild); 11 right = DepthTree(BT->rChild); 12 13 return ((left > right)?left:right) + 1; 14 } 15 }
求高度，根据上面所说，分治并考虑开头和出口，求一个节点的高度，其实就是找到左右子树最高的高度并加一，如图else，这样递归下去，总会有出口，当节点为空时，便返回0
就这样，我们就可以很轻松的求出二叉树的高度
同样的还有很多：
求二叉树的节点数目：
1 int GetNodeNumber ( BiNode *BT ) 2 { 3 if ( BT == NULL ) 4 { 5 return 0; 6 } 7 else 8 { 9 return GetNodeNumber(BT->lChild) + GetNodeNumber(BT->rChild) + 1; 10 } 11 }
求叶子节点数：
1 int GetLeafNumber( BiNode *BT ) 2 { 3 if ( BT == NULL ) 4 { 5 return 0; 6 } 7 else if ( BT != NULL && BT->lChild == NULL && BT->rChild == NULL ) 8 { 9 return 1; 10 } 11 else 12 { 13 return GetLeafNumber( BT->lChild ) + GetLeafNumber( BT->rChild ); 14 } 15 }
从这段代码我们可以注意到，对于出口的考虑是至关重要的，假如我们只考虑到BT为空的情况，那么最后一路返回值都会是零，那么结果就会错误，但假如我们只考虑到叶子节点的条件，那么我们势必会导致程序崩溃，因为BT为空没有出口，只能执行else，那么就会出错。
3、求分支节点
1 int GetBranchNumber ( BiNode *BT ) 2 { 3 if ( BT == NULL || ( BT->lChild == NULL && BT->rChild == NULL) ) 4 { 5 return 0; 6 } 7 else 8 { 9 return GetBranchNumber(BT->lChild) + GetBranchNumber(BT->rChild) + 1; 10 } 11 }
4、求父节点
1 BiTree GetParent ( BiNode *BT,elementType x ) 2 { 3 BiTree temp1,temp2; 4 if ( BT->lChild != NULL || BT->rChild != NULL ) 5 { 6 if ( (BT->lChild != NULL && BT->lChild->data == x) || (BT->rChild != NULL && BT->rChild->data == x) ) //假如是当前节点的话，则返回 7 { 8 return BT; 9 } 10 else 11 { 12 if ( BT->lChild != NULL ) 13 { 14 temp1 = GetParent(BT->lChild,x); //在左子树寻找 15 16 } 17 if ( BT->rChild != NULL ) 18 { 19 temp2 = GetParent(BT->rChild,x); //在右子树寻找 20 } 21 if ( temp1 != NULL ) 22 { 23 return temp1; 24 } 25 if ( temp2 != NULL ) 26 { 27 return temp2; 28 } 29 } 30 } 31 else 32 { 33 return NULL; //未找到的话则返回空 34 } 35 }
5、求孩子节点
1 void GetChild ( BiNode *BT,elementType x ) 2 { 3 if (BT) 4 { 5 if ( BT->data == x ) 6 { 7 if ( BT->lChild != NULL ) 8 { 9 cout<<"左孩子存在，为："<<BT->lChild->data<<endl; 10 } 11 else 12 { 13 cout<<"左孩子不存在"<<endl; 14 } 15 if ( BT->rChild != NULL ) 16 { 17 cout<<"右孩子存在，为："<<BT->rChild->data<<endl; 18 } 19 else 20 { 21 cout<<"右孩子不存在"<<endl; 22 } 23 } 24 else 25 { 26 GetChild(BT->lChild,x); 27 GetChild(BT->rChild,x); 28 } 29 } 30 }
6、求某节点的层次
1 int GetNodeLevel ( BiNode *BT,elementType x,int h ) //注意这个h是默认的值1 2 { 3 if ( BT == NULL ) 4 { 5 return 0; 6 } 7 else if ( BT->data == x ) 8 { 9 return h; 10 } 11 else 12 { 13 int l = GetNodeLevel(BT->lChild,x,h+1);//先遍历左子树，假如左子树不存在，再遍历右子树 14 if ( l != 0 ) 15 { 16 return l; 17 } 18 else 19 { 20 return GetNodeLevel(BT->rChild,x,h+1); 21 } 22 } 23 }
7、交换左右子树的指针
1 void SwapSubTree( BiNode *BT ) 2 { 3 BiNode *temp; 4 5 if ( BT != NULL ) 6 { 7 temp = BT->lChild; 8 BT->lChild = BT->rChild; 9 BT->rChild = temp; 10 SwapSubTree(BT->lChild); 11 SwapSubTree(BT->rChild); 12 } 13 }
8、求两个节点最近的公共祖先
1 BiTree CommonParent( BiNode *BT,elementType x1,elementType x2 ) 2 { 3 if ( BT == NULL || BT->data == x1 || BT->data == x2 ) 4 { 5 return BT; 6 } 7 else 8 { 9 BiTree left = CommonParent(BT->lChild,x1,x2); 10 BiTree right = CommonParent(BT->rChild,x1,x2); 11 12 if ( left != NULL && right != NULL ) 13 { 14 return BT; 15 } 16 else if ( left == NULL && right != NULL ) 17 { 18 return right; 19 } 20 else if ( left != NULL && right == NULL ) 21 { 22 return left; 23 } 24 } 25 }
9、二叉树的复制
1 void BiTreeCopy ( BiNode *BT,BiNode *&bt ) 2 { 3 if (BT) 4 { 5 bt = new BiNode; 6 bt->data = BT->data; 7 bt->lChild = NULL; 8 bt->rChild = NULL; 9 BiTreeCopy(BT->lChild,bt->lChild); 10 BiTreeCopy(BT->rChild,bt->rChild); 11 } 12 }
经过上面这么多的递归函数的训练，相信你也差不多对递归有一点理解了，其实他的关键便在于能否分治，以及在分治后，如何恰当的找到开头和出口。但是，递归也是具有很大的缺点的，一次次递归会占用大量的空间，他的时间和空间效率远比循环，非递归等操作要低，而且递归是一个整体的过程，我们很难让他中间停止。
但是，目前我们还没找到比递归遍历二叉树更好的方法，绝大多数高校都在课本中介绍了二叉树遍历的非递归遍历方法，但是，实际上这个是没有什么实际应用价值的，因为他只是对通过栈实现递归的模拟，而且他的时间和空间性能远比不上系统栈，所以，除了极个别函数之外，我们一般不建议使用它
和递归一样，非递归的操作也是从三种遍历开始的：
//先序非递归遍历
1 void PreOrderTraverseNR( BiNode *BT ) 2 { 3 BiNode *p; 4 Stack S; 5 initialStack(&S); 6 p = BT; 7 8 while( p || !stackEmpty(&S) ) 9 { 10 if (p) 11 { 12 cout<<p->data<<","; 13 pushStack(&S,p); 14 p = p->lChild; 15 } 16 else 17 { 18 popStack(&S,&p); 19 p = p->rChild; 20 } 21 } 22 }
//中序非递归遍历 23 void InOrderTraverseNR( BiNode *BT ) 24 { 25 BiNode *p; 26 Stack S; 27 p = BT; 28 initialStack(&S); 29 30 while ( p || !stackEmpty(&S) ) 31 { 32 if (p) 33 { 34 pushStack(&S,p); 35 p = p->lChild; 36 } 37 else 38 { 39 popStack(&S,&p); 40 cout<<p->data<<","; 41 p = p->rChild; 42 } 43 } 44 }
//后序非递归遍历 45 void PostOrderTraverseNR( BiNode *BT ) 46 { 47 BiNode *p; 48 Stack S; 49 int tag[MAXLEN]; 50 p = BT; 51 initialStack(&S); 52 53 while ( p || !stackEmpty(&S) ) 54 { 55 if (p) 56 { 57 pushStack(&S,p); 58 tag[S.top] = 0; 59 p = p->lChild; 60 } 61 else 62 { 63 stackTop(&S,&p); 64 if ( tag[S.top] == 0 ) 65 { 66 tag[S.top] = 1; 67 p = p->rChild; 68 } 69 else 70 { 71 popStack(&S,&p); 72 cout<<p->data<<","; 73 p = NULL; 74 } 75 } 76 } 77 }
对于非递归遍历便不再多说，他也仅仅是一种模拟罢了，先序和中序理解起来比较简单，自行找一个树进行模拟一下即可，对于后序遍历的树，它多加了一个tag用来标记是否遍历，后序遍历的左右根因为一个节点想要输出，必须要在左右节点子树都遍历过的情况下才能输出。
对于这种鸡肋的算法，其实也有很多函数也是通过这三种遍历来实现的。
求节点路径
这个算法其实有很多实现的方法，但是，我个人觉得比较正统的便是后序非递归遍历，因为后序遍历的特点便是左右子树先输出然后再输出根节点，也就是说，在找到一个节点的时候，那么根据栈先进后出的特点，栈中储存的便是一个又一个根节点，这便是天然的路径。
1 int BiNodePath ( BiNode *BT,elementType x ) 2 { 3 Stack S; 4 initialStack(&S); 5 BiNode *pt = BT; 6 int tag[MAXLEN]; 7 int n; 8 while ( pt != NULL || !stackEmpty(&S) ) 9 { 10 if (pt) 11 { 12 pushStack(&S,pt); 13 tag[S.top] = 0; 14 pt = pt->lChild; 15 } 16 else 17 { 18 stackTop(&S,&pt); 19 if ( tag[S.top] == 0 ) 20 { 21 tag[S.top] = 1; 22 pt = pt->rChild; 23 } 24 else 25 { 26 if ( pt->data == x ) 27 { 28 int j = 0; 29 while (!stackEmpty(&S)) //在找到这个节点时，弹出所有的栈元素，并结束程序 30 { 31 stackTop(&S,&pt); 32 cout<<pt->data<<"--"; 33 popStack(&S,&pt); 34 j++; 35 } 36 cout<<endl; 37 return j; 38 } 39 popStack(&S,&pt); 40 pt = NULL; 41 } 42 } 43 } 44 }
同样以这个算法为基础，我们便可以衍生出许多其他的算法
所有叶子节点到根的路径
1 void LeafPath( BiNode *BT,BiNode *SBT ) //SBT为传入的树的根节点，便于后面寻找路径 2 { 3 if ( BT ) 4 { 5 if ( BT->lChild == NULL && BT->rChild == NULL ) 6 { 7 BiNode *temp = SBT; 8 BiNodePath(temp,BT->data); 9 } 10 LeafPath(BT->lChild,SBT); 11 LeafPath(BT->rChild,SBT); 12 } 13 }
最长路径
1 void LongestPath ( BiNode *BT,BiNode *SBT,int height )//SBT为传入的树的根节点，便于后面寻找路径 2 { 3 if ( BT ) 4 { 5 if ( BT->lChild == NULL && BT->rChild == NULL ) 6 { 7 BiNode *temp = SBT; 8 if ( height == 0 ) 9 { 10 height = DepthTree(temp); 11 } 12 int j = BiNodePath(temp,BT->data); 13 if ( height == j ) 14 { 15 cout<<"此为最长路径"<<j<<endl; 16 } 17 } 18 LongestPath(BT->lChild,SBT,height); 19 LongestPath(BT->rChild,SBT,height); 20 } 21 }
以上便是以递归遍历和非递归遍历为首的一套树的相关函数
除此之外，还有许多其他的函数，他们也是上面各种函数的一种拓展
1、层次遍历
所谓层次遍历，就是逐层输出树的节点值，这里要用到队列，前面的无论是先序，中序，还是后序，都是有一种规律在约束着，先左后右，注定右面的要先入栈，但却无法输出，但队列不同，他满足先进先出，根节点输出后，便访问下面的两个节点，先访问，就先输出，这也便是层次输出
1 void LevelOrderTraverse( BiNode *BT ) 2 { 3 if ( BT == NULL ) 4 { 5 cout<<"空树！"<<endl; 6 return; 7 } 8 seqQueue Q; 9 initialQueue(&Q); 10 inQueue(&Q,BT); 11 BiNode *t = BT; 12 BiNode *last,*nlast; //这里的last和nlast是为了使输出的时候逐行输出 13 last = nlast = t; 14 while ( !queueEmpty(Q) ) 15 { 16 queueFront(Q,&t); 17 cout<<t->data<<" "; 18 if ( t->lChild != NULL ) 19 { 20 inQueue(&Q,t->lChild); 21 nlast = t->lChild; 22 } 23 if ( t->rChild != NULL ) 24 { 25 inQueue(&Q,t->rChild); 26 nlast = t->rChild; 27 } 28 outQueue(&Q); 29 30 if ( last == t ) 31 { 32 cout<<endl; 33 last = nlast; 34 } 35 } 36 }
2、顺序表和链表的相互转化
void ArrayToBiTree ( BiNode *&BT,char str[],int i ) /*为了防止访问未知元素，必须提前*/ { /*将所有元素初始化*/ if ( str[i] != '/' && i <= strlen(str) )//这里的str必须提前进行初始化即str[MAXLEN] = "";（所有的MAXLEN个元素都为\0) { BT = new BiNode; BT->data = str[i]; BT->lChild = NULL; BT->rChild = NULL; ArrayToBiTree (BT->lChild,str,2*i); ArrayToBiTree (BT->rChild,str,2*i+1); } } void BiTreeToArray ( BiNode *BT,char str[],int i ) { if (BT) { str[i] = BT->data; BiTreeToArray (BT->lChild,str,2*i); BiTreeToArray (BT->rChild,str,2*i+1); } else { str[i] = '/'; } int j = 1; str[0] = '/'; while ( j < (i-1)/2 ) //将中间空缺的元素补齐 { if ( str[j] == '\0') { str[j] = '/'; } j++; } }
更多精彩
