树与二叉树

技术分享 9个月前 (05-03) 0 999+

关注

树

定义

结点的度数其实就是这个结点下连的线，比如：A的度 = AB+AC+AD = 3

树的度就是MAX(结点的度)

叶子结点就是没后代的结点

树的基本性质

所有结点数 = 所有结点的度数之和 + 1(这个1也就是根节点)

习题：

所有节点数 =4 + 20 * 4 + 10 * 3 + 1 * 2 + 10 * 1 + 1 = 123

123 - 20 - 10 - 1 - 10 = 82
所有结点数 = 不同度的节点数之和

假设所有节点数为n，度0～4的个数为n0～n4，则n = n0 + n1 + n2 + n3 + n4
第一层m^{0，第二层m}1，第i层m^(i-1)
等比数列求和公式

二叉树

定义

就是每个分支只有二叉的树，子树有左右之分

基本形态

二叉树的性质

这是某一层的最多结点数

这是整个二叉树的最多结点数

n0 = n2 + 1

对于任何非空的二叉树，度0(叶子)和度2的结点数为n0、n2，那么 n0 = n2 + 1
n2 = 0 的时候，n0 = 1，每把一个叶子画一个二叉，n2++，n0++

n = 1 * n1 + 2 * n2 + 1
n = n0 + n1 + n2
解得，n0 = n2 + 1

特殊二叉树

满二叉树

完全二叉树

没有左子树，不能有右子树，上一层没铺满，不能有下一层

判断完全二叉树

不是

是

完全二叉树的性质

1.2.3.就是二叉树的性质

如果总结点数-1是奇数，说明有一个度为1的结点

习题

叶子结点出现在最后2层，这里求的是最多，所以最后一层是第7层

第6层最多的结点数=2^(6-1)=32

第6层的非叶子结点=32-8=24

第7层的最多结点数= 24*2 = 48

前6层的最多结点数=2^6 - 1 = 63

总计=63+48 = 111，选c

n = n0+n1+n2

n0=n2+1

所以，n = 2n2 + n1 + 1

而768-1是奇数，所以有一个度为1的结点，即n1 = 1

解得 n2 = 383

n0 = n2 + 1 = 384，选c

n=n0+n1+n2

n1 = 0

n0=n2+1

所以，n = 2n0 - 1 = 2k -1 ，选a

二叉树的实现

顺序结构实现——除了满二叉树和完全二叉树的其他场景比较浪费空间

链式结构实现

//链式结构实现 typedef char ElemType;  //树结点 typedef struct TreeNode {     ElemType data;     TreeNode *lchild;     TreeNode *rchild; } TreeNode;  //用树结点指针表示二叉树 typedef TreeNode* BiTree;

创建二叉树

二级指针概念：

指针pp 存的是指针p的地址

那么*pp 就是得到p的地址，**pp就是得到p的值

char str[] = "ABDH#K###E##CFI###G#J##"; int idx = 0;  //创建二叉树 // T是二级指针(BiTree**) //  *T就是对二叉树的结点进行操作 void createTree(BiTree *T) { 	ElemType ch; 	ch = str[idx++]; 	if (ch == '#') 	{ 		*T = NULL; 	} 	else 	{ 		*T = (BiTree)malloc(sizeof(TreeNode)); 		(*T)->data = ch; 		createTree(& ( (*T)->lchild ) ); 		createTree(& ( (*T)->rchild ) ); 	} }

遍历

前序遍历

NLR / NRL （根-左-右）/（根-右-左）

下面都以先左的遍历为例

从根节点开始，先从左子结点开始一层层向下递(进栈)并打印，如果左子节点是空就归(出栈)，然后开始递右结点，进行如上同样操作，并向上一层层归，归到根节点后，对根节点的右子节点进行同样的操作。

具体动画演示可以看《数据结构（C 语言描述）》的55:00左右进度条

//前序遍历 void preOrder(BiTree T){     if(T == NULL) return;     printf("%c ", T->data);     //递归子树     preOrder(T->lchild);     preOrder(T->rchild); }

中序遍历

LNR / RNL

从根节点开始，先从左子结点开始一层层向下递(进栈)，如果左子节点是空就归(出栈)并打印，然后开始递右结点，进行如上同样操作，并向上一层层归，归到根节点后，对根节点的右子节点进行同样的操作。

//中序遍历 void inOrder(BiTree T){     if(T == NULL) return;     inOrder(T->lchild);     printf("%c ", T->data);     inOrder(T->rchild); }

后序遍历

LRN / RLN

