树的概念

树的定义

树的性质

树中的结点数等于所有结点的度数加1。度为m的树中第i层上至多有m^i-1个结点。高度为h的m叉树至多有(m^h-1)/(m-1)个结点。具有n个结点的m叉树的最小高度为[log_m(n(m-1)+1)] (向上取整)总结点数 = n₀+n₁+ … +n_m 。总分支数 = 1n₁+2n₂+3n₃+ … +mn_m 。总结点数 = 总分支数 + 1 。

二叉树的概念

二叉树的定义

每个结点至多有两棵子树，并且两棵子树有左右之分，次序不能颠倒。与度为2的有序树的区别：特殊的二叉树： 满二叉树：高度为h，含有2^h-1个结点的二叉树。完全二叉树：高度为h、有n个结点的二叉树，每个结点都与高度为h的满二叉树中编号1~n的结点一一对应。二叉排序树：左子树上的所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字的二叉树。平衡二叉树：树上任意结点的左子树和右子树的深度之差不超过1。

二叉树的性质

非空二叉树上叶子结点数等于度为2的结点数加1，即n₀=n₂+1（结点数为n，则边数为n-1） 。非空二叉树上第k层上之多有2^k-1个结点 。高度为h的二叉树至多有2^h-1个结点。完全二叉树的性质： 当i>1时，结点i的双亲编号为[i/2] (向下取整)，即当i为偶数时，双亲编号为i/2(结点i是双亲的左孩子)；当i为奇数时，双亲编号为(i-1)/2(结点i是双亲的右孩子)。当2i<=n时，结点i的左孩子编号为2i，否则无左孩子；当2i+1<=n时，结点i的右孩子的编号为2i+1，否则无右孩子。结点i所在的层次为[log₂i]+1(向下取整)。 -具有n个结点的完全二叉树的高度为[log₂(n+1)] (向上取整)或[log₂n]+1 (向下取整) 。

二叉树的存储结构

顺序存储结构

#define MaxSize 1000 struct TreeNode{ ElemType value; bool isEmpty; }; TreeNode t[MaxSize]; for(int i=0; i<MaxSize; i++){ t[i].isEmpty = true; }

链式存储结构

typedef struct BiTNode { ElemType data; struct BitNode *lchild, *rchild; }BiTNode,*BiTree; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; // 定义一颗空树 BiTree root = NULL;

二叉树的遍历

基本操作

// 插入根节点 root = (BiTree)malloc(sizeof(BiTNode)); root->data = {1}; root->lchild = NULL; root->rchild = NULL; // 插入新结点 BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode)); p->data = {2}; p->lchild = NULL; p->rchild = NULL; root->lchild = p; // 访问树中的元素 void visit(BiTNode *p){ printf("%c", p->data); }

遍历操作

// 先序遍历(递归) void PreOrder(BiTree T){ if(T!=NULL){ visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } } // 先序遍历(非递归) void PreOrder(BiTree T){ InitStack(S);// 初始化栈S BiTree p=T;// p为遍历指针 while(p || !IsEmpty(S)){ if(p){// 指针向左 visit(p);// 访问该结点 Push(S, p);// 结点入栈 p = p->lchild;// 指针向左 } else{ Pop(S,p);// 出栈，转向出栈结点的右子树 p = p->rchild;// 指针指向当前结点右孩子 } } } // 中序遍历(递归) void InOrder(BiTree T){ if(T!=NULL){ InOrder(T->lchild); visit(T); InOrder(T->rchild); } } // 中序遍历(非递归) void InOrderNonRecursion(BiTree T){ InitStack(S);// 初始化栈S BiTree p = T;// p为遍历指针 while(p || !IsEmpty(S)){ if(p){// 若存在左结点，一直入栈 Push(S, p); p = p->lchild; } else{// 直到无左结点，出栈并访问栈中元素 Pop(S, p); visit(p); p = p->rchild;// 指针向右走，至当前结点的右孩子，继续进入下轮循环 } } } // 后序遍历 void PostOrder(BiTree T){ if(T!=NULL){ PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } } // 后序遍历(非递归) void PostOrderNonRecursion(BiTree T){ InitStack(S); BiTree p = T; BiTree r = NULL; while(p || !Empty){ if(p){ Push(S, p); p = p->lchild; } else{ GetTop(S, p);// 获取栈顶元素 if(p->rchild && p->rchild!=r){//若右子树存在，且未被访问过 p = p->rchild; Push(S, p); p = p->lchild; } else{ Pop(S, p); visit(p); r = p;// 记录最近访问过的结点 p=NULL;// 结点访问完成后，重置p指针 } } } } // 层序遍历 void LevelOrder(BiTree T){ LinkQueue Q; InitQueue(Q);// 初始化辅助队列 BiTree p; EnQueue(Q,T);// 将根结点入队 while (!isEmpty(Q))// 队列不空则循环 { DeQueue(Q,p);// 队头结点出队 visit(p);// 访问出队结点 if(p->lchild!=NULL) EnQueue(Q, p->lchild);// 左孩子入队 if(p->rchild!=NULL) EnQueue(Q, p->rchild);// 右孩子入队 } } /* 遍历操作的应用 */ // 求树的深度 int treeDepth(BiTree T){ if(T = NULL) return 0; else{ int l = treeDepth(T->lchild); int r = treeDepth(T->rchild); return l>r ? l+1 : r+1; } }

