2019 September 04 CPP基础

C/CPP与数据结构-第三节 树（一）

树

  1. 树的基本知识
    1. 树的定义：
      1. 由一个或多个（n>=0）节点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m（m>=0）个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是一棵树，被称作这个根的子树。
      2. 注意：过去许多书籍中都定义n>=1,曾经有空树不是树的说法，但现在定义已改。
      3. 树的定义具有递归性，即树中还有数。

    2. 常见的术语：

       根： 即根结点(没有前驱)
 叶子： 即终端结点(没有后继)
 森林： 指m棵不相交的树的集合(例如删除A后的子树个数)
 有序树： 结点各子树从左至右有序，不能互换（左为第一）
 无序树： 结点各子树可互换位置。
 双亲： 即上层的那个结点(直接前驱) parent
 孩子： 即下层结点的子树 (直接后继) child
 兄弟： 同一双亲下的同层结点（孩子之间互称兄弟）sibling
 堂兄弟：即双亲位于同一层的结点（但并非同一双亲）cousin 
 祖先： 即从根到该结点所经分支的所有结点
 子孙： 即该结点下层子树中的任一结点
 结点： 即树的数据元素
 结点的度： 结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）
 结点的层次： 从根到该结点的层数（根结点算第一层）
 终端结点： 即度为0的结点，即叶子
 分支结点： 除树根以外的结点（也称为内部结点）
 树的度： 所有结点度中的最大值（Max{各结点的度}）
 树的深度(或高度)： 指所有结点中最大的层数（Max{各结点的层次}）
    3. 树的表示法有几种：
      1. 图形表示法
      2. 嵌套集合表示法
      3. 广义表表示法 : ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
      4. 目录表示法
      5. 左孩子－右兄弟表示法
        1. 就是将一棵树转化为二叉树

        图4

    4. 树的逻辑结构
      1. (特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。
    5. 树的存储结构
      1. 树是非线性结构，该怎样存储？
        1. 仍然有顺序存储、链式存储等方式。
      2. 树的顺序存储方案应该怎样制定？
        1. 可规定为：从上至下、从左至右将树的结点依次存入内存。
        2. 重大缺陷：复原困难（不能唯一复原就没有实用价值）。
      3. 树的链式存储方案应该怎样制定？
        1. 可用多重链表：一个前趋指针，n个后继指针。
          1. 细节问题：树中结点的结构类型样式该如何设计？
          2. 即应该设计成“等长”还是“不等长”？
        2. 缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。
      4. 计算机如何实现各种不同进制的运算？
        1. 实现思路：先研究最简单、最有规律的二进制运算规律，然后设法把各种不同进制的运算转化二进制运算。
      5. 树的存储可否借鉴这种思路呢？
        1. 解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为这种简单的树

二叉树

  1. 为何要重点研究每结点最多只有两个 “叉” 的树？
    1. 二叉树的结构最简单，规律性最强；
    2. 可以证明，所有树都能转为唯一对应的二叉树，不失一般性
  2. 二叉树的定义：
    1. 定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。
    2. 逻辑结构：  一对二（1：2）
    3. 基本特征:
      1. 每个结点最多只有两棵子树（不存在度大于2的结点）；
      2. 左子树和右子树次序不能颠倒（有序树）。

    4. 问：具有3个结点的二叉树可能有几种不同形态？（5种） 普通树呢？（2种） 图4

      1. 二叉树5种：
        1. 2、3、4、5有什么不同呢？
        2. 左子树/右子树的不同
      2. 普通树2种：
        1. 没有左子树、右子树的概念，因此2、3、4、5相同，只有2种
  3. 二叉树的性质
    1. 性质1：在二叉树的第i层上至多有2(i次方)-1个结点（i>0）。
    2. 性质2：深度为k的二叉树至多有2(k次方)-1个结点（k>0）。
    3. 性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）
      1. 即 叶子节点数= 度数为2的节点数 +1；
      2. 度数为2的节点：就是这个节点有2个子树
    4. 满二叉树：一棵深度为k 且有2(k次方) -1个结点的二叉树。（特点：每层都“充满”了结点）
    5. 完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。特点如下：
      1. k-1层一定是满二叉树
      2. 最后一层：右边有叶子左边一定右叶子。就是靠左
    6. 性质4：具有n个结点的完全二叉树的深度必为[log(2底数)n]＋1
      1. 解释：[]取下值的意思，2的n次方 = 13，那么n一定是3<n<4,那么此时n就去3，这就是向下取值。那么结果：3+1 = 4；

    7. 性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。

      图4

  4. 二叉树的存储
    1. 顺序存储接口
      1. 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。
      2. 顺序存储后能否复原成唯一对应的二叉树形状？
        1. 若是完全/满二叉树则可以做到唯一复原。
        2. 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）
        3. 例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。
      3. 讨论：不是完全二叉树怎么办？
        1. 一律转为完全二叉树！
        2. 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。
        3. 缺点：浪费空间；插入、删除不便    
    2. 二叉树的链式存储
      1. 那么二叉树的链表还如何表示呢？
        1. 二叉链表示法
          1. 一个结构体分为：左孩子指针、数据域、右孩子指针
          2. 左孩子指针指向左孩子结构体，右孩子指针指向右孩子结构体

          3. 二叉链结点数据类型定义：

             typedef struct BiTNode
 {
 	int data;
 	struct BiTNode *lchild, *rchild;
 }BiTNode, *BiTree;
        2. 三叉链表示法：
          1. 如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表
          2. 一个结构体分为：左孩子指针、数据域、右孩子指针、双亲指针

          3. 三叉链结点数据类型定义：

             typedef struct TriTNode 
 {
 	int data;
 	//左右孩子指针
 	struct TriTNode *lchild, *rchild;
 	//双亲指针
 	struct TriTNode *parent;
 }TriTNode, *TriTree;

      2. 树的另一种表示方法：双亲链表法

         //双亲链表
 #define MAX_TREE_SIZE 100
 typedef struct BPTNode
 {
 	int data;
 	int parentPosition; //指向双亲的指针 //数组下标
 	char LRTag; //左右孩子标志域，表示当前结点为双亲的左或右孩子
 }BPTNode;
            
 typedef struct BPTree
 {
 	BPTNode nodes[100]; //因为节点之间是分散的，需要把节点存储到数组中
 	int num_node;  //节点数目
 	int root; //根结点的位置 //注意此域存储的是父亲节点在数组的下标
 }BPTree;
        1. 将结点全部放到一个数组中nodes
        2. 每个结点保存与父子结点的关系
         //A
 BPTree myTree; //
 myTree.root = 0; // 数组的0号位置，是根节点
 myTree.nodes[0].data = 'A';
            
 //B
 myTree.nodes[1].data = 'B';
 myTree.nodes[1].parentPosition = 0; //双亲数组下标
 myTree.nodes[1].LRTag = 1;  //A的左子
            
 //C
 myTree.nodes[2].data = 'C';
 myTree.nodes[2].parentPosition = 0; //双亲数组下标
 myTree.nodes[2].LRTag = 2; //A的右子
  5. 遍历二叉树和线索二叉树
    1. 遍历二叉树（Traversing Binary Tree）
      1. 遍历规则
        1. 二叉树由根、左子树、右子树构成，定义为D、 L、R
      2. D、 L、R的组合定义了六种可能的遍历方案：
        1. LDR,   LRD,   DLR,   DRL,   RDL,   RLD
      3. 若限定先左后右，则有三种实现方案：
        1. DLR : 先 (根)序遍历 ,即先根再左再右
          1. 先根，然后遍历根的左子树，左子树若还有子树接着遍历，知道根的左子树全部遍历完，再遍历右子树
        2. LDR : 中 (根)序遍历 ,即先左再根再右
          1. 从根节点A开始，找到根节点的左子树节点B，然后查看节点B是否有左子树，若有则县访问B节点的左子树，就这样一直下去。。。
        3. LRD : 后(根)序遍历 ,即先左再右再根
          1. 同理
      4. 举例：树：A(B(D,E),C)
        1. 先序遍历：A、B、D、E、C
          1. 先访问A，A的左子树B,B的左子树D，D没有左子树，所以访问B的右子树E,在访问A的右子树C
        2. 中序遍历：D、B、E、A、C
          1. 先从A节点开始，找A的左子树B，到B节点，先找B的左子树D，D节点没有左子树，因此就访问D,然后访问D的双亲B,然后访问B的右子树E，然后访问B的双亲A，然后再访问A的右子树。
        3. 后序遍历：D、E、B、C、A
          1. 先从A节点开始，找A节点的左子树B，到B节点，先找B的左子树D，D节点没有左子树，因此就访问D,然后访问B的右子树E，接着访问B，在访问A的右子树C,最后访问跟节点A

          图4

  6. 遍历算法实现：

    1. 先序遍历

       DLR(NODE *root ){  
     if (root) {//非空二叉树
         printf(“%d”,root->data); //访问D
         DLR(root->lchild); //递归遍历左子树
         DLR(root->rchild); //递归遍历右子树
     }
 	}

    2. 中序遍历

       LDR(NODE *root){ 
     if(root !=NULL){  
           LDR(root->lchild);
           printf(“%d”,root->data);
           LDR(root->rchild); 
     } 
 }

    3. 后序遍历

       LRD (NODE *root){
     if(root !=NULL) {
         LRD(root->lchild);
         LRD(root->rchild);
         printf(“%d”,root->data); 
      }
 }

  7. 代码示例：

     #define _CRT_SECURE_NO_WARNINGS
 #include<stdlib.h>
 #include<string.h>
 #include<stdio.h>
    
 typedef struct BitNode
 {
 	int data;
 	struct BitNode *lchild, *rchild;
 } BitNode;
    
 typedef struct BitNode* BitTree;
    
    
 //先序遍历
 void preOrder(BitNode *T) {
 	if (T == NULL) return;
 	//先跟
 	printf("%d", T->data);
 	//再左
 	if (T->lchild != NULL) {
 		preOrder(T->lchild);
 	}
    
 	//再右
 	if (T->rchild != NULL) {
 		preOrder(T->rchild);
 	}
 }
    
 //中序遍历
 void inOrder(BitNode *T) {
 	if (T == NULL) return;
 	//先左
 	if (T->lchild != NULL) {
 		inOrder(T->lchild);
 	}
 	//再根
 	printf("%d", T->data);
 	//再右
 	if (T->rchild != NULL) {
 		inOrder(T->rchild);
 	}
 }
    
 //后序遍历
 void postOrder(BitNode *T) {
 	if (T == NULL) return;
 	//先左
 	if (T->lchild != NULL) {
 		postOrder(T->lchild);
 	}
 	//再右
 	if (T->rchild != NULL) {
 		postOrder(T->rchild);
 	}
 	//再根
 	printf("%d", T->data);
    	
 }
    
 //计算一颗树的所有叶子数量
 //思想：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。
 void countLeftNum(BitNode *T,int *sum) {
 	if (T == NULL) return;
 	if (T->lchild ==NULL && T->rchild == NULL)
 	{
 		(*sum)++;
 	}
 	//求左子树的叶子节点个数
 	countLeftNum(T->lchild,sum);
 	//求右子树
 	countLeftNum(T->rchild,sum);
 }
    
 //求树的深度
 //算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。
 //技巧：递归时应当从叶子开始向上计数，层深者保留。否则不易确定层数。
    
 int  depth(BitNode *T) {
 	if (T == NULL) return 0;
 	int leftDep = 0;
 	int rigDep = 0;
 	int deph = 0;
    
 	leftDep = depth(T->lchild);
 	rigDep = depth(T->rchild);
    
 	deph = 1 + (leftDep > rigDep ? leftDep : rigDep);
 	return deph;
 }
    
 //拷贝二叉树
 /*
 1. 先拷贝左子树
 2. 再拷贝右子树
 3. new一个结点，左指针指向左子树，右指针指向右子树
 4. 如果左子树是一棵树，递归1/2/3
 */
 BitNode *copyTree(BitNode *T) {
 	if (T == NULL) return NULL;
 	BitNode *newlChild = NULL;
 	BitNode *newrChild = NULL;
 	BitNode *newNode = NULL;
 	//先拷贝左子树
 	newlChild = copyTree(T->lchild);
 	//在拷贝右子树
 	newrChild = copyTree(T->rchild);
    
 	//创建新节点
 	newNode =(BitNode *)malloc(sizeof(BitNode));
 	if (newNode == NULL) return NULL;
    
 	//拷贝当前旧节点到新节点
 	newNode->data = T->data;
 	newNode->lchild = newlChild;
 	newNode->rchild = newrChild;
    	
 	return newNode;
 }
    
 /*
 		1
 	2		3
 4		5
 */
 void main() {
 	BitNode nodeA, nodeB, nodeC, nodeD, nodeE;
 	memset(&nodeA, 0, sizeof(BitNode));
 	memset(&nodeB, 0, sizeof(BitNode));
 	memset(&nodeC, 0, sizeof(BitNode));
 	memset(&nodeD, 0, sizeof(BitNode));
 	memset(&nodeE, 0, sizeof(BitNode));
    
 	nodeA.data = 1;
 	nodeB.data = 2;
 	nodeC.data = 3;
 	nodeD.data = 4;
 	nodeE.data = 5;
    
 	nodeA.lchild = &nodeB;
 	nodeA.rchild = &nodeC;
 	nodeB.lchild = &nodeD;
 	nodeC.lchild = &nodeE;
    
 	//拷贝二叉树
 	{
 		BitNode *newTree = copyTree(&nodeA);
 		printf("中序遍历新树 \n");
 		inOrder(newTree);
 	}
    
 	//树的高度
 	{
 		printf("\n树的高度：%d \n", depth(&nodeA));
 	}
    
 	//树的叶子总数
 	{
 		int s = 0;
 		countLeftNum(&nodeA,&s);
 		printf("叶子总数：%d", s);
 	}
    
 	//树的遍历
 	printf("\n先序遍历： ");
 	preOrder(&nodeA);
    
 	printf("\n中序遍历：");
 	inOrder(&nodeA);
    
 	printf("\n后序遍历：");
 	postOrder(&nodeA);
    
 	system("pause");
 	return;
 }

树的非递归遍历(中序遍历) 经典算法案例

中序 遍历的几种情况

分析1：什么时候访问根、什么时候访问左子树、什么访问右子树:
       当左子树为空或者左子树已经访问完毕以后，再访问根
       访问完毕根以后，再访问右子树。
分析2：非递归遍历树，访问结点时，为什么是栈，而不是其他模型（比如说是队列）。
      先走到的后访问、后走到的先访问，显然是栈结构
分析3：结点所有路径情况
    步骤1：
        如果结点有左子树，该结点入栈；
        如果结点没有左子树，访问该结点；
    步骤2：
        如果结点有右子树，重复步骤1；
        如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1
        如果栈为空，表示遍历结束。 
        
注意：入栈的结点表示，本身没有被访问过，同时右子树也没有被访问过。

分析4：有一个一直往左走入栈的操作，中序遍历的起点

  1. 树如下图：A(B(,C(D,)),E(,F(G(H,I),)))

    图4

  2. 按照上面算法分析：

     栈：stack   输出：P
 1. 经过A，A有左子树，则A入栈：stack（A）
 2. 经过B，B无左子树，则访问B：P(B)
 3. B有右子树，经过C,   C有左子树，则C入栈：stack（AC)
 4. 经过D，D无左子树，则访问D：P(BD)
 5. D节点没有右子树，栈回退，访问栈顶元素C,则P(BDC), stack(A)
 6. C无右子树，栈回退，访问栈顶元素A,则P(DBCA),stack()
 7. A有右子树，经过E,E无左子树，则访问E，则P(DBCAE)
 8. E有右子树，经过F，F有左子树，则F入栈: stacc(F)
 9. 经过G，G有左子树，则G入栈，stack（FG)
 10. 经过H，H无左子树，则访问H，P(DBCAEH)
 11. H无右子树，则栈回退，访问栈顶元素G, P(DBCAEHG) stack（F)
 12. G有右子树，经过I,I无左子树，则访问I,P(DBCAEHGI)
 13. I无右子树，则栈回退，访问栈顶元素F,P(DBCAEHGIF),stack（）
 14. F无右子树，而且栈为空，则遍历结束

  3. 代码举例：

     #include<iostream>
 #include<stack>
 using namespace std;
    
 typedef struct BitNode
 {
 	int data;
 	struct BitNode *lchild, *rchild;
 } BitNode;
    
 typedef struct BitNode* BitTree;
    
    
 //一直向左走，找到改树的起点
 BitNode * goFarLeft(BitNode *T, stack<BitNode *> &s) {
 	if (T == NULL) return NULL;
 	while (T->lchild != NULL) //一直检查是否有左子树
 	{
 		//有左子树则入栈
 		s.push(T);
 		//经过左子树在循环
 		T = T->lchild;
 	}
 	//返回没有左子树的节点T
 	return T;
 }
 //非递归中序遍历
 void myInorder(BitNode *T) {
  //定义栈
 	stack<BitNode *> s;
 	//一直往左走，找到中序遍历的起点
 	BitNode *t = goFarLeft(T, s);
 	while (t != NULL)
 	{
 		cout << t->data << endl;
 		//查看节点有右子树
 		if (t->rchild != NULL)
 		{
 			t = goFarLeft(t->rchild, s);
 		}
 		//没有右子树,且栈不为nil
 		else if (!s.empty())
 		{
 			//获取栈顶元素
 			t = s.top();
 			//出栈
 			s.pop();
 		}
 		else //没有右子树，且栈为nil
 		{
 			t = NULL;
 		}
 	}
 }
    
 void main() {
 	BitNode nodeA, nodeB, nodeC, nodeD, nodeE;
 	memset(&nodeA, 0, sizeof(BitNode));
 	memset(&nodeB, 0, sizeof(BitNode));
 	memset(&nodeC, 0, sizeof(BitNode));
 	memset(&nodeD, 0, sizeof(BitNode));
 	memset(&nodeE, 0, sizeof(BitNode));
    
 	nodeA.data = 1;
 	nodeB.data = 2;
 	nodeC.data = 3;
 	nodeD.data = 4;
 	nodeE.data = 5;
    
 	nodeA.lchild = &nodeB;
 	nodeA.rchild = &nodeC;
 	nodeB.lchild = &nodeD;
 	nodeC.lchild = &nodeE;
    
 	{
 		//非递归中序遍历
 		myInorder(&nodeA);
 	}
    
 	system("pause");
 	return;
 }

All content is licensed under CC BY-NC-SA

Buit with Jekyll and 3-Jekyll theme • Hosted on Github

Table of Contents