wordpress类似网站模板,移动做网站吗,中国风网页设计欣赏,有没有做淘宝的网站吗文章目录 三叉链表存储二叉树三叉链表的前序遍历#xff08;不使用栈#xff09;法一三叉链表的前序遍历#xff08;不使用栈#xff09;法二 一维数组存储二叉树一维数组存储二叉树的先序遍历 线索二叉树的建立真题演练 三叉链表存储二叉树
三叉链表结构体表示如下图所示… 文章目录 三叉链表存储二叉树三叉链表的前序遍历不使用栈法一三叉链表的前序遍历不使用栈法二 一维数组存储二叉树一维数组存储二叉树的先序遍历 线索二叉树的建立真题演练 三叉链表存储二叉树
三叉链表结构体表示如下图所示 构造三叉链表方式
typedef struct node{char data;struct node*parent,*lchild,*rchild;
}BTNode,*BiTree;
BTNode * creattree(BiTree t){ // 易错点树的引用char ch;cinch;if(ch#){tNULL;}else{t(BTNode*)malloc(sizeof(BTNode));// 易错点忘记重新创建新结点t-datach;t-parentNULL;t-lchildNULL;t-rchildNULL;if(t-lchild) t-lchild-parentt;if(t-rchild) t-rchild-parentt;creattree(t-lchild);creattree(t-rchild);}return t;
}另外设计一个填充函数函数功能是将所有结点的parent结点填充正确。
void FillParent(BiTree root){if(rootNULL) return;if(root-lchild) {root-lchild-parentroot;FillParent(root-lchild);}if(root-rchild){root-rchild-parentroot;FillParent(root-rchild);}
}三叉链表的前序遍历不使用栈法一
void PreOrder(BiTree t){ //访问顺序根左右BTNode *p;while(t){visit(t);//访问根if(t-lchild) tt-lchild;//找到左下结点下一次就循环访问左else if(t-rchild) tt-rchild;//下一次循环访问右else{//如果当前结点既没有左孩子也没有有孩子while(1){//一直往上回溯到有非空的父亲结点、同时找到二叉树的那个“叉”pt;//p指向根ttt-parent;//t指向父亲结点if(!t) break;//如果t为空则说明该节点是空结点排除这种情况if(t-lchildpt-rchild) break;//如果t的左孩子是p且t的右孩子不为空跳出while之后到右结点}if(t)tt-rchild;//往右边访问}}
}三叉链表的前序遍历不使用栈法二
// 【题目】二叉树采用三叉链表的存储结构试编写
// 不借助栈的非递归中序遍历算法。
// 三叉链表类型定义
typedef struct TriTNode
{char data;struct TriTNode *parent, *lchild, *rchild;
} TriTNode, *TriTree;void InOrder(TriTree PT, void (*visit)(char))
/* 不使用栈非递归中序遍历二叉树PT */
/* 对每个结点的元素域data调用函数visit */
{TriTree p PT, pr;while (p){if (p-lchild)p p-lchild; // 寻找最左下结点else{visit(p-data); // 找到最左下结点并访问if (p-rchild){p p-rchild; // 若有右子树转到该子树继续寻找最左下结点}else{pr p; // 否则返回其父亲p p-parent;while (p (p-lchild ! pr || !p-rchild)){ // 若其不是从左子树回溯来的或左结点的父亲并没有右孩子if (p-lchild pr) // 若最左结点的父亲并没有右孩子visit(p-data); // 直接访问父亲不用转到右孩子pr p; // 父亲已被访问故返回上一级p p-parent; // 该while循环沿双亲链一直查找若无右孩子则访问直至找到第一个有右孩子的结点为止但不访问该结点留给下步if语句访问}if (p){ // 访问父亲并转到右孩子经上步while处理可以确定此时p有右孩子visit(p-data);p p-rchild;}}}}
}
一维数组存储二叉树
// 动态输入
void CreateTreeArray(int a[], int n)
{char ch;for (int i 0; i n; i){cin ch;a[i] ch;}
}一维数组存储二叉树的先序遍历
// 前序遍历
#define Maxsize 50
typedef struct BTNodeArray
{int data[Maxsize];int length;
} BTNodeArray;
void PreOrderArray(BTNodeArray t, int i)
{if (i t.length)return;printf(%d, t.data[i]);PreOrderArray(t, i * 2); // 遍历左子树PreOrderArray(t, i * 2 1); // 遍历右子树
}线索二叉树的建立
线索二叉的的基本结构 使用中序遍历的顺序进行线索化。代码中有一个难以理解的点为什么不用p直接找后继而是使用了前驱结点找后继。实际上不是不用p找后继而是从p找不到后继所以只能间接地找前驱的后继这样的方式找后继明白了这点代码就不难懂了。
//中序遍历线索化
void InOrder(ThreadTree p,ThreadTree pre){if(p!NULL){InOrder(p-lchild,pre);if(p-lchildNULL){ //只能通过当前结点找前驱p-lchildpre;p-ltag1;}if(pre-rchildNULL){ //只能通过前驱结点找后继pre-rchildp;pre-rtag1;}prep;InOrder(p-rchild,pre);}return;
}
void InOrderThread(ThreadTree t){ThreadNode *preNULL;if(t!NULL){InOrder(t,pre);pre-rchildNULL;pre-rtag1;}
}真题演练 //建立三叉链表
//删除每一个元素为x的结点以及以他为根的子树且释放相应存储空间
#includeiostream
using namespace std;void BuildTree(BiTree t){char ch;cinch;if(ch#){tNULL;}else{t(BTNode *)malloc(sizeof(BTNode));t-datach;t-parentNULL;t-lchildNULL;t-rchildNULL;if(t-lchild) t-lchild-parentt;if(t-rchild) t-rchild-parentt;BuildTree(t-lchild);BuildTree(t-rchild);}
}
void Destory(BiTree t){if(tNULL) return;if(t-lchild) Destory(t-lchild);if(t-rchild) Destory(t-rchild);free(t); //释放根节点tNULL; //空指针赋值0
}
void DeleteX(BiTree t,char x){if(tNULL) return;if(t-datax) Destory(t);DeleteX(t-lchild,x);DeleteX(t-rchild,x);
}