线索二叉树

/* 树的线索化操作 */ // 线索二叉树结点 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag;// 左、右线索标志位 }ThreadNode, *ThreadTree; /* 中序遍历（暴力算法） */ // 遍历函数 void InOrder(BiTree T){ if(T!=NULL){ InOrder(T->lchild);// 递归遍历左子树 visit(T);// 访问根结点 InOrder(T->rchild);// 递归遍历右子树 } } // 访问结点 void visit(BiTNode *q){ if(q=p)//当前访问结点刚好是结点p final = pre;//找到p的前驱 else pre = q;//pre指向当前访问结点 } // 辅助全局变量，用于查找结点p的前驱 BiTNode *p;// p指向目标结点 BiTNode *pre = NULL;// 指向当前访问结点的前驱 BiTNode *final = NULL;// 用于记录最终结果 /* 线索化遍历树操作 */ /* 中序线索化 */ // 全局变量pre，指向当前访问结点的前驱 ThreadNode *pre=NULL; //中序遍历二叉树，边遍历边线索化 void Inthread(ThreadTree T){ if(T!=NULL){ Inthread(T->lchild); visit(T); Inthread(T->rchild); } } void visit(ThreadNode *q){ if(q->lchild==NULL){// 左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if(pre!=NULL&&pre->rchild==NULL){ pre->rchild = q;//建立前驱结点的后继线索 pre->rtag = 1; } pre = q; } //中序线索化二叉树T void CreateInThread(ThreadTree T){ pre = NULL; if(T!=NULL){ InThread(T); if(pre->rchild == NULL) pre->rtag=1; } } //中序线索化（课本） void InThread(ThreadTree p, ThreadTree &pre){ if(p!=NULL){ InThread(p->lchild, pre);// 递归，线索化左子树 if(p->lchild==NULL){ // 左子树为空，建立前驱线索 p->lchild = pre; p->ltag = 1; } if(pre!=NULL&&pre->rchild==NULL){ pre->rchild = p;// 建立前驱节点的后继线索 pre->rtag = 1; } pre = p;//标记当前结点成为刚刚访问过的结点 InThread(p->rchild, pre);//递归，线索化右子树 } } //中序线索化二叉树T void CreateInThread(ThreadTree T){ ThreadTree pre = NULL; if(T!=NULL){ InThread(T, pre); pre->rchild = NULL; pre->rtag = 1; } } /* 先序线索化 */ // 全局变量 pre， 指向当前访问结点的前驱 ThreadNode *pre = NULL; // 先序线索化二叉树T void CreatePreThread(ThreadTree T){ pre = NULL;// pre初始化为NULL if(T!=NULL){//非空二叉树才能线索化 PreThread(T);//先序线索化二叉树 if(pre->rchild==NULL) pre->rtag = 1;//处理遍历的最后一个结点 } } // 先序遍历二叉树，边遍历边线索化 void PreThread(ThreadTree T){ if(T! = NULL){ visit(T); if(T->rtag == 0)// lchild不是前驱线索 PreThread(T->rchild); } } void visit(ThreadNode *q){ if(q->lchild == NULL){// 左子树为空，建立前驱线索 q->lchild = pre; q->rtag = 1; } if(pre!=NULL && pre->rchild==NULL){ pre->rchild = q;// 建立前驱结点的后继线索 pre->rtag = 1; } pre = q; } // 先序线索化（课本） void PreThread(ThreadTree p, ThreadTree &pre){ if(p!=NULL){ if(p->lchild == NULL){ p->lchild = pre; p->ltag = 1; } if(pre!=NULL && pre->rchild==NULL){ pre->rchild = p; pre->rtag = 1; } pre = p; if(p->ltag = 0) InThread(p->rchild, pre); Inthread(p->rchild, pre); } } // 先序线索胡二叉树T void CreateThread(ThreadTree T){ ThreadTree pre = NULL; if(T!=NULL){ PreThread(T, pre); if(pre->rchild==NULL) pre->rtag = 1; } } /* 后序线索化 */ //全局变量pre， 指向当前访问结点 ThreadNode *pre=NULL; //后续线索化二叉树T void CreatePostThread(ThreadTree T){ pre = NULL; if(T!=NULL){ InThread(T); if(pre->rchild==NULL) pre->rtag = 1; } } // 后续线索化二叉树，边遍历边线索化 void PostThread(ThreadTree T){ if(T!==NULL){ PostThread(T->lchild); PostThread(T->rchild); visit(T); } } void visit(ThreadNode *q){ if(q->lchild == NULL){ q->lchild=pre; q->rtag=1; } if(pre!=NULL&&pre->rchild==NULL){ pre->rchild=q; pre->rtag=1; } pre = q; } // 后序线索化（课本） void PostThread(ThreadTree p, ThreadTree &pre){ if(p!=NULL){ InThread(p->lchild, pre); InThread(p->rchild, pre); if(p->lchild==NULL){ p->lchild = pre; p->ltag = 1; } if(pre!=NULL && pre->rchild==NULL){ pre->rchild = p; pre->rtag = 1; } pre = p; } } // 后序线索胡二叉树T void CreatePostThread(ThreadTree T){ ThreadTree pre=NULL; if(T!=NULL){ PostThread(T, pre); if(pre->rchild==NULL) pre->rtag = 1; } }