1、二叉树的表示法
1.1、二叉链表示法
数据结构定义：
//1 - 二叉链表示法//节点类型为int
typedef struct BiTNode
{int data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;//节点类型为char
typedef struct BiTNodeC
{char data;struct BiTNodeC *lchild, *rchild;
}BiTNodeC, *BiTreeC;
实现：
void play01_2()
{BiTNode *pt1, *pt2, *pt3, *pt4, *pt5;pt1 = (BiTree) malloc(sizeof(BiTNode)); pt2 = (BiTree)malloc(sizeof(BiTNode)); pt3 = (BiTree)malloc(sizeof(BiTNode));pt4 = (BiTree)malloc(sizeof(BiTNode)); pt5 = (BiTree)malloc(sizeof(BiTNode));pt1->data = 1; pt2->data = 2; pt3->data = 3;pt4->data = 4; pt5->data = 5;//表达二叉树pt1->lchild = pt2; pt1->rchild = pt3;pt2->lchild = pt4;pt3->lchild = pt5;//free(pt1); free(pt2); free(pt3); free(pt4); free(pt5);
}
1.2、三叉链表示法
和二叉链表示法相比，多了一个指向父节点的指针。
//2 - 三叉链表示法
typedef struct TriTNode
{int data;struct BiTNode *lchild, *rchild;struct BiTNode *parent; //多了一个指向父节点的指针
}TriTNode, *TriTree;
1.3、双亲链表表示法
数据结构定义：
//3 - 双亲链表表示法（子节点中保存了双亲节点的位置）
#define MAX_TREE_SIZE 100
typedef struct BPTNode
{int data;int parentPosition; //指向双亲的指针（双亲数组下标）char LRTag; //左右孩子标志域 L或R
}BPTNode;typedef struct BPTree
{BPTNode nodes[MAX_TREE_SIZE]; //因为节点之间是分散的，需要把节点存储到数组中int num_node; //节点的数目int root; //根节点的位置，注意此域存储的是父亲节点在数组的下标
}BPTree;
实现：
void play01_3()
{BPTree tree; //定义树tree.root = 0; //根节点位置tree.num_node = 5;//给树的元素赋值//根节点tree.nodes[0].data = 1;//tree.nodes[1].data = 2;tree.nodes[1].parentPosition = 0;tree.nodes[1].LRTag = 'L';tree.nodes[2].data = 3;tree.nodes[2].parentPosition = 0;tree.nodes[2].LRTag = 'R';for (int i = 0; i < 3; i++){cout << tree.nodes[i].data << endl;}
}
2、创建树
2.1、#法创建树
BiTreeC createTree2(const char *s)
{BiTreeC node = nullptr;//1## - 先序字符串static int cur_index = 0;char ch = s[cur_index];cur_index++;if (ch == '#'){return nullptr;}else{node = (BiTreeC)malloc(sizeof(BiTNodeC));if (nullptr == node) return nullptr;memset(node, 0, sizeof(BiTNodeC));node->data = ch;node->lchild = createTree2(s);node->rchild = createTree2(s);}return node;
}const char *s = "ABDH#K###E##CFI###G#J##"; //先序字符串
BiTreeC p = nullptr;
p = createTree2(s);
2.2、中序和先序创建树
基本思想：
中序和先序创建树 算法：
1、通过先序遍历结果中找到根节点root，再通过root在中序遍历结果中找出左子树(左侧)、右子树（右侧）
2、在root的左子树中，找出左子树的根节点（在先序结果中中找），转步骤1；
3、在root的右子树中，找出右子树的根节点（在先序结果中中找），转步骤1；
const string g_pre_str = "ADEBCF";
const string g_in_str = "DEACFB";string split_left(const string root_str, const char& root)
{if (root_str.size() == 1){return "";}string in_str = root_str;string left = in_str.substr(0, in_str.find(root));return left;
}string split_right(const string root_str, const char& root)
{string in_str = root_str;if (root_str.size() == 1 || in_str.find(root) >= in_str.length()-1){return "";}string right = in_str.substr(in_str.find(root) + 1, in_str.length());return right;
}char getRoot(const string root_str)
{size_t pre_index = g_pre_str.length();for (size_t i = 0; i < root_str.length(); i++){size_t tmp = g_pre_str.find(root_str.at(i));pre_index < tmp ? pre_index : pre_index = tmp;}return g_pre_str.at(pre_index);
}BiTreeC createTree_in_and_pre(const string root_str)
{BiTreeC node = nullptr;if (root_str.empty()){return nullptr;}char root = getRoot(root_str);if ('\0' == root){return nullptr;}node = (BiTreeC)malloc(sizeof(BiTNodeC));memset(node, 0, sizeof(BiTNodeC));node->data = root;string left_str = split_left(root_str, root);string right_str = split_right(root_str, root);node->lchild = createTree_in_and_pre(left_str);node->rchild = createTree_in_and_pre(right_str);return node;
}
const char *pre = "ADEBCF";
const char *in = "DEACFB";
BiTreeC p = nullptr;
p = createTree_in_and_pre(g_in_str);
2.3、销毁树
先序创建树则后续销毁。
void freeTree(BiTreeC t)
{if (nullptr == t)return;if (nullptr != t->lchild){freeTree(t->lchild); t->lchild = nullptr;}if (nullptr != t->rchild){freeTree(t->rchild); t->rchild = nullptr;}if(t){free(t);t = nullptr;}return;
}
3、二叉树的遍历
3.1、先序遍历
先序遍历：中左右
//先序遍历
void preOrder(BiTNode* root)
{if (nullptr == root){return;}//打印根节点cout << root->data << " ";//然后 遍历左子树preOrder(root->lchild);//最后 遍历右子树preOrder(root->rchild);return;
}
3.2、中序遍历
中序遍历：左中右
//中序遍历
void inOrder(BiTNode* root)
{if (nullptr == root){return;}//先 遍历左子树inOrder(root->lchild);//然后 打印根节点的值cout << root->data << " ";//最后 遍历右子树inOrder(root->rchild);return;
}
3.3、后序遍历
后序遍历：左右中
//后序遍历
void postOrder(BiTNode* root)
{if (nullptr == root){return;}//先 遍历左子树postOrder(root->lchild);//然后 遍历右子树postOrder(root->rchild);//最后 打印根节点的值cout << root->data << " ";return;
}
3.4、树的非递归遍历
树的非递归遍历（中序遍历），算法基本思想：
中序遍历的几种情况：
分析1：什么时候访问根？什么时候访问左子树？什么时候访问右子树？
当左子树为空或者左子树已经访问完毕，再访问根；
访问根之后，再访问右子树；
分析2：为什么是栈，而不是其他（比如 队列）
先走到的后访问，后走到的先访问，显示是站结构
分析3：节点所有路径情况
步骤1： 找到中序遍历的起点
如果节点 有 左子树，该节点入栈，继续找下一个左子树；
如果该节点 没有 左子树，访问该节点；
步骤2：
如果节点 有 右子树，走到右子树的根节点，重复步骤1；
如果节点 没有 右子树（节点访问完毕），根据栈顶指示访问栈顶元素，并回退；
如果栈为空，表示遍历结束；
注意：入栈的节点表示，本身没有被访问过，同时右子树也没有被访问过。
using TreeStack = stack<BiTreeC>;//步骤①：向左走，直到找到中序遍历的起点
BiTreeC goLeft(BiTreeC root, TreeStack &stack)
{if (nullptr == root){return nullptr;}while (nullptr != root->lchild){stack.push(root); //先压栈（节点有左子树）root = root->lchild; //然后继续找左子树}cout << root->data << " "; //节点没有左子树，直接访问该节点return root;
}//中序 非递归 遍历
void InOrder_stack(BiTreeC root)
{if (nullptr == root){return;}TreeStack stack;BiTreeC t = goLeft(root, stack);while (t){if (nullptr != t->rchild){//如果有右子树，则执行步骤①t = goLeft(t->rchild, stack);}else if(nullptr == t->rchild && !stack.empty()){//如果没有右子树，根据栈顶提示 回退，t = stack.top();stack.pop();//打印cout << t->data << " ";}else{t = nullptr;}}
}
4、树的操作
4.1、求树的高度
int treeDepth(BiTNode* root)
{int leftDepth = 0;int rightDepth = 0;int depth = 0;if (nullptr == root){return depth;}//左子树高度leftDepth = treeDepth(root->lchild);//右子数高度rightDepth = treeDepth(root->rchild);depth = 1 + (leftDepth>rightDepth?leftDepth:rightDepth);return depth;
}
4.2、copy树
BiTree treeCopy(BiTNode* root)
{BiTree newNode = nullptr;BiTree newLeft = nullptr;BiTree newRight = nullptr;if (nullptr == root)return root;newLeft = treeCopy(root->lchild);newRight = treeCopy(root->rchild);//效果与下面等同，因为上面已经判断了 nullptr == root 的情况/* //该代码也可正常运行if (root->lchild){newLeft = treeCopy(root->lchild);}elsereturn nullptr;if (root->rchild){newRight = treeCopy(root->rchild);}elsereturn nullptr;*/newNode = (BiTree)malloc(sizeof(BiTNode));if (!newNode)return nullptr;newNode->lchild = newLeft;newNode->rchild = newRight;newNode->data = root->data;return newNode;
}