从根节点开始，先从左子结点开始一层层向下递(进栈)，如果左子节点是空就归(出栈)，然后开始递右结点，进行如上同样操作，在右结点空的时候归(出栈)并打印，并向上一层层归，归到根节点后，对根节点的右子节点进行同样的操作。

//后序遍历 void postOrder(BiTree T){     if(T == NULL) return;     postOrder(T->lchild);     postOrder(T->rchild);     printf("%c ", T->data); }

习题

前：ABDHEICFGJK

中：HDBEIAFCJGK

后：HDIEBFJKGCA

前：ABDEGHCFI

中：DBGEHAFIC

后：DGHEBIFCA

先画出二叉树：

	 A 	/         B   D       /   /         C   E   F

后：CBEFDA

二叉树遍历性质

习题

先右后左的中序遍历，RNL，选d

ADB都能画出来，所以选c

	1                     2                         3

选b

(这题不要多选，一般情况只需要考虑先左就行)

	 f        /          c     g           /         a d        /          e     b

选b

因为对于顺序结构来说，没有的子树节点需要填NULL，所以相当于是高度为5的满二叉树需要的存储单元，也就是二叉树的最大结点数公式，即2^5 - 1 = 31

线索二叉树

目标：构建一个双向循环链表

会出现空余空间不够用的情况吗？

不会，n个节点有n+1个空

代码实现

typedef char ElemType;  typedef struct ThreadNode {     ElemType data;     struct ThreadNode *lchild, *rchild;     int ltag, rtag; } ThreadNode;  typedef ThreadNode *ThreadTree;

ltag：0 指向lchild，1指向前驱

rtag：0 指向rchild，1指向后继

中序遍历线索化

#include <stdio.h> #include <stdlib.h>  typedef char ElemType;  typedef struct ThreadNode {     ElemType data;     struct ThreadNode *lchild, *rchild;     int ltag, rtag; } ThreadNode;  typedef ThreadNode *ThreadTree;  char str[] = "ABDH##I##EJ###CF##G##"; int idx = 0;  ThreadTree prev;  //创建二叉树 void createTree(ThreadTree *T){     ElemType ch; 	ch = str[idx++]; 	if (ch == '#') 	{ 		*T = NULL; 	} 	else 	{ 		*T = (ThreadTree)malloc(sizeof(ThreadNode)); 		(*T)->data = ch;  		createTree(& ( (*T)->lchild ) );         //lchild有左孩子，则ltag=0         if( (*T)->lchild != NULL){             (*T)->ltag = 0;         }          createTree(& ( (*T)->rchild ) );         if( (*T)->rchild != NULL){             (*T)->rtag = 0;         } 	} }  //线索化——加前驱后继的逻辑 void threading(ThreadTree T){     if(T != NULL){         //一直往左边遍历         threading(T->lchild);         //当前结点的左孩子为空，当前结点的左孩子设定为指向前驱         if(T->lchild == NULL){             T->ltag = 1;             T->lchild = prev;         }         //前驱结点的右孩子为空，前驱结点的右孩子设定为指向当前结点(当前结点就是前驱节点的后继)         if(prev->rchild == NULL){             prev->rtag = 1;             prev->rchild = T;         }         //更新prev到根节点，往右边遍历         prev = T;         threading(T->rchild);     } }  //中序遍历线索化 void inOrderThreading(ThreadTree *head ,ThreadTree T){     *head = (ThreadTree)malloc(sizeof(ThreadNode));     (*head)->ltag = 0;     (*head)->rtag = 1;     (*head)->rchild = (*head);     if(T == NULL){         (*head)->lchild = (*head);     }     else{         //头节点的左孩子指向树的根节点         (*head)->lchild = T;          //prev：上一个访问的节点是头节点         prev = (*head);          //加前驱后继的逻辑         threading(T);          //最后一个节点的右孩子指向头节点         prev->rtag = 1;         prev->rchild = (*head);          //头节点的右孩子指向遍历的最后一个节点         (*head)->rchild = prev;      } }  //基于线索的中序遍历 void inOrder(ThreadTree T){     ThreadTree current = T->lchild;     while(current != T){         //如果当前节点有左孩子，则一直往左边遍历         //没有左孩子，则退出当前循环 输出当前节点         while(current->ltag == 0){             current = current->lchild;         }         printf("%c",current->data);         //往右边遍历, 直到右孩子不为空且当前的右孩子是头节点         while(current->rtag == 1 && current->rchild != T){             current = current->rchild;             printf("%c",current->data);         }         current = current->rchild;     }     printf("n"); }  int main(){     ThreadTree head;     ThreadTree T;     createTree(&T);     inOrderThreading(&head,T);     inOrder(head);     return 0; }