说在前面 本文是王道数据结构P191的10个算法例题归纳,二叉树的存储结构为二叉链表。
1 2 3 4 5 typedef struct BiTNode { ElemType data; struct BiTNode *lchild ,*rchild ; }BiTNode,*BiTree;
统计二叉树中度为1的结点个数 1 2 3 4 5 6 7 8 9 10 11 int NodeCount1 ( BiTree T) {if (T==NULL ) { return 0 ; } if (T->lchild==NULL &&T->rchild!=NULL ||T->rchild==NULL &&T->lchild!=NULL ){ return 1 +NodeCount1(T->lchild)+NodeCount1(T->rchild); } return NodeCount1(T->lchild)+NodeCount1(T->rchild);}
给定一个二叉树,当根仅具有一个孩子时,代表根度为1,统计一次并递归寻找子树度为1的根;当根有两个孩子,不统计递归寻找子树度为1的根。
也可以用非递归方法,使用队列层次遍历。
统计二叉树中度为2的结点个数 1 2 3 4 5 6 7 8 9 10 11 int NodeCount2 ( BiTree T) {if (T==NULL ) { return 0 ; } if (T->lchild==NULL &&T->rchild!=NULL ||T->rchild==NULL &&T->lchild!=NULL ){ return NodeCount2(T->lchild)+NodeCount2(T->rchild); } return 1 +NodeCount2(T->lchild)+NodeCount2(T->rchild);}
统计二叉树中度为0的结点个数 1 2 3 4 5 6 7 8 9 10 11 int NodeCount0 ( BiTree T) {if (T==NULL ) { return 0 ; } if (T->lchild==NULL &&T->rchild==NULL ){ return 1 ; } return NodeCount0(T->lchild)+NodeCount0(T->rchild);}
统计二叉树的高度 1 2 3 4 5 6 7 8 9 10 11 int Height (BiTree T) { if (T == NULL ) return 0 ; int ldep = Height(T->lchild); int rdep = Height(T->rchild); if (ldep > rdep) return ldep + 1 ; else return rdep + 1 ; }
统计二叉树的宽度 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void LevelWidth (BiTree T, int a[], int h) { if (T!=NULL ) { a[h] += 1 ; LevelWidth(T->lchild, a, h + 1 ); LevelWidth(T->rchild, a, h + 1 ); } } int Width (BiTree T) { int a[MaxSize + 1 ], h = 1 ; for (int i = 0 ; i <= MaxSize; i++) a[i] = 0 ; LevelWidth(T, a, h); int wid = a[0 ]; for (int i = 1 ; i <= MaxSize; i++) if (a[i] > wid) wid = a[i]; return wid; }
从二叉树中删去所有的叶结点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void Del_0 (BiTree T) { BiTNode *p = T; if ((p->lchild ==NULL && p->rchild ==NULL )|| p ==NULL ) { free (p); return ; } else if (p->lchild->lchild ==NULL && p->lchild->rchlid ==NULL ) { free (p->lchild); p->lchild =NULL ; } else if (p->rchild->lchild ==NULL && p->rchild->rchlid ==NULL ) { free (p->rchild); p->rchild =NULL ; } Del_0(T->lchild); Del_0(T->rchild); }
首先叶子是指左右孩子都没有的结点。
注意此代码为递归,只会向内层深⼊,所以删除完叶⼦结点,使原分⽀结点变为叶⼦结点,但不会再继续删除。
计算指定结点*p所在的层次 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int GetLevel (BiTree T, BiTNode *p) { if (T == NULL ) return 0 ; if (T == p) return 1 ; int depl = GetLevel(T->lchild, p); int depr = GetLevel(T->rchild, p); if (depl || depr) { if (depl > depr) return 1 + depl; else return 1 + depr; } return 0 ; }
计算二叉树中各结点中最大元素的值 1 2 3 4 5 6 7 8 9 int Get_Max (BiTree T) { if (T == NULL ) return 0 ; int maxl = Get_Max(T->lchild); int maxr = Get_Max(T->rchild); int max = maxl > maxr ? maxl : maxr; return max > T->data ? max : T->data; }
交换二叉树中每个结点的两个子女 1 2 3 4 5 6 7 8 9 10 11 12 void Exc (BiTree T) { if (T->lchild != NULL ) Exc(T->lchild); if (T->rchild != NULL ) Exc(T->rchild); BiTNode *p; p = T->lchild; T->lchild = T->rchild; T->rchild = p; }
以先序次序输出一颗二叉树中所有结点 1 2 3 4 5 6 7 8 9 void PreAndLevel (BiTree T, int i) { if (T != NULL ) { printf ("data=%d,level=%d" , T->data, i); PreAndLevel(T->lchild, i + 1 ); PreAndLevel(T->rchild, i + 1 ); } }
参考 部分题解答源自 霸道总裁爱上网的博客_CSDN博客-c++,算法,安卓领域博